map - 在表示为 2d 形状的地图中的最短路径搜索

Question

我有一个包含一些最短路径搜索算法的小型库。它们是为简单的无向图（正常表示 - 顶点和边）而开发的。现在我想以某种方式将它们应用到一个有点不同的场景中——地图被表示为二维形状，由共享边（即多边形的边）连接。在这种情况下，搜索可以在地图对象或某个点 (x,y) 开始/结束。最好的方法是什么？尝试将算法应用于形状？或尝试从形状中提取“正常”图形（我有可用的预处理时间）？任何建议将不胜感激，因为我真的不确定该走哪条路，而且我没有足够的时间（和技能）来探索许多选择......

非常感谢

Answer 1

您正在寻找的“路径”是什么？要遍历的形状列表？（否则，您只需在起点+终点之间画一条直线。）

当形状共享多边形边时，很容易将其预处理为形状为顶点并由边连接的格式。然后，只需将其传递给您现有的图书馆即可获得答案。