在表示为二维形状的地图中搜索最短路径
我有一个包含一些最短路径搜索算法的小型库。它们是为简单的无向图（正常表示 - 顶点和边）而开发的。现在我想以某种方式将它们应用到稍微不同的场景 - 其中地图表示为二维形状，通过共享边（即多边形的边）连接。在这种情况下，搜索可以在地图对象或某个点 (x,y) 处开始/结束。最好的方法是什么？尝试将算法应用到形状上？或者尝试从形状中提取“正常”图形（我有可用的预处理时间）？任何建议将不胜感激，因为我真的不确定该走哪条路，而且我没有足够的时间（和技能）来探索许多选择......
非常感谢
I have a small library of a few shortest path search algorithms. They were developed for simple undirected graphs (the normal representation - vertices and edges). Now I'd like to somehow apply them on a bit different scenario - where the maps are represented as 2-dimensional shapes, connected by shared edges (edges of the polygons, that is). In this scenario, the search can start/end either at a map object or some point (x,y). What would be the best approach? Try to apply the algorithms onto shapes? or try to extract a 'normal' graph out of the shapes (I have preprocessing time available)? Any advice would be much appreciated, as I'm really not sure which way to go, and I don't have enough time (and skill) to explore many options...
Thanks a lot
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您正在寻找的“路径”是什么？要遍历的形状列表？ （否则，您只需在起点和终点之间绘制一条直线。）
很容易将其预处理为一种格式，其中形状是顶点，并且当形状共享多边形边时通过边连接。然后，只需将其传递给您现有的图书馆即可获得答案。
What's the "path" you're looking for? A list of the shapes to traverse? (Otherwise you just draw a straight line between start+end points.)
It's easy to preprocess it into a format where the shapes are vertices and are connected by edges when the shapes share a polygon side. Then, just pass it off to your existing library to get the answer.