多边形包含点算法解释

Question

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

另外，这个功能有没有失效的情况？

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

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

Answer 1

就是维基百科上描述的ray casting algorithm。

The number of intersections for a ray passing from the exterior of the polygon to any point; if odd, it shows that the point lies inside the polygon. If it is even, the point lies outside the polygon; this test also works in three dimensions.

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)

解释：计算多边形线段与线O相交的X坐标，然后测试是否为目标点左侧。

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

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

多边形包含点算法解释

Polygon contains point algorithm explanation

language-agnostic

algorithm

geometry