我看到以下算法可以检查此链接中的点是否在给定的多边形中:
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; }
我尝试了这种算法,它实际上非常完美。但是可惜的是,在花了一些时间来理解它之后,我无法很好地理解它。
因此,如果有人能够理解此算法,请向我解释一下。
谢谢。
该算法是向右投射光线。循环的每次迭代,都将测试点相对于多边形的边缘之一进行检查。如果该点的y坐标在边的范围内,则if测试的第一行成功。第二行检查测试点是否在该行的左侧(我想- 我没有任何废纸可以检查)。如果是这样,则从测试点向右绘制的线将越过该边缘。
通过反复反转的值c,该算法计算出右线与多边形相交的次数。如果交叉的次数是奇数,则该点在内部;反之,如果是偶数,则该点在外面。
c
我会担心a)浮点运算的准确性,以及b)具有水平边缘或测试点与顶点的y坐标相同的影响。