Checking if a longitude/latitude coordinate resides inside a complex polygon in an embedded device?

Question

I need the user to be able to draw a complex polygon on a map and then have the application check if a given longitude/latitude resides within that polygon.

I was only able to find algorithms that were using a simple x/y cartesian coordinate system that doesn't compensate for the curvature of the earth.

The user draws the polygon on a PC, where the points are transferred over radio to a embedded device, which then needs to check if the given polygon resides within it's current position (taken from GPS).

As this is for an embedded device I am not able to use huge libraries, rather I need the algorithm to perform the check myself or a very small library. But I seem to be unable to find any such algorithm.

What sort of distances are you looking at? I do this sort of work a lot and if you're talking about relatively small polygons like say < 1000 meters those simple algorithms will work fine relative to the accuracy of a standard GPS. Earth curvature doesn't have much effect over smaller distances. — PeterJ
Note that if you're working with GIS, you might like this SO sister-site: gis.stackexchange.com — Drew Noakes
@PeterJ I'm looking to use this both on a very-wide scale (hundreds of kilometers) but still require very-close precision as it will also be used within segmented areas that are < 1 km — ChewToy
Fair enough, but remember unless segments are a long way apart it won't make a difference. For example a 200KM highway with a series of segments a few KM apart won't make much difference. It's only if you say have an edge on a polygon 100KM long that it's really going to make a difference, which is pretty rare in my experience. Most real-life things like say a city border aren't that straight in practice so it's worth some thought about likely errors and if you really need it. At highway speeds you'll probably also need some dead reckoning too if you really need that precision. — PeterJ

Drew Noakes Drew Noakes · Accepted Answer · 2012-12-19T11:13:30

Here's an implementation I wrote in C# for a Polygon class that contains a list of vertices. It doesn't consider the curvature of the Earth. Rather, you would pre-process the polygon into smaller segments prior to running this.

The performance of this algorithm is very good. Even for polygons with thousands of edges it completes in around one or two milliseconds on my desktop.

The code has been optimised quite a bit and so isn't that readable as psuedo-code.

public bool Contains(GeoLocation location)
{
    if (!Bounds.Contains(location))
        return false;

    var lastPoint = _vertices[_vertices.Length - 1];
    var isInside = false;
    var x = location.Longitude;
    foreach (var point in _vertices)
    {
        var x1 = lastPoint.Longitude;
        var x2 = point.Longitude;
        var dx = x2 - x1;

        if (Math.Abs(dx) > 180.0)
        {
            // we have, most likely, just jumped the dateline (could do further validation to this effect if needed).  normalise the numbers.
            if (x > 0)
            {
                while (x1 < 0)
                    x1 += 360;
                while (x2 < 0)
                    x2 += 360;
            }
            else
            {
                while (x1 > 0)
                    x1 -= 360;
                while (x2 > 0)
                    x2 -= 360;
            }
            dx = x2 - x1;
        }

        if ((x1 <= x && x2 > x) || (x1 >= x && x2 < x))
        {
            var grad = (point.Latitude - lastPoint.Latitude) / dx;
            var intersectAtLat = lastPoint.Latitude + ((x - x1) * grad);

            if (intersectAtLat > location.Latitude)
                isInside = !isInside;
        }
        lastPoint = point;
    }

    return isInside;
}

The basic idea is to find all edges of the polygon that span the 'x' position of the point you're testing against. Then you find how many of them intersect the vertical line that extends above your point. If an even number cross above the point, then you're outside the polygon. If an odd number cross above, then you're inside.

Checking if a longitude/latitude coordinate resides inside a complex polygon in an embedded device?

2 Answers