我想为商场或机场等室内场所制作一个基本上是谷歌地图的应用程序。我知道我必须从平面图创建一个图表并使用最短路径查找算法来绘制从一个位置到另一个位置的最短路径。如何将商场或机场表示为图表？我是否将每个商店或大门或其他东西作为节点，将人行道作为边缘？还是我必须更具体，例如每 5-10 英尺制作一个节点？我需要具体到什么程度？我应该如何制作节点和边？
问问题
309 次
2 回答
0
我建议将平面图视为一个网格，其中每个单元格代表x平方米。在可访问区域内的每个单元格上放置一个节点。边缘位于每个相邻单元之间，并且都具有x成本。
这种方法的优点是您可以有效地将其放置在内存中（您可以将其放入矩阵中，而不必使用 adiecency 列表等）。对于寻路，您可以使用简单的 A* 实现，该实现使用两点之间的欧几里得距离作为启发式。
于 2012-05-27T20:41:32.410 回答
0
您想在这里解决几个不同的问题。一是两地之间的结构关系，二是几何关系。最短路径部分取决于几何形状，部分取决于结构。例如。路径不一定是直线。对于该结构，您可以将商场商店和大门表示为节点，将路径表示为边。将节点之间的实际距离作为边缘的“权重”，并使用Dijstra 的算法找到最短路径。
如果您只需要以文本形式呈现结果，例如“转到 A，然后转到 B”，或者在地铁（地下）样式的拓扑图上，这很好。但是，如果您想在地板的几何精确表示上显示结果，则需要使结构和几何之间的连接更加牢固。我建议您在路径转弯的任何地方添加节点来扩充上述结构，并使用 x,y 坐标以及布尔值标记节点是否为中间节点。只选择真正的节点作为源和目标，但对 Dijkstra 使用整个图。在屏幕上绘制结果时，遍历最短路径中的节点，并使用它们的坐标绘制一条从源到目标的分段直线。
于 2012-05-27T21:25:08.350 回答