服务器之家

服务器之家 > 正文

C语言实现的PNPoly算法代码例子

时间:2021-01-21 14:13     来源/作者:C语言程序设计

C语言的实验用到的一个算法,判断一个点是否在多边形的内部。C的代码如下:

?
1
2
3
4
5
6
7
8
9
10
11
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)很好理解,就是一条边上的两个顶点分别在待测点的上方和下方,通过这条语句可以知道从待测点向右引出的射线有可能与该条边相交(只要待测点在边的左侧即可)。

但具体判断相交就要交给解析几何了。建系写出该条边所在直线的方程:

C语言实现的PNPoly算法代码例子

变形一下:

C语言实现的PNPoly算法代码例子

代入待测点坐标,根据图形关系得到这个不等式:

C语言实现的PNPoly算法代码例子

也就是语句testx < vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]了.

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享 2020-04-07
返回顶部