Search code examples
c#pointpolygonspoint-in-polygon

Point inside compound polygon

I have seen many algorithms for point inside polygon. What I learned so far came from this site: http://alienryderflex.com/polygon/

The best algorithm usually look like this:

var inside = false;
for (int i = poly.Count - 1, j = 0; j < poly.Count; i = j++)
{
    var p1 = poly.Vertices[i];
    var p2 = poly.Vertices[j];

    if ((p1.Y < testY != p2.Y < testY) && //at least one point is below the Y threshold and the other is above or equal
        (p1.X >= testX || p2.X >= testX)) //optimisation: at least one point must be to the right of the test point
    {
        if (p1.X + (testY - p1.Y) / (p2.Y - p1.Y) * (p2.X - p1.X) > testX)
            inside = !inside;
    }
}

But compound polygon segments can either be a straight line or an arc. Arc segments are defined by the normal 2 points and a bulge which is used to find the center and radius of the arc. The 2 points are used to find the start and end angle of the arc.

Using the test point Y and Math.Asin((testY - arc.Center.Y) / arc.Radius) I can find the angle at which the test line intersect the circle. When the test line intersects the circle, there are 2 intersection points. After that I test the angle to know if the intersections points are on the arc.

My result are pretty good so far except that when the test point happen have exactly the same y as a vertex. It will be counted for the 2 adjacent segments. For a normal segment, this case is avoided by the if (p1.Y < testY != p2.Y < testY)
enter image description here

I can't find any similar implementation for compound polygon for the arc part. Did someone ever had to do something similar or have any hint?

Solution

  • With this line

    p1.Y < testY != p2.Y < testY

    you only count segments that approach the query line from the bottom (or cross it). And this is exactly what you need to do for the arcs.

    For this, it may be desirable to split the arc into monotone parts (with respect to the y-axis). In your example, the lower arc already is monotone. The upper arc should be split into two (along a vertical line through the its center). Then you have minY and maxY for each segment and you can apply the above formula:

    minY < testY != maxY < testY

    Alternatively, you could check if the intersection is at the arc end (equal y-coordinate) and evaluate if the arc continues downwards based on the angle and arc direction. But depending on the implementation, this might have some numerical stability issues. The first option (with splitting into monotone parts) is probably easier to implement. And it generalizes to other primitives.