C语言实现的PNPoly算法代码例子
写C语言的实验用到的一个算法，判断一个点是否在多边形的内部。C的代码如下：
int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
int i, j, c = 0;
for (i = 0, j = nvert-1; i < nvert; j = i++) {
if ( ((verty[i]>testy) != (verty[j]>testy)) &&
(testx < (vertx[j]-vertx[i]) * (testy-verty[i]) /
(verty[j]-verty[i]) + vertx[i]) )
c = !c;
}
return c;
}
其中nvert是多边形顶点的个数，vertx和verty分别是多边形顶点横、纵坐标的数组，textx和testy是待测点的坐标。这个算法是由W. Randolph Franklin提出的，根据Jordan curve theorem，多边形将平面分为内外两个区域，假设待测点在多边形内部，从待测点引出一条射线必然会与多边形有至少一个交点。该射线与多边形第一次相交时将“冲出”多边形，第二次相交将“进入”多边形，依此类推，若射线与多边形有奇数个交点，则该点在多边形内部，反之则在外部。
PNPoly算法正是从待测点引出一条水平向右的射线，并计算与多边形的交点个数。解释一下这段代码：for (i = 0, j = nvert-1; i < nvert; j = i++)循环的含义就是始终让j = i – 1，如果i = 0那么j = nvert – 1，从而依次检验多边形的每条边。接下来的重点就是条件语句，(verty[i]>testy) != (verty[j]>testy)很好理解，就是一条边上的两个顶点分别在待测点的上方和下方，通过这条语句可以知道从待测点向右引出的射线有可能与该条边相交（只要待测点在边的左侧即可）。
但具体判断相交就要交给解析几何了。建系写出该条边所在直线的方程：
变形一下：
代入待测点坐标，根据图形关系得到这个不等式：
也就是语句testx < vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]了.
-
本文向大家介绍C语言实现九大排序算法的实例代码，包括了C语言实现九大排序算法的实例代码的使用技巧和注意事项，需要的朋友参考一下 直接插入排序 将数组分为两个部分，一个是有序部分，一个是无序部分。从无序部分中依次取出元素插入到有序部分中。过程就是遍历有序部分，实现起来比较简单。 折半插入排序 折半插入再直接插入上有改进，用折半搜索替换遍历数组，在数组长度大时能够提升查找性能。其本质还是从无序部分取出
-
本文向大家介绍C语言中K-means算法实现代码，包括了C语言中K-means算法实现代码的使用技巧和注意事项，需要的朋友参考一下 K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。 算法过程如下： 1）从N个样本随机选取K个样本作为质心 2）对剩余的每
-
本文向大家介绍马尔可夫链算法（markov算法）的awk、C++、C语言实现代码，包括了马尔可夫链算法（markov算法）的awk、C++、C语言实现代码的使用技巧和注意事项，需要的朋友参考一下 1. 问题描述 马尔可夫链算法用于生成一段随机的英文，其思想非常简单。首先读入数据，然后将读入的数据分成前缀和后缀两部分，通过前缀来随机获取后缀，籍此产生一段可读的随机英文。 为了说明方便，假设我们有如下
-
本文向大家介绍c语言5个常用的排序算法实例代码，包括了c语言5个常用的排序算法实例代码的使用技巧和注意事项，需要的朋友参考一下 1.插入排序 基本思想：插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。 2.希尔排序 基本思想：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个
-
本文向大家介绍C语言实现图的搜索算法示例，包括了C语言实现图的搜索算法示例的使用技巧和注意事项，需要的朋友参考一下 本文实例讲述了C语言实现图的搜索算法。分享给大家供大家参考，具体如下： 在游戏中，常常遇到路径规划问题，用到图的相关算法，我们以简单图来学习。 图通常有两种表示方式，矩阵和邻接表。矩阵表示简单，运算快，但当矩阵是稀疏矩阵的时候就存在空间浪费的问题，并且效率也会下降，而邻接表节约空间，
-
本文向大家介绍C语言实现树的动态查找实例代码，包括了C语言实现树的动态查找实例代码的使用技巧和注意事项，需要的朋友参考一下 C语言实现树的动态查找实例代码 本例演示一种树数据结构存储记录集合时的动态查找方法。首先程序通过construct()函数，利用已经存在的结构体数组数据建立一个二叉树，建立树的过程中，要保证每个节点的值都大于它的左子树上节点的值而小于它右子树所有节点的值，该函数返回建立树的根