[發明專利]一種基于測繪信息的高精度道路最短路徑計算方法

有效

• 申請號: 202110752162.0
• 申請日: 2021-07-03
• 公開（公告）號: CN113447039B
• 公開（公告）日: 2022-06-21
• 發明（設計）人: 胡亞清;顧善植;藍丹;吳瑤;王聰睿;殷悅;王明興;楊石夢
• 申請（專利權）人: 湖南匯視威智能科技有限公司
• 主分類號: G01C21/34
• 分類號: G01C21/34;G01C21/20
• 代理公司: 深圳中一聯合知識產權代理有限公司 44414
• 代理人: 李艷麗

1.一種基于測繪信息的高精度道路最短路徑計算方法，其特征在于，包括以下步驟：

第一步，根據道路兩側的測繪數據對道路兩側分別進行曲線擬合，得到道路的邊緣曲線，將兩曲線端點閉合，形成封閉的道路曲面邊緣；

第二步，在曲面邊緣形成的封閉曲線上連續取點，取樣時保持點距離小于10cm，該間隔可以確保可以在公分級的網格模型中形成封閉區域；

第三步，對邊緣的取樣點，在x、y平面進行投影，將三維點轉化為二維，即去除高度坐標，可以證明這一操作不會對最終的最短路徑計算結果產生影響，這是由于道路的側傾角度一般較小，因而對三維曲面空間中的最短路徑而言，其在二維空間的投影與直接在二維空間進行最短路徑規劃所得到的最短路徑是重合的；

第四步，對投影后得到的區域進行公分級的網格化建模，具體實施流程如下：

S4.1).構造一個包含了道路投影區域的矩形區域，對矩形區域進行分割，得到公分級的網格劃分，并用同樣大小的矩陣表示各個網格的可通行狀況，矩陣初始值為0，表示不可通行；

S4.2).對第三步得到的離散點在網格內進行映射，對每個點，找到其所在的網格，將該網格對應的矩陣值修改為2；

S4.3).對步驟S4.2中形成的封閉區域進行填充，將該區域內的矩陣值置為1，標識為可通行區域；

第五步，對第四步中生成的可通行矩陣，應用針對平滑無障礙曲面提出的基于Dijkstra算法改造形成的最短路徑規劃算法，獲取在可通行區域內的最短路徑，具體實施流程如下：

S5.1).在矩陣可通行區域的兩端各取一個點，作為最短路徑規劃的起點s和終點e；

S5.2).構造兩列表V、U，初始化時V中僅包含起點s，U中始終維護當前所有可通行矩陣節點與s之間的距離，未探索時距離為無窮大；

S5.3).從U中遍歷探索與V中節點相鄰的節點，對被探索的節點而言，先計算其與相鄰節點的距離，計算距離時使用矩陣坐標計算其歐氏距離，若探索節點的值為0則表示不可通行，此時距離為無窮大，并加上參與計算的相鄰點自身記錄的距離值，在存在多個相鄰點的情況下，記錄其中的最小值作為被探索節點的距離值；

不同于傳統Dijkstra算法，此處若被探索節點的值在第四步中設為了2，則還需在歐氏距離計算結果上減去一個極小值0.0001；

S5.4).遍歷列表U中的節點，將擁有最小距離值的節點取出并加入到列表V中，并記錄其上一個相鄰節點；

S5.5).若終點e還未加入節點V則繼續重復步驟S5.3、S5.4，直到將終點e加入，并記錄節點s到e的節點路徑，該路徑即為最短路徑；

第六步，根據最短網格路徑，計算相應的實際最短路徑，具體實施步驟如下：

S6.1).根據網格值對第五步中的最短路徑進行分段，每一段上的網格值全為1或全為2，且相鄰段之間的網格值不相等，網格值為1的段為邊緣段，邊緣段即表示路徑與道路邊緣重合，網格值為2的段為跳躍段，跳躍段是從一條邊緣離開到再次進入一條邊緣的過程，在平滑曲面內，跳躍段在水平投影上必然是一條直線；

S6.2).對S6.1中所有邊緣段，根據S4.2中的映射方法，找到網格對應的邊緣點，重新將網格路徑變換為曲線路徑上的點，恢復其高度坐標即可再次映射至3維邊緣曲線中，對該空間曲線進行插值微分求和即可得到邊緣段的長度；對S6.1中所有跳躍段，由于本質是從邊緣離開并重新回到邊緣的一條直線，直線上任意點的x、y坐標均可根據其在邊緣上的端點坐標通過線性插值得到，而高度坐標可利用該點兩側邊緣的高度使用等比公式得到，進而同樣使用插值微分的方法計算得到其空間長度；

S6.3)對所有邊緣段和跳躍段求和即可得到最短路徑長度。