像Garmin和TomTom這樣的導航系統一直讓我着迷。我想要實現小型地圖/導航應用程序來嘗試各種路徑算法並擴展我對它們的瞭解。地圖導航項目，道路數據通常如何存儲/表示？
這是一個問題的兩個部分：
1）如何被存儲的地圖數據？ - 當您擁有道路網絡時，通常會如何存儲這些數據？數據的哪些部分保留以便稍後再現地圖？每條道路存儲爲一系列改變方向的點嗎？這些數據存儲在哪種文件格式？是否有公共可用的庫輕鬆解析這些文件？有沒有人有關於如何存儲/表示地圖/道路數據的細節，這將是非常有用的。
2.）導航/路徑 - 在此地圖上進行基本路徑數據（a Garmin）時，我的假設是正確的，它被轉換爲有向圖？每個道路交叉點都是頂點與邊緣之間的頂點距離嗎？這正是我想要做的，所以我可以嘗試一些基本的衆所周知的路徑算法，並看看我得到了什麼。
我見過this美國的公開地圖數據，但我不確定它是如何表示的，以及它是否足夠詳細，以便能夠從中創建我的有向圖。
如果有人有任何信息，我將不勝感激。更詳細的知識你有更好的。
我不知道導航系統單元的具體情況，但在標準GIS世界中，地圖數據基本上存儲爲多邊形，線條和點的集合，每個點都由座標（以及使用的投影和其他參數）。例如，最常見的格式之一是shapefile，描述爲here,，而基於數據庫的格式標準是here。
我已成功使用此存儲模型進行道路顯示和路線計算，使用PostgreSQL,PostGIS和PGRouting。使用通常的圖形算法進行計算，並且以通用格式存儲的數據也作爲圖形存儲以允許其應用。我不能將這種體驗外推到嵌入式設備，因爲它們的計算能力有限，因此它們可能會做得非常不同。他們很可能預先計算好多東西。
對於稍微不同的方式來存儲，檢查OpenStreetMap
爲了提高拉絲速度在多個存儲和有限的分辨率的成本，許多應用程序將使用一個地理參照柵格格式如GeoTiff。
鑑於Zich低於
相當堅持的意見「的數據是在載體在沒有異常的所有導航系統！」
我想我會添加一點到上面。首先，我將導航系統定義爲一個系統，可以幫助您根據當前位置如何到達想要去的地方，通常需要花費一些可能的替代路線並推薦最低成本的路線。可能的路線可能由交通工具決定，例如汽車停留在道路上，而山地徒步者則不行。路線的成本計算可能因運輸方式以及用戶要求而異。汽車可能希望根據道路速度採取最快的路線，卡車可能需要最節省燃料的路線，希望步行者可能需要最安全的直達路線，船隻或飛機可能需要避開危險天氣系統的路線，同時還最小化燃料成本和花費的時間。
在最簡單的層面上，地圖和指南針是一個導航系統。用小屏幕，可擴展柵格地圖和GPS替換地圖，並且您仍然有一個導航系統。大多數中低端海上導航系統仍然以這種方式工作，圖表代表海岸線和海底以及GPS給您的位置，以及迴聲探測深度。
在更高端的頻譜中，自主機器人導航系統（例如Mars Rover navigation system）即時生成DTM模型作爲短程導航的基礎，而衛星收集DEM用於更遠距離的導航。
說所有導航系統的工作就像消費者Garmin或湯姆湯姆設備是一個相當幼稚的推定。 FWIW，許多現代Garmin設備還包括raster based DEM data，其中低成本的GPS高度可能大大不準確。
存儲的確切方式取決於格式;有不同的GIS格式的堆。 GDAL是一個很好的閱讀（幾乎）所有人的免費圖書館。
通常道路將存儲在文件作爲一個「線路層」中，這是一組具有附加的元數據折線。因此，每條道路都會有一系列頂點，並且根據數據的質量，希望能夠獲得諸如單向或非單向，速度估計和某種連接標識等信息。
是的，他們通常轉換爲有向圖來解決。邊緣權重可以是距離，或者更有用的是，行進該邊緣所花費的時間。
迅速求解是預計算和存儲空間（嵌入式設備可能需要在這裏不同的選擇到PC）之間的折衷。這裏有一些非常有趣的算法。
穆罕默德：好，我沒有進入太多細節那裏，因爲原來的問題似乎在這方面很舒服。如果你對圖論不熟悉，現在做一些閱讀可能是一個好主意 - Wikipedia對引言很好。
什麼通常發生的是，在GIS數據的道路被存儲爲與連接元數據折線。在屏幕上顯示它們很好，但爲了能夠瀏覽它們，您需要知道哪些是相互連接的。因此，在元數據中，通常每條路都有一個節點ID，因此您可以說「這是路段457，它從節點332到節點667」。因此，當您讀入GIS數據時，您會將其表示爲一組通過弧線連接的節點（即圖形）。
如果該元數據是不可用，你可以推斷出它從道路具有相同的開始/結束座標（這是一些不那麼美妙的GIS數據的情況下）。 「定向」位僅僅意味着道路有方向 - 其中一些可以沿任何一個方向行駛，但另一些只能是單向的。
尋找通過有向圖的路徑的典型算法是Dijkstra算法;實踐中使用各種衍生物。基本上涉及沿着圖形的弧線從節點移動到節點，因此您需要適當的數據結構來支持該節點。
希望有幫助...
以前的回答都是指GIS系統。這不是PND（便攜式導航設備）如何工作的方式。它們太簡單了，無法運行桌面/工作級別的GIS軟件。
相反，PND存儲的信息與Simucal推測的非常相似。道路被分解成細分市場。這使模型更簡單。在一個細分市場中，像最高速度這樣的屬性不會改變。
爲了規劃目的，道路段充當圖中的邊緣。對於每個節點，傳入和傳出節點都存儲。然後使用修改的A *算法完成規劃。邊緣權重通常不是距離，而是估計的旅行時間（或在TomTom的情況下，實際的測量時間）。
雖然道路網絡通常是典型的，並且正常的A *是一個慢起動器。當從一個小鎮旅行到另一個小鎮時，A *會花費過多的時間爬過起始小鎮。但是，我們人類知道，長途旅行時最好使用高速公路。這就是他們的目標。 PND同樣喜歡高速公路。由於高速公路非常罕見，這節省了大量的內存。
另一種優化是前向和後向搜索;你計劃從雙方到一些中間點。這樣做的一大優點是，如果轉彎錯誤，您可以從新的起點再次搜索。向後搜索樹不變，因爲您的目的地沒有移動。
如果您需要查看一些代碼以瞭解路由應用程序的工作方式，請嘗試查看從openstreetmap.org wiki鏈接的一些路由應用程序。 Navit和Gosmore都是開源的，特別容易設置。
Gosmore應用程序的開發者Nic Roets寫了一個interesting post關於他的選擇來表示您可能感興趣的道路矢量數據。
如果你想看看戈斯莫爾的行動，它是基於openstreetmap數據的yournavigation.org路由網站的後端。
數據在所有導航系統中均無嚮導！ – Zich 2017-02-03 22:22:54
@Zich，瞭解所有導航系統一定是件好事。簡要介紹一下自主機器人導航，您會看到許多涉及點雲的點擊，例如http://www.robotics.unsw.edu.au/u10/Autonomous-navigation-using-a-real-time-其中GeoTIFF經常用於將可繪製地形表面表示爲點雲（即DEM）的3D點雲。這樣的系統基於從DEM（通常爲柵格）或DTM（通常基於矢量的TIN）生成簡檔來搜索最低成本的路線而不進行導航。 – 2017-02-04 09:22:48
是啊！（所有navi ...）都是這樣的，你說有些汽車使用鐵路！我說不！所有的汽車都有車輪，他們不使用鐵路方式！簡單！是的，這是一條通用規則，可以在GIS軟件中對柵格數據執行最短路徑分析（即在Arcgis中使用走廊功能），但它不是導航系統！上面的許多答案都應該肯定地投下一票，但我不能忽視你的答案。 – Zich 2017-02-04 21:20:40