[發明專利]一種面向虛擬地球的最短路徑分層規劃方法

有效

• 申請號: 201710218708.8
• 申請日: 2017-04-05
• 公開（公告）號: CN107092978B
• 公開（公告）日: 2020-11-03
• 發明（設計）人: 陳靜;董全華;劉婷婷;毛天陽
• 申請（專利權）人: 武漢大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 嚴彥

1.一種面向虛擬地球的最短路徑分層規劃方法，其特征在于：包括面向虛擬地球的道路網預處理過程和面向虛擬地球的最短路徑分層規劃過程，

所述面向虛擬地球的道路網預處理過程包括以下步驟，

步驟1.1，面向虛擬地球的路網數據分層分塊組織，包括基于比例尺的方式，將大比例尺路網放置在金字塔的下層，小比例尺路網放置在金字塔的上層；采用等經緯度格網進行路網的分塊劃分，首先獲取整個矢量道路網數據的經緯度范圍，然后計算出在全球經緯度格網中的行列號范圍，如果道路要素跨越多個格網，則記錄與格網邊界的交點，將交點稱為格網點，并按格網點所在格網邊界的位置分為上下左右四類；

步驟1.2，上層瓦片局部最短路徑預存，包括計算上層瓦片中各個格網點之間的最短路徑，形成一條新的格網點之間的弧段，稱為格網弧段，然后存儲格網弧段的起止格網點、長度和坐標點數據；

所述面向虛擬地球的最短路徑分層規劃過程包括以下步驟，

步驟2.1，在分層路網的上層確定入點和出點，實現方式如下，

首先確定路徑規劃中起止點對的分布情況，如果起止點的經度差大于緯度差，則為橫向分布；如果起止點的緯度差大于經度差，則為縱向分布；

如果起止點為橫向分布，則在起止點鄰列格網的左格網點集合或者右格網點集合中選取出入點，鄰列的行范圍由起止點所在行確定；如果起止點為縱向分布，則在起止點鄰行格網的上格網點集合或者下格網點集合中選取出入點，鄰行的列范圍由起止點所在列確定；

確定出入點的選擇范圍之后，分別比較起點與入點選擇范圍中的點的連線與直線的夾角，終點與出點選擇范圍中點的連線與直線的夾角，選擇構成夾角最小的點作為出入點；

步驟2.2，在上層路網中獲取入點和出點之間的最短路徑，實現方式如下：

所述上層路網中入點和出點之間最短路徑的計算采用改進的Dijkstra算法實現，包括節點分區時采用一維線性數組存儲所有的結點，數組的長度根據結點的個數確定，數組中分別開辟三個連續的存儲空間分別存儲O集合、U集合以及S集合中的結點，O、U、S集合分別代表未標記、標記和選中點集；三個集合的排列順序為O集合在最前面，U集合在最中間，S集合在最后，保證結點在兩個集合之間的移動只涉及兩個結點，而其他的結點保持不變；

步驟2.3，在下層中確定入點和出點對應的格網點，實現方式如下：

根據入點或出點的坐標計算出在下層中的瓦片編碼，得到在下層中的瓦片位置和瓦片中的格網點集合，然后分別從上、下、左、右四個格網點集合中選取對應的集合進行比較，選取坐標偏差最小的格網點作為入點和出點在下層中的對應點， 所述坐標偏差是由于上下兩層的道路網數據來源不同，同一個點在兩層中所表達的位置有稍許偏差，不能做到完全的精確匹配；

步驟2.4，在下層路網中獲取起點和入點之間、出點和終點之間的最短路徑，將上下兩層中的最短路徑連接起來，作為最終的最優路徑輸出。