时间戳

首页 > 解决方案 > 多边形包含点算法解释

algorithm - 多边形包含点算法解释

问题描述

我已经在许多关于包含点的多边形的不同 SO 问题上看到了这个解决方案的变体，但问题是作者都没有给出任何解释。我似乎无法弄清楚这个功能是如何工作的，并且看到许多其他评论者对此的问题没有得到解答，我认为最好只是问一下，这样会有一个具体的解释。

另外，是否存在此功能失败的情况？

更新： 我确实知道光线投射方法是如何工作的，有一些非常好的资源，但我真的很困惑这段代码是如何具体工作的。 

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

标签： algorithmlanguage-agnosticgeometry

解决方案

它是维基百科上描述的光线投射算法。

RecursiveEvenPolygon

从多边形外部到任意点的光线的交点数；如果为奇数，则表明该点位于多边形内。如果是偶数，则该点位于多边形之外；这个测试也适用于三个维度。

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坐标O，然后测试是否在目标点的左侧。

result = false;
for each segment:
    if segment crosses on the left:
        result = !result;
return result;

解释：O如果目标点左侧与直线相交的多边形线段数为奇数，则目标点在多边形内。

推荐阅读