检查经度/纬度坐标是否位于嵌入式设备中的复杂多边形内？

Question

我需要用户能够在地图上绘制复杂的多边形,然后让应用程序检查给定的经度/纬度是否位于该多边形内.

我只能找到使用简单的x/y笛卡尔坐标系的算法,该坐标系不能补偿地球的曲率.

用户在PC上绘制多边形,其中点通过无线电传输到嵌入式设备,然后需要检查给定多边形是否位于其当前位置(取自GPS).

由于这是针对嵌入式设备,我无法使用大型库,而是我需要算法来自行执行检查或者是非常小的库.但我似乎无法找到任何这样的算法.

Answer 1

这是我在C#中为包含顶点列表的Polygon类编写的实现.它不考虑地球的曲率.相反,您可以在运行此多边形之前将多边形预处理为较小的段.

该算法的性能非常好.即使对于具有数千个边缘的多边形,它也会在我的桌面上大约一到两毫秒内完成.

代码已经过相当优化,所以不像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"位置.然后你会发现它们中有多少与在你的点之上延伸的垂直线相交.如果偶数穿过该点,那么您就在多边形之外.如果一个奇数跨过,那么你就在里面.

Answer 2

很好的解释和简单的C代码,您可以转换为您的需求

http://alienryderflex.com/polygon/

如果有许多非重叠多边形,则将多边形检查与RTree组合以快速剔除搜索树.