[發明專利]一種車載機自主導航方法

有效

• 申請號: 200910311010.6
• 申請日: 2009-12-07
• 公開（公告）號: CN102087113A
• 公開（公告）日: 2011-06-08
• 發明（設計）人: 黃思志;楊一麟;劉輝;時宜
• 申請（專利權）人: 廈門雅迅網絡股份有限公司
• 主分類號: G01C21/34
• 分類號: G01C21/34;G06F17/30
• 代理公司: 廈門市首創君合專利事務所有限公司 35204
• 代理人: 潘國慶;李雁翔

1.一種車載機自主導航方法，包含：

步驟A，將全國范圍的電子地圖按相同大小的矩形分割成順序編號的網格；對每一網格內的道路弧、道路弧的轉向元素、道路邊和道路邊上的點重新編號，逐一生成對應網格的基礎數據表；對于所有網格逐一用本網格的基礎數據表建立本網格內每一條入弧到所有出弧的轉向元素，計算出本網格內每一條入弧到所有出弧的最短路徑的長度，將本網格內每一條入弧到所有出弧的轉向元素及所述最短路徑的長度記錄到本網格的簡化數據表；

步驟B，將所有網格的基礎數據表和簡化數據表下載到車載機；

步驟C，確z起點和終點所在的道路弧，及起點道路弧和終點道路弧所在的網格；

步驟D，規劃出由起點網格內和終點網格內按對應基礎數據表導出的最短路徑、所有中間網格內按對應簡化數據表導出的簡化最短路徑組成的簡化路徑；

步驟E，按簡化路徑導航；其中，每當進入一個網格時將下一個中間網格的簡化最短路徑轉化為按基礎數據導出的該網格內的最短路徑，供進入下一個中間網格時導航用。

2.根據權利要求1所述的一種車載機自主導航方法，其特征在于：所述的步驟A中，具體將全國范圍的電子地圖按相同大小的矩形分割成順序編號的網格；并對每一網格內的道路弧、道路弧的轉向元素、道路邊和道路邊上的點重新編號，逐一生成對應網格的基礎數據表的處理，包含以下的子步驟：

子步驟A1，加載全國電子地圖的地圖源數據，按照規定的網格大小，對上述地圖源數據進行切割并順序編號；計算出每個網格所覆蓋的道路弧、每一道路弧的所有轉向元素、每一道路弧所對應的道路邊和每一道路邊上所有的點，對于每個穿越網格邊界的道路邊、道路弧等分別切分，并在切分后的道路弧元素間生成新的轉向元素；

子步驟A2，按網格編號，順序在每一個網格內對本網格內的道路弧、每一道路弧的所有轉向元素、每一道路弧所對應的道路邊和每一道路邊上所有的點分別重新編號；依據上述地圖源數據的拓撲關系，在每一網格內及其相鄰網格間對重新編號的道路弧、每一道路弧的所有轉向元素、每一道路弧所對應的道路邊和每一道路邊上所有的點按新的編號建立拓撲關系；把每一網格內的道路弧、每一道路弧的所有轉向元素、每一道路弧所對應的道路邊和每一道路邊上所有的點，按照新的編號順序寫入本網格的基礎數據表。

3.根據權利要求1所述的一種車載機自主導航方法，其特征在于：所述的步驟D中，具體規劃出由起點網格內和終點網格內按對應基礎數據表導出的最短路徑、所有中間網格內按對應簡化數據表導出的簡化最短路徑組成的簡化路徑的處理，包含以下的子步驟：

子步驟D1，用起點道路弧所連接的轉向元素查找出所有可達的下一條道路弧，將起點道路弧作為這些道路弧的前趨道路弧；將這些道路弧及其前趨道路弧添加到開表中；

子步驟D2，取出開表中離起點道路弧路徑最短的道路弧作為當前道路弧，把當前道路弧及其前趨弧信息加入到閉表中；

子步驟D3，若當前道路弧在起點網格，加載起點網格基礎拓撲數據表，找到所有當前道路弧連接的轉向元素和所有可達的下一條道路弧；若當前道路弧在中間網格，加載當前道路弧所在網格的簡化數據表，找到所有當前道路弧連接的簡化轉向元素和所有可達的下一條道路弧；若當前道路弧在終點網格且不是終點道路弧，加載終點網格基礎數據表，找到所有當前道路弧連接的轉向元素和所有可達的下一條道路弧；然后執行子步驟D4；若當前道路弧是終點道路弧，執行子步驟D5；

子步驟D4，設置當前道路弧為所有可達的下一條道路弧的前趨道路弧，把找到的所有可達的下一條道路弧及其前趨道路弧加入到開表中，返回執行子步驟D2；

子步驟D5，取出閉表，把終點道路弧作為當前道路弧；

子步驟D6，把當前道路弧添加到簡化路徑弧序列開頭；

子步驟D7，判斷當前道路弧是否是起點道路弧，是則退出；否則在閉表里查找當前道路弧的前趨道路弧，將該前趨道路弧作為當前道路弧，再次執行子步驟D6，繼續回溯。

4.根據權利要求3所述的一種車載機自主導航方法，其特征在于：所述的步驟E中，按簡化路徑導航的處理，包含以下的子步驟：

子步驟E1，由簡化路徑弧序列的起點道路弧開始，置起點道路弧為當前道路弧；

子步驟E2，判斷當前道路弧是否是終點道路弧，是則退出；否則由簡化路徑弧序列取出下一條道路弧；

子步驟E3，若下一條道路弧不是跨網格的弧，或者當前道路弧在起點網格或終點網格內，則進行起點網格或終點網格內的導航顯示的擴展；否則進行中間網格的路徑擴展，加載當前道路弧所在網格的基礎數據表，以本網格當前道路弧對應的入弧為起點道路弧，下一條道路弧對應的出弧為終點道路弧，依據本網格的基礎數據表，利用dijkstra算法，計算出本網格內基礎數據表示的最短路徑道路弧序列，把計算出來的道路弧序列，插入到當前道路弧與下一條道路弧之間。計算出來的最短道路弧序列擴展了簡化路徑中間網格的當前道路弧到跨網格的下一條道路弧之間的真實道路弧序列；

子步驟E4，生成當前道路弧與下一個道路弧之間的詳細導航顯示信息，進行導航；把下一條道路弧置為當前道路弧，返回執行子步驟E2，繼續向終點道路弧行進。