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

Question

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

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

Answer 1

我认为下面的代码是最好的解决方案(摘自这里):int&nbsp;pnpoly(int&nbsp;nvert,&nbsp;float&nbsp;*vertx,&nbsp;float&nbsp;*verty,&nbsp;float&nbsp;testx,&nbsp;float&nbsp;testy){ &nbsp;&nbsp;int&nbsp;i,&nbsp;j,&nbsp;c&nbsp;=&nbsp;0; &nbsp;&nbsp;for&nbsp;(i&nbsp;=&nbsp;0,&nbsp;j&nbsp;=&nbsp;nvert-1;&nbsp;i&nbsp;<&nbsp;nvert;&nbsp;j&nbsp;=&nbsp;i++)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(&nbsp;((verty[i]>testy)&nbsp;!=&nbsp;(verty[j]>testy))&nbsp;&& &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(testx&nbsp;<&nbsp;(vertx[j]-vertx[i])&nbsp;*&nbsp;(testy-verty[i])&nbsp;/&nbsp;(verty[j]-verty[i])&nbsp;+&nbsp;vertx[i])&nbsp;) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c&nbsp;=&nbsp;!c; &nbsp;&nbsp;} &nbsp;&nbsp;return&nbsp;c;}论点内涵多边形中的顶点数。是否在结尾重复第一个顶点，已经在上面提到的文章中讨论过了。vertx，verty数组包含多边形顶点的x坐标和y坐标。遗嘱*测试点的x和y坐标。它既短又有效，同时适用于凸多边形和凹多边形。正如前面所建议的，您应该首先检查包围矩形并分别处理多边形孔。这背后的想法很简单。作者将其描述如下：我从测试点水平地运行一条半无限射线(增加x，固定y)，并计算它穿过多少个边。在每个十字路口，光线在内部和外部之间切换。这叫做Jordan曲线定理。每次水平射线穿过任何边缘时，变量c都从0切换到1和1到0。基本上，它是跟踪交叉边的数目是偶数还是奇数。0表示偶数，1表示奇数。