Is point inside polygon?

问题:

I need to write a function that will calculate if a point is inside polygon (true/false).

Polygon always contains 4 points. I'm reading polygons and points from SVG file

<g id="polygons">
    <g id="LWPOLYLINE_183_">
        <polyline class="st10" points="37.067,24.692 36.031,23.795 35.079,24.894 36.11,25.786 37.067,24.692   " />
    </g>
    <g id="LWPOLYLINE_184_">
        <polyline class="st10" points="35.729,23.8 35.413,23.516 34.625,24.39 34.945,24.67 35.729,23.8   " />
    </g>
    <g id="LWPOLYLINE_185_">
        <polyline class="st10" points="34.483,24.368 33.975,23.925 34.743,23.047 35.209,23.454 34.483,24.368   " />
    </g>
    <g id="LWPOLYLINE_227_">
        <polyline class="st10" points="36.593,22.064 36.009,21.563 35.165,22.57 35.736,23.061 36.593,22.064   " />
    </g>
</g>
<g id="numbers">
    <g id="TEXT_1647_">
        <text transform="matrix(0.7 0 0 1 34.5876 23.8689)" class="st12 st2 st13">169</text>
    </g>
    <g id="TEXT_1646_">
        <text transform="matrix(0.7 0 0 1 35.1049 24.1273)" class="st12 st2 st13">168</text>
    </g>
    <g id="TEXT_1645_">
        <text transform="matrix(0.7 0 0 1 35.924 24.7302)" class="st12 st2 st13">167</text>
    </g>
    <g id="TEXT_1643_">
        <text transform="matrix(0.7 0 0 1 36.0102 22.4477)" class="st12 st2 st13">174</text>
    </g>
</g>

So for polyline it would be the first 4 sets of coordinates and for text X and Y are last 2 numbers in matrix brackets. Also don't know if that point for text is the center of text or bottom left corner (suppose it's this).

So far I got all coordinates for points and polygons in lists so I'm cross checking that way.

回答1:

A simple way to test whether a point is inside a polygon is to count the number of intersections between the edges of the polygon and a ray originating from the test point. Because you can pick the ray to be whatever you want, it's usually convenient to pick it to be parallel to the X axis. The code for that looks something like this:

public static bool IsInPolygon( this Point testPoint, IList<Point> vertices )
{
    if( vertices.Count < 3 ) return false;
    bool isInPolygon = false;
    var lastVertex = vertices[vertices.Count - 1];
    foreach( var vertex in vertices )
    {
        if( testPoint.Y.IsBetween( lastVertex.Y, vertex.Y ) )
        {
            double t = ( testPoint.Y - lastVertex.Y ) / ( vertex.Y - lastVertex.Y );
            double x = t * ( vertex.X - lastVertex.X ) + lastVertex.X;
            if( x >= testPoint.X ) isInPolygon = !isInPolygon;
        }
        else
        {
            if( testPoint.Y == lastVertex.Y && testPoint.X < lastVertex.X && vertex.Y > testPoint.Y ) isInPolygon = !isInPolygon;
            if( testPoint.Y == vertex.Y && testPoint.X < vertex.X && lastVertex.Y > testPoint.Y ) isInPolygon = !isInPolygon;
        }

        lastVertex = vertex;
    }

    return isInPolygon;
}

public static bool IsBetween( this double x, double a, double b )
{
    return ( x - a ) * ( x - b ) < 0;
}

There's some extra code stuffed in there to deal with some literal corner cases (if the test ray hits a vertex directly, that needs some special treatment).

回答2:

Given 4 points that define the vertices of a polygon, in order, clockwise or counterclockwise. To determine if a points is inside first workout if the polygon is concave by getting the cross product of each pair of lines.

The polygon is p1,p2,p3,p4 each have a x and y.

To get the cross product get 3 points, p1,p2,p3 where p2 is the vertex where the two lines join.

cross = (p2.x-p1.x) * (p3.y-p2.y) - (p2.y-p1.y) * (p3.x-p2.x);

Do for {p1,p2,p3}, {p2,p3,p4},{p3,p4,p1}, and {p4,p1,p2}

If the cross is the same sign for all verts (note 0 is both negative and positive) then the polygon is concave.

If not all the same only one can be different. You need to split the polygon into two 3 sided polygons by joining the different point with the one opposite.

Eg is cross of p2,p3,p4 is negative and the rest positive then you have two polygons p1,p2,p3 and p3,p4,p1

Now you have either one or two polygons.

Calculate the cross for the point you are testing against each line

cross = (p2.x-p1.x) * (testPoint.y-p1.y) - (p2.y-p1.y) * (testPoint.x-p1.x);

Do for each line {p1,p2}, {p2,p3}, {p3,p4},{p4,p1}

If the sign is the same for all the line segments then the point is inside the polygon. If you have two polygons, you only need to satisfy the same sign condition for one polygon

回答3:

Solved it this way:

public static bool IsPointInPolygon4(PointF[] polygon, PointF testPoint)
    {
        bool result = false;
        int j = polygon.Count() - 1;
        for (int i = 0; i < polygon.Count(); i++)
        {
            if (polygon[i].Y < testPoint.Y && polygon[j].Y >= testPoint.Y || polygon[j].Y < testPoint.Y && polygon[i].Y >= testPoint.Y)
            {
                if (polygon[i].X + (testPoint.Y - polygon[i].Y) / (polygon[j].Y - polygon[i].Y) * (polygon[j].X - polygon[i].X) < testPoint.X)
                {
                    result = !result;
                }
            }
            j = i;
        }
        return result;
    }