合并空间上封闭的路径/线段的算法

Question

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

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

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

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

在地图渲染器中使用哪些已建立的算法来实现此目的？显然，Google Maps，OSM等是如何做到的？

Answer 1

A要查找路径与路径之间的距离B：

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

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

• 上述方法将有助于找到距离。
• 新路径将是两条路径之间的中间距离。