Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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.

like image 279
ChewToy Avatar asked Dec 19 '12 10:12

ChewToy


People also ask

How do you determine if a coordinate is in latitude or longitude?

The first number is always the latitude and the second is the longitude. It easy to remember which is which if you think of the two coordinates in alphabetical terms: latitude comes before longitude in the dictionary. For example, the Empire State Building lies at 40.748440°, -73.984559°.

How do you determine if a point is inside or outside a polygon?

To determine the status of a point (xp,yp) consider a horizontal ray emanating from (xp,yp) and to the right. If the number of times this ray intersects the line segments making up the polygon is even then the point is outside the polygon.

What technology can we use to determine latitude and longitude?

You can easily find the latitude and longitude of any location using the Google Maps app on your iOS or Android device.


2 Answers

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.

like image 60
Drew Noakes Avatar answered Oct 11 '22 09:10

Drew Noakes


Good explanations and simple C code that you can convert to your needs

http://alienryderflex.com/polygon/

Combine the polygon check with a RTree for quick culling of the search tree if you have many non overlapping polygons.

like image 30
Niclas Lindgren Avatar answered Oct 11 '22 09:10

Niclas Lindgren