Geo Fencing - point inside/outside polygon

Question

I would like to determine a polygon and implement an algorithm which would check if a point is inside or outside the polygon.

Does anyone know if there is any example available of any similar algorithm?

Answer 1

After searching the web and trying various implementations and porting them from C++ to C# I finally got my code straight:

        public static bool PointInPolygon(LatLong p, List<LatLong> poly)
    {
        int n = poly.Count();

        poly.Add(new LatLong { Lat = poly[0].Lat, Lon = poly[0].Lon });
        LatLong[] v = poly.ToArray();

        int wn = 0;    // the winding number counter

        // loop through all edges of the polygon
        for (int i = 0; i < n; i++)
        {   // edge from V[i] to V[i+1]
            if (v[i].Lat <= p.Lat)
            {         // start y <= P.y
                if (v[i + 1].Lat > p.Lat)      // an upward crossing
                    if (isLeft(v[i], v[i + 1], p) > 0)  // P left of edge
                        ++wn;            // have a valid up intersect
            }
            else
            {                       // start y > P.y (no test needed)
                if (v[i + 1].Lat <= p.Lat)     // a downward crossing
                    if (isLeft(v[i], v[i + 1], p) < 0)  // P right of edge
                        --wn;            // have a valid down intersect
            }
        }
        if (wn != 0)
            return true;
        else
            return false;

    }

    private static int isLeft(LatLong P0, LatLong P1, LatLong P2)
    {
        double calc = ((P1.Lon - P0.Lon) * (P2.Lat - P0.Lat)
                - (P2.Lon - P0.Lon) * (P1.Lat - P0.Lat));
        if (calc > 0)
            return 1;
        else if (calc < 0)
            return -1;
        else
            return 0;
    }

The isLeft function was giving me rounding problems and I spent hours without realizing that I was doing the conversion wrong, so forgive me for the lame if block at the end of that function.

BTW, this is the original code and article: http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

Answer 2

By far the best explanation and implementation can be found at Point In Polygon Winding Number Inclusion

There is even a C++ implementation at the end of the well explained article. This site also contains some great algorithms/solutions for other geometry based problems.

I have modified and used the C++ implementation and also created a C# implementation. You definitely want to use the Winding Number algorithm as it is more accurate than the edge crossing algorithm and it is very fast.

Answer 3

The problem is easier if your polygon is convex. If so, you can do a simple test for each line to see if the point is on the inside or outside of that line (extending to infinity in both directions). Otherwise, for concave polygons, draw an imaginary ray from your point out to infinity (in any direction). Count how many times it crosses a boundary line. Odd means the point is inside, even means the point is outside.

This last algorithm is trickier than it looks. You will have to be very careful about what happens when your imaginary ray exactly hits one of the polygon's vertices.

If your imaginary ray goes in the -x direction, you can choose only to count lines that include at least one point whose y coordinate is strictly less than the y coordinate of your point. This is how you get most of the weird edge cases to work correctly.

Answer 4

the polygon is defined as a sequential list of point pairs A, B, C .... A. no side A-B, B-C ... crosses any other side

Determine box Xmin, Xmax, Ymin, Ymax

case 1 the test point P lies outside the box

case 2 the test point P lies inside the box:

Determine the 'diameter' D of the box {[Xmin,Ymin] - [Xmax, Ymax]} ( and add a little extra to avoid possible confusion with D being on a side)

Determine the gradients M of all sides

Find a gradient Mt most different from all gradients M

The test line runs from P at gradient Mt a distance D.

Set the count of intersections to zero

For each of the sides A-B, B-C test for the intersection of P-D with a side from its start up to but NOT INCLUDING its end. Increment the count of intersections if required. Note that a zero distance from P to the intersection indicates that P is ON a side

An odd count indicates P is inside the polygon

Answer 5

C# code

bool IsPointInPolygon(List<Loc> poly, Loc point)
{
    int i, j;
    bool c = false;
    for (i = 0, j = poly.Count - 1; i < poly.Count; j = i++)
    {
        if ((((poly[i].Lt <= point.Lt) && (point.Lt < poly[j].Lt)) 
                || ((poly[j].Lt <= point.Lt) && (point.Lt < poly[i].Lt))) 
                && (point.Lg < (poly[j].Lg - poly[i].Lg) * (point.Lt - poly[i].Lt) 
                    / (poly[j].Lt - poly[i].Lt) + poly[i].Lg))
        {

            c = !c;
        }
    }

    return c;
}

Location class

public class Loc
{
    private double lt;
    private double lg;

    public double Lg
    {
        get { return lg; }
        set { lg = value; }
    }

    public double Lt
    {
        get { return lt; }
        set { lt = value; }
    }

    public Loc(double lt, double lg)
    {
        this.lt = lt;
        this.lg = lg;
    }
}

Answer 6

I add one detail to help people who live in the... south of earth!! If you're in Brazil (that's my case), our GPS coord are all negatives. And all these algo give wrong results.

The easiest way if to use the absolute values of the Lat and Long of all point. And in that case Jan Kobersky's algo is perfect.