点入多边形算法 [英] 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 坐标在边的范围内，则 if 测试的第一行成功.第二行检查测试点是否在该行的左侧(我认为 - 我没有任何可检查的废纸).如果这是真的，则从测试点向右绘制的线穿过该边缘.

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.

不过，我会担心 a) 浮点运算的准确性，以及 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屋！