對於iPhone地圖應用程序，我該如何創建圖表？

Question

我想製作一個應用程序，基本上就是谷歌地圖的室內場所，如商場或機場。我知道我必須從平面佈局圖創建一個圖形，並使用最短路徑查找算法來繪製從一個位置到另一個位置的最短路線。 我如何將圖形表示爲商場或機場？我是否將每個商店或大門作爲節點和走道作爲邊緣？或者我必須更具體一些，比如每隔5-10英尺做一個節點？我需要做些什麼以及我應該做什麼節點和邊緣？

Answer 1

我建議將平面圖看作網格，其中每個網格代表x平方米。在位於可訪問區域內的每個單元上放置一個節點。邊緣位於每個相鄰單元之間，並且全部具有成本x。

這種方法的優點是，你可以有效地將它放在內存中（你可以把它放在矩陣中，而不必使用adiecency list或類似的東西）。對於尋路，你可以使用一個簡單的A *實現，它使用兩點之間的歐幾里得距離作爲啓發式。

Answer 2

這裏有幾個你想解決的問題。首先是兩地之間的結構關係，其次是幾何結構。最短路徑部分取決於幾何結構，部分取決於結構。例如。一條途徑不一定是直線。對於這個結構，你可以將商場的商店和大門表示爲節點，將路徑表示爲邊緣。將節點之間的實際距離作爲邊的「權重」，並使用Dijstra's algorihtm來查找最短路徑。

如果您只是需要像「轉到A，然後轉到B」那樣在文本上顯示結果，或者在地鐵（地下）風格的拓撲地圖上，這很好。但是，如果您想要以幾何精確的地面圖形顯示結果，則需要使結構和幾何體之間的連接更加牢固。我建議你增加上面描述的結構，在路徑轉彎處添加節點，並用x，y座標標記節點，以及是否爲中間節點的布爾值。只能選擇真正的節點作爲源和目的地，但將整個圖用於Dijkstra。在屏幕上繪製結果時，在最短路徑上遍歷節點，並使用它們的座標繪製從源到目標的分段直線。