Search code examples
algorithmlanguage-agnosticgeometry

Polygon contains point algorithm explanation

I have seen variants of this solution on many different SO questions about polygons containing a point, but the issue is none of the authors give any explanation. I cannot seem to figure out how this function works, and seeing that many other commenters have had their questions about this go unanswered, I thought it best to just ask so there would be a concrete explanation.

Also, are there any cases where this function fails?

UPDATE: I do know how the raycasting method works, there are some very good resources for that, but I am really confused how this code works specifically. 

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

  • It is the ray casting algorithm described on Wikipedia.

    RecursiveEvenPolygon

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

    Explanation: The code loops through each line segment of the polygon, with i being index of current point, and j being index of previous point (previous of first point is the last point, since polygon is closed).

    if (polygon[i].Y < point.Y && polygon[j].Y >= point.Y ||
    polygon[j].Y < point.Y && polygon[i].Y >= point.Y)

    Explanation: If the polygon line segment crosses line O, i.e. if it starts above and ends below, or starts below and ends above.

    if (polygon[i].X + (point.Y - polygon[i].Y)
    / (polygon[j].Y - polygon[i].Y)
    * (polygon[j].X - polygon[i].X)
    < point.X)

    Explanation: Calculate the X coordinate where the polygon line segment crosses line O, then test if that is to the left of target point.

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

    Explanation: If the number of polygon line segments crossing line O to the left of the target point is odd, then the target point is inside the polygon.