合并空间上接近的路径/线段的算法

Question

我正在寻找用于街道 map 制图概括的几何算法(的名称)。

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

例如，考虑以下使用 OpenStreetMaps 数据创建的道路/车道图:

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

map 渲染器中使用哪些既定算法来实现这一点？显然，谷歌地图、OSM 等是这样做的——怎么做的？

Answer 1

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

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

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

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}