对于iPhone地图应用程序，如何创建图形？

Question

我想做一个应用程序，基本上是谷歌地图的室内场所，如商场或机场。我知道我必须从平面布置图创建一个图，并使用最短路径查找算法来绘制从一个位置到另一个位置的最短路径。如何将购物中心或机场表示为图形？我是不是把每个商店、大门或其他东西当作一个节点，把人行道当作边？或者我必须更具体，比如每5-10英尺创建一个节点？我需要具体到什么程度，我应该做什么节点和边？

Answer 1

我建议将平面图看作一个网格，其中每个单元代表x平方米。在位于可访问区域内的每个单元上放置一个节点。每个相邻单元格之间的边都有x的代价。

这种方法的优点是，您可以有效地将其放置在内存中(您可以将其放入矩阵中，而不必使用辐射列表或类似的列表)。对于寻路，您可以使用一个简单的A*实现，该实现使用两点之间的欧几里得距离作为启发式。

Answer 2

这里有几个您想要解决的不同问题。首先是两地之间的结构关系，其次是几何关系。最短路径部分取决于几何形状，部分取决于结构。例如：路径不一定是直线。对于结构，您可以将商场商店和大门表示为节点，将路径表示为边。将节点之间的实际距离作为边的“权重”，并使用Dijstra's algorihtm查找最短路径。

如果你只需要像“转到A，然后转到B”这样的文本形式来显示结果，或者在地铁(地下)样式的拓扑图上，这是很好的。但是，如果您希望以精确的几何图形表示楼板来显示结果，则需要加强结构和几何图形之间的连接。我建议你在上面描述的结构中，在路径转弯的地方添加节点，并用x，y坐标和布尔值标记节点，以确定它是否是中间节点。只选择真正的节点作为源和目标，但使用Dijkstra的整个图。在屏幕上绘制结果时，迭代最短路径中的节点，并使用它们的坐标绘制一条从源到目标的分段直线。