上图显示了 3 个元素:
- 输入图 - 根据一个国家/地区的 OSM 数据创建。
- 过程 - 将输入图转换为输出图
- 输出图 - 输入图的更简单版本，每条道路上没有详细节点。它仅包含根据输入图道路计算的城市/村庄节点和边。
我想从输入图创建输出图。换句话说，我需要一个图表来让我快速计算出这个问题的答案:如果我从城市 3 开车到城市 7，我会经过哪个城市/村庄？ 在这个例子中，答案是:
- 您将经过城市/村庄:5、6、7
- 您将经过城市/村庄:2、4、6、7
- 您将经过城市/村庄:5、4、6、7
城市/村庄节点是从 OSM 文件中检索的。输出图边应具有基于输入图边计算的权重。权重是从一个节点到下一个节点的距离(以米为单位)。
在原始 OSM 数据文件(和输入图中)中，描述城市或村庄的节点未与道路边相连。我所看到的是，我必须处理此图，仅获取代表城市和村庄的节点，然后尝试匹配(基于从城市/村庄节点到道路节点的距离)并制作一些仅连接城市/村庄节点的捷径。
我的问题是:
- 这已经完成了吗？我不想重复别人的工作。
- 您将如何创建输出图？
最佳答案
您可以根据路由算法找到一条路径。有几个软件实现，比如 osmand。 然后，在 OSM 数据中，不要寻找代表城市的节点，而是寻找城市的行政边界(多边形)。 此时，使用经典的几何算法，您可以计算路线与行政边界之间的交叉点列表。
此方法可以解决您的问题，但不会将简化图计算为中间步骤。因此，每个请求的计算 secret 集度更高。
恐怕在一张由道路构成的图表中，两点之间有大量不同的路径，可能以各种顺序穿过数据中的所有城市。所以你需要一些优化标准来选择少量路径(短距离、短旅行时间、不收费、风景优美的道路等)。这导致需要一些路由算法，这就导致了上面的解决方案...
关于algorithm - 处理 OSM 数据图的想法，用于输出简单的城市/村庄节点，它们之间有边，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9964380/