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

Question

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

algorithmmathembeddedgeometrygis

20

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

我只能找到使用简单的x/y笛卡尔坐标系算法，这些算法没有考虑到地球的曲率。

用户在PC上绘制多边形，然后将点通过无线电传输到嵌入式设备，然后需要检查给定多边形是否位于当前位置（从GPS获取）。

由于这是针对嵌入式设备的，我不能使用庞大的库，而是需要自己执行检查的算法或者一个非常小的库。但是我似乎找不到这样的算法。

- ChewToy

2

你需要考虑的是什么距离？我经常从事这种工作，如果你说的是相对较小的多边形，比如<1000米，那么这些简单的算法就可以很好地适应标准GPS的精度。在较短的距离内，地球曲率的影响不大。 - PeterJ

请注意，如果您正在处理GIS相关的工作，您可能会喜欢这个与SO相关的网站：http://gis.stackexchange.com/ - Drew Noakes

@PeterJ 我打算在非常广阔的范围内（数百公里）使用它，但仍需要非常精确，因为它也将用于小于1公里的分段区域。 - ChewToy

好的，但请记住，除非各个片段之间相距很远，否则这并不会产生影响。例如，一条200公里长的高速公路，其中一系列片段相距几公里，不会有太大的影响。只有当您拥有一个100公里长的多边形边缘时，它才会真正产生影响，而这在我的经验中相当罕见。大多数现实生活中的事物，比如城市边界，在实践中都不太直，所以值得考虑可能的误差和是否真正需要这些。如果您确实需要这种精度，那么在高速公路上行驶时，您可能还需要一些死算测量。 - PeterJ

2个回答

7

良好的解释以及可以根据您的需要转换为简单C代码 http://alienryderflex.com/polygon/ 如果有许多不重叠的多边形，请将多边形检查与RTree结合起来，以便快速修剪搜索树。

- Niclas Lindgren

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Drew Noakes · Accepted Answer

这是我用C#编写的多边形类的实现，其中包含了一个顶点列表。它没有考虑地球的曲率。相反，在运行此程序之前，您需要对多边形进行预处理，将其分成较小的线段。

该算法的性能非常好。即使对于具有数千个边的多边形，在我的台式机上也可以在大约一到两毫秒内完成。

这段代码已经被优化过了，因此不像伪代码那么易读。

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”位置的多边形的所有边。然后找出有多少条线交叉垂直于穿过您的点上方的竖直线。如果偶数条线穿过该点，则在多边形外部。如果奇数条线穿过该点，则在内部。