检查经度/纬度坐标是否位于嵌入式设备的复杂多边形内? [英] 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.

我只能找到使用不补偿地球曲率的简单 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# 为包含顶点列表的 Polygon 类编写的实现.它不考虑地球的曲率.相反，您会在运行之前将多边形预处理成更小的部分.

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

基本思想是找到跨越您要测试的点的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.

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