点在多边形算法 [英] Point in Polygon Algorithm

问题描述

我看到了下面的算法工作，检查点是否在此链接给定的多边形：

I saw the below algorithm works to check if a point is in a given polygon from this link:

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

我想这个算法，它的实际工作只是完美。但可悲的是，我可以好后，花一些时间去得到它的想法不明白。

I tried this algorithm and it actually works just perfect. But sadly I cannot understand it well after spending some time trying to get the idea of it.

所以，如果有人能够理解这个算法，请解释给我一点点。

So if someone is able to understand this algorithm, please explain it to me a little.

感谢你。

推荐答案

的算法是光线投射到右侧。循环的每次迭代中，测试点检查针对多边形的边缘之一。如果该测试的第一行成功，如果点的Y坐标为边缘的范围内。第二行检查测试点是否是该行的左边（我想 - 我还没有得到任何草稿纸手检查）。如果是真的，从测试点向右绘制的线横跨边缘的地方。

The algorithm is ray-casting to the right. Each iteration of the loop, the test point is checked against one of the polygon's edges. The first line of the if-test succeeds if the point's y-coord is within the edge's scope. The second line checks whether the test point is to the left of the line (I think - I haven't got any scrap paper to hand to check). If that is true the line drawn rightwards from the test point crosses that edge.

通过反复颠倒的 C值，该算法计数多少次，右线交叉的多边形。如果它穿越的次数为奇数，则该点是在里面;如果偶数，该点是外

By repeatedly inverting the value of c, the algorithm counts how many times the rightward line crosses the polygon. If it crosses an odd number of times, then the point is inside; if an even number, the point is outside.

我将同一个关注）的浮点运算的准确性，和b）具有一个水平边缘，或一个测试点使用相同的y坐标为顶点，但带来的影响。

I would have concerns with a) the accuracy of floating-point arithmetic, and b) the effects of having a horizontal edge, or a test point with the same y-coord as a vertex, though.

这篇关于点在多边形算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！