随机图中的测地线实时寻路方法（插曲）

本文可以作为本系列的一个小插曲，为后续分析打下一个算法的基础。尝试引入 Delaunay算法，使用算法从大量的地块中心中提炼出它们之间的拓扑关系。这些信息可以用于进行“测地线”距离的计算，而测地线用于在较复杂的连通图中进行自动寻路。随机场景下自动寻路的开源代码可见我的前端笔记本

Path finder in random graph^[1]

---

• 随机图中的测地线实时寻路方法（插曲）^[2]

  • 随机地理图中的邻居节点算法^[3]
  • 随机图的“测地线”寻路方法验证^[4]

    • 寻路结果演示^[5]

随机地理图中的邻居节点算法

在本系列的数据集中，我们面临的问题是得到了大量的地块节点，我们已知这些地块的中心点和多边形边界，但未知它们之间的拓扑结构，这导致这些节点之间的邻居关系不那么显然。因此需要引入一些额外的算法，使用算法从大量的地块中心中提炼出它们之间的拓扑关系。

简单来说，我们将这些地块看作是一个“图”中的无数节点，将地块之间的物理距离看作是节点之间的“边”的长度度量，该算法从图的角度对该图进行简化，简化的结果是求出每个节点的三角包络，并且能够识别出每个节点的邻居。另外，这个过程需要相当快，才能处理本系列中的较大规模数据。

因此，我们选择 Delaunay 算法来实现以上功能，该算法的细节如下图所示。

Delaunay triangulation^[6]

随机图的“测地线”寻路方法验证

为了验证算法的有效性，我使用之前文章中曾经用到的美国 Walmarts 店铺的分布数据，将各个店铺作为图的节点进行 delaunay 计算。虽然验证结果是成功的，但我无意仅满足于此，因为图的近邻拓扑信息可以用于进行“测地线”距离的计算。从下图的例子中不难看到，简单的测地线计算就像是“跳棋”一样，从原始节点向目标节点，经过图中的边进行“跳动”，而经过的最短路径就是测地线长度。当然，测地线可以用于在较复杂的连通图中进行自动寻路，（请不要问我什么叫“连通图”，因为在本文中不讲）。

Graph Geodesic -- from Wolfram MathWorld^[7]

Geodesic^[8]

寻路结果演示

接下来，我提供了测地线寻路的效果演示。下图中每个点代表地理数据得到的节点，而节点的颜色代表它与目标点之间的距离远近，（本段的距离指测地线距离）。其中，原始节点是用绿色圈圈出的节点，目标节点就是用红圈圈出的点，红色线代表原始节点到目标节点的最短路径。除了原始节点之外，其他绿色标记的节点是原始节点的“等势面”。另外，图中黑色方框圈出的区域是用户随机输入的“禁止进入的区域”，这些区域是用于验证寻路算法的正确性。从距离分布图中可以看到，人为禁区的设立会大大提高其附近节点的距离成本。

Path finder in random graph^[9]

以上代码在前端使用 Javascript 进行计算时，可以以 70 毫秒的速度完成 3000 条记录的计算，这几乎保证了寻路过程的计算是实时的。

【视频演示】

参考资料

[1]

Path finder in random graph: https://observablehq.com/@listenzcc/path-finder-in-random-graph

[2]

随机图中的测地线实时寻路方法（插曲）: #随机图中的测地线实时寻路方法插曲

[3]

随机地理图中的邻居节点算法: #随机地理图中的邻居节点算法

[4]

随机图的“测地线”寻路方法验证: #随机图的测地线寻路方法验证

[5]

寻路结果演示: #寻路结果演示

[6]

Delaunay triangulation: https://en.wikipedia.org/wiki/Delaunay_triangulation

[7]

Graph Geodesic -- from Wolfram MathWorld: https://mathworld.wolfram.com/GraphGeodesic.html

[8]

Geodesic: https://en.wikipedia.org/wiki/Geodesic

[9]

Path finder in random graph: https://observablehq.com/@listenzcc/path-finder-in-random-graph