如何确定二维点是否位于多边形内？

Question

如何确定二维点是否位于多边形内？我想创造一个快地二维点内多边形算法，用于命中测试。Polygon.contains(p:Point))。如能就有效的技术提出建议，将不胜感激。

Answer 1

我认为下面的代码是最好的解决方案(摘自这里):

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

论点

• 内涵

  多边形中的顶点数。是否在结尾重复第一个顶点，已经在上面提到的文章中讨论过了。

• vertx，verty

  数组包含多边形顶点的x坐标和y坐标。

• 遗嘱

  *测试点的x和y坐标。

它既短又有效，同时适用于凸多边形和凹多边形。正如前面所建议的，您应该首先检查包围矩形并分别处理多边形孔。

这背后的想法很简单。作者将其描述如下：

我从测试点水平地运行一条半无限射线(增加x，固定y)，并计算它穿过多少个边。在每个十字路口，光线在内部和外部之间切换。这叫做Jordan曲线定理。

每次水平射线穿过任何边缘时，变量c都从0切换到1和1到0。基本上，它是跟踪交叉边的数目是偶数还是奇数。0表示偶数，1表示奇数。