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

Question

我正在寻找一种用于街道地图制图概括的几何算法（名称）。

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

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

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

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

标签： algorithmgraphicsgeometrygiscartography

Answer 1

作为研究人员，我研究过一个与此类似的问题。我关于频繁路线的论文这是关于给定一堆轨迹（以不同的时间/速度），如何对路段进行逆向工程。

您可以使用 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}