一尘不染

点多边形算法

algorithm

我看到以下算法可以检查此链接中的点是否在给定的多边形中:

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;
}

我尝试了这种算法,它实际上非常完美。但是可惜的是,在花了一些时间来理解它之后,我无法很好地理解它。

因此,如果有人能够理解此算法,请向我解释一下。

谢谢。


阅读 178

收藏
2020-07-28

共1个答案

一尘不染

该算法是向右投射光线。循环的每次迭代,都将测试点相对于多边形的边缘之一进行检查。如果该点的y坐标在边的范围内,则if测试的第一行成功。第二行检查测试点是否在该行的左侧(我想-
我没有任何废纸可以检查)。如果是这样,则从测试点向右绘制的线将越过该边缘。

通过反复反转的值c,该算法计算出右线与多边形相交的次数。如果交叉的次数是奇数,则该点在内部;反之,如果是偶数,则该点在外面。

我会担心a)浮点运算的准确性,以及b)具有水平边缘或测试点与顶点的y坐标相同的影响。

2020-07-28