检查是否经/纬度坐标驻留在一个复杂的多边形内部的嵌入式设备？

问题描述

我需要用户能够利用一个复杂的多边形地图上，然后具有该应用程序检查，如果一个给定的经度/纬度驻留在多边形内

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.

我才能够找到的是用简单的X / Y直角坐标系，不补偿地球曲率的算法。

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.

用户绘制多边形PC机，其中该点被转移通过无线电向嵌入式​​设备，然后需要检查，如果给定的多边形驻留在它的当前位置（从GPS获取）上

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.

推荐答案

下面是一个实现我写在C＃中包含顶点列表的多边形类。它不考虑地球的曲率。相反，你会先pre-过程中的多边形分成小段来运行此。

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.

在code已被优化了不少，所以是不是可读性psuedo- code。

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;
}

其基本思想是找到多边形的跨越你对测试点的X位置的所有边缘。然后，你会发现他们中的多少相交上面的点延伸的垂直线。如果偶数交叉点上方，那么你的多边形外。如果奇数跨以上，那么你在里面。

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.

这篇关于检查是否经/纬度坐标驻留在一个复杂的多边形内部的嵌入式设备？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！