math - 使用 OpenStreetMap 数据的路由引擎

Question

作为我学术项目的一部分，我必须根据 OSM 提供的数据构建一个路由引擎。我已经查看了 OSM 的数据模型，我对它很好。但是，我无法将 OSM XML 文件转换为可用于应用搜索算法（Dijkstra、A* 等）的图形结构（节点和边）。我希望将图形存储在内存中以允许快速读/写。

因此，任何人都可以阐明或建议如何做到这一点的技术，甚至可以为进一步研究提供指导。

请注意，我不允许重复使用现有的路由引擎，因为这会破坏执行该项目的目的。

score 4 · Accepted Answer

您需要做的就是：

为每个<node>项目创建一个节点
每个<way>条目都是一个有序的<nd>项目列表，每个项目都是一个节点的反向引用。因此，对于 each <way>，您可以成对地遍历其<nd>s 并在引用的两个节点之间创建一条弧线。

您可以使用流式 XML 解析器一次性完成此操作，因为 XML 数据在路径之前定义了所有节点。

数据本质上不包括距离，因此您需要根据每个节点的纬度计算距离。您还应该在路由中考虑道路类型highway=*（access=*waterway=stream

1 回答 1