1

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.

Darko Heron
  • 31
  • 1
  • 8
  • Show what you´ve tried so far and where exactly you´re stuck. Stack is not a code-serice, you have to provide some ideas how to solve your *specifc* problem. Asking for writing the complete code is therefor offtopic here. – MakePeaceGreatAgain Oct 04 '16 at 13:24
  • i was calculating like this: ((lowerRightX - upperLeftX) / 2) + upperLeftX = X coord for near middle of polygon ((upperRightY - downLeftY) /2) + downLeftY = Y coord for near middle of polygon and then I checked other list searching for point that has closest X Y coords to that calculated point: var closest = (from entry in myDict where Math.Abs(entry.Key) < 3 && Math.Abs(entry.Value) < 3 orderby entry.Key ascending select entry).FirstOrDefault(); Works in 90% of my cases. – Darko Heron Oct 04 '16 at 13:39
  • Have look at this http://stackoverflow.com/questions/1560492/how-to-tell-whether-a-point-is-to-the-right-or-left-side-of-a-line Now you just check all the lines. – Lidaranis Oct 04 '16 at 13:47
  • If you can use GDI+ you can build a GraphicsPath and use it IsVisivle(point) method. – TaW Oct 04 '16 at 13:54

3 Answers3

6

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).

Kyle
  • 6,500
  • 2
  • 31
  • 41
1

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

Blindman67
  • 51,134
  • 11
  • 73
  • 136
  • An easier test for a point within a polygon is to count the number of polygon edges that cross a ray originating from the test point and going in any direction. If the number of intersections is odd, the point is in the polygon. If it's even, it's outside of the polygon. This doesn't require any special treatment for concave polygons (or even self-intersecting ones). – Kyle Oct 04 '16 at 15:42
  • @kyle yes indeed, though I am not sure which is more efficient (assuming the bounding box test is done first in both cases). I will have to test this. Thanks for the heads up.. :) – Blindman67 Oct 04 '16 at 15:59
  • @kyle The reason the cross product method is better is that you can store the results of the polygon (left/right) turns as bits. As 4sided polygons are symmetrical (in terms of left right turns) you need only 3bits. 7 variants represent the polygon and are transformationally invariant (rotate,skew,scale can all be applied). The test then, with most outside conditions able to return a result in a minimum of 2 cross products. This offers a significant performance advantage over the edge cross method. – Blindman67 Oct 04 '16 at 19:54
1

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;
    }
Darko Heron
  • 31
  • 1
  • 8