多边形包含点算法解释
多边形包含点算法解释
提问于 2018-07-15 02:57:12
我在许多不同的问题上见过这个解决方案的变体，所以关于包含点的多边形的问题，但是问题是没有一个作者给出任何解释。我似乎不知道这个函数是如何工作的，而且看到许多其他评论者对此的问题没有得到回答，我认为最好只是问一下，这样就会有一个具体的解释了。
此外，是否有此功能失败的情况？
更新:我知道光线投射方法是如何工作的，有一些非常好的资源，但是我真的很困惑这段代码具体是如何工作的。
public static bool(ean) PolygonContainsPoint(Point[] polygon, Point point)
{
bool(ean) result = false;
int j = polygon.Count - 1;
for (int i = 0; i < polygon.Count; i++)
{
if (polygon[i].Y < point.Y && polygon[j].Y >= point.Y || polygon[j].Y < point.Y && polygon[i].Y >= point.Y)
{
if (polygon[i].X + (point.Y - polygon[i].Y) / (polygon[j].Y - polygon[i].Y) * (polygon[j].X - polygon[i].X) < point.X)
{
result = !result;
}
}
j = i;
}
return result;
}回答 1
Stack Overflow用户
回答已采纳
发布于 2018-07-15 03:24:51
这是维基百科上描述的光线投射算法。
光线从多边形外部传递到任意点的交叉点数；如果是奇数，则表示该点位于多边形内。如果是偶数，点在多边形之外；这个测试也在三维上工作。
int j = polygon.Count - 1;
for (int i = 0; i < polygon.Count; i++)
{
// ...
j = i;
}说明:代码循环遍历多边形的每个线段，其中i是当前点的索引，j是前一点的索引(第一点的前一点是最后一点，因为多边形是关闭的)。
if (polygon[i].Y < point.Y && polygon[j].Y >= point.Y ||
polygon[j].Y < point.Y && polygon[i].Y >= point.Y)说明:如果多边形线段跨越线O，，即如果它从上面开始，结束在下面，或者开始在下面和上面结束。
if (polygon[i].X + (point.Y - polygon[i].Y)
/ (polygon[j].Y - polygon[i].Y)
* (polygon[j].X - polygon[i].X)
< point.X)说明:计算多边形线段穿过线的X坐标，然后测试它是否位于目标点的左侧。
result = false;
for each segment:
if segment crosses on the left:
result = !result;
return result;说明:如果在目标点左边的O线上的多边形线段数目是奇数，那么目标点就在多边形内。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51344870
复制相关文章
相似问题
腾讯云开发者
