首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >检查经度/纬度坐标是否驻留在嵌入式设备中的复杂多边形中?

检查经度/纬度坐标是否驻留在嵌入式设备中的复杂多边形中?
EN

Stack Overflow用户
提问于 2012-12-19 18:17:37
回答 2查看 24.3K关注 0票数 18

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

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

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

因为这是针对嵌入式设备的,所以我不能使用大型的库,而是需要算法来执行自己的检查或一个非常小的库。但我似乎找不到任何这样的算法。

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2012-12-19 19:13:31

这是我用C#为一个包含顶点列表的Polygon类编写的实现。它没有考虑地球的曲率。相反,您应该在运行此操作之前将多边形预处理为较小的段。

该算法具有很好的性能。即使是有数千条边的多边形,它在我的桌面上也只需一到两毫秒就能完成。

代码已经过了相当多的优化,所以可读性不如psuedo-code。

代码语言:javascript
运行
复制
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”位置。然后你会发现他们中有多少人与延伸到你的点之上的垂直线相交。如果一个偶数在点上交叉,那么你就在多边形之外。如果奇数在上面交叉,那么你就在里面。

票数 16
EN

Stack Overflow用户

发布于 2014-07-21 23:27:23

很好的解释和简单的C代码,可以根据需要进行转换

http://alienryderflex.com/polygon/

如果有许多不重叠的多边形,请将多边形检查与RTree相结合,以便快速剔除搜索树。

票数 7
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/13950062

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档