12

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

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

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

道路网络图，由几乎平行地穿过图像的三条水平线和在中间与它们相交的一条垂直线组成

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

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

4

3 回答 3

3

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

您可以使用 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}
于 2019-10-16T00:49:44.867 回答
2

这不是它的用途，但是做一些像霍夫变换这样的事情怎么样？

要找到足够接近的路径：

  1. 将线段转换为霍夫空间（r，θ），
  2. 让每个点投票给它最近的可用“bin”。您可以根据您希望合并两条路径的容差来确定 bin 量化。
  3. 累加器中的每个点还应保留对其父路径的引用，以及线段的长度。
  4. 找到恰好包含两个投票的 bin，因为我们只对合并两条路径感兴趣
  5. 创建一个 nxn 累加器矩阵A，其中 n 是您拥有的路径数，这样 a ij是合并第 i 条和第 j 条路径的投票，这将是一个大部分稀疏矩阵。
  6. 对于我们感兴趣的每个 bin，在对应于其两个父路径的单元格中的累加器矩阵中投票。
  7. 如果累加器矩阵中存在具有足够多投票数的单元格（即，算法认为这些路径中有足够数量的线段相当相似），则可以合并这两条路径。

合并两条路径：

  1. 将所选 bin 中的点转换回笛卡尔空间，使用长度（保留参考）、斜率和位置来定义与每个 bin 对应的每个线段。
于 2019-10-13T11:18:37.850 回答
0

A要找到 path和 path之间的距离B：

  • X路径上的给定点A
  • 定义与点和下一点Y之间的线成 90 度的线。X
  • 计算线Y与路径中的一条线的交点B
  • 计算点X和交点之间的距离，得到点路径之间的空间X。

要在两条路径之间创建路径：

  • 上述方法将有助于找到距离。
  • 新路径将是两条路径之间的中间距离。
于 2019-10-13T09:46:59.733 回答