空间封闭路径/线段的合并算法 [英] Algorithm for merging spatially close paths / line segments

问题描述

我正在寻找一种用于街道地图制图综合的几何算法。

在我的地图数据中，我有许多路径(有序的点列表，由线段连接)彼此靠近且几乎平行。如何(1)识别这些"相邻路径ˮ"(即如何查找比某个阈值更近的路径)和(2)将它们合并为一条路径(即如何计算闭合路径之间的中心线)？

作为示例，请考虑以下使用OpenStreetMaps中的数据创建的道路/车道图：

如您所见，水平运行的道路的两条车道被建模为两条独立的路径。对于局部视图，这很有用，但对于更缩小的视图，我需要合并两条路径(车道)，以便仅显示道路的一条线。

地图渲染器中用于实现此目的的既定算法是什么？显然，谷歌地图、OSM等都是这样做的--如何做到这一点？

推荐答案

我作为研究人员曾经研究过类似的问题。my paper on frequent route这是关于给定一系列轨迹(在不同的时间/速度)，如何对路段进行反向工程。

您可以使用Frechet Distance测量线段之间的距离，并使用该距离对线段进行聚类。对于每个簇，您可以指定一个代表性的线段。这就是解决方案的要点。

更简单的实现方式是使用以下算法：

def reduce_segments (G : graph):
    for e in G.edges: 
        if not e.mark: 
            continue
        similar_edges = get_all_edge_with_frechet_distance_less_than_thr(G.edges, thr)
        for se in similar_edges:
            se.mark = True
    return {ee : ee in G.edges and ee.mark == False}

这篇关于空间封闭路径/线段的合并算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！