[發明專利]一種高效分級尋路方法、裝置、介質和設備

有效

• 申請號: 202210345629.4
• 申請日: 2022-04-02
• 公開（公告）號: CN114470776B
• 公開（公告）日: 2022-07-08
• 發明（設計）人: 張佳亮;董偉;黃正雨;李鑒
• 申請（專利權）人: 北京優锘科技有限公司
• 主分類號: A63F13/56
• 分類號: A63F13/56
• 代理公司: 北京安度修典專利代理事務所(特殊普通合伙) 11424
• 代理人: 楊方成;馬歡萍

1.一種高效分級尋路方法，其特征在于，所述方法包括：

基于數據源提供的路徑點序列和德洛內三角化算法，生成標準尋路網格數據；

遍歷數據源路徑點數量M，計算M個路徑點在x,y方向上的四個極值點數據，并且將所述路徑點數量M通過開方運算得到數量閾值N，在所述路徑點序列中均勻選取N個路徑點作為宏觀路徑點，基于四個極值點數據與宏觀路徑點通過德洛內三角化算法，生成宏觀尋路網格數據；

根據Astar尋路算法在所述宏觀尋路網格數據上計算得到初步宏觀尋路路徑數據，所述初步宏觀尋路路徑數據為從起始查詢點與目標查詢點之間的路徑數據；

對所述初步宏觀尋路路徑數據進行處理得到最終宏觀尋路路徑數據；

根據所述最終宏觀尋路路徑數據，結合所述標準尋路網格數據，分段進行微觀標準尋路；

合并分段微觀標準尋路結果，得到最終標準尋路路徑數據。

2.根據權利要求1所述的高效分級尋路方法，其特征在于，基于數據源提供的路徑點序列和德洛內三角化算法，生成標準尋路網格數據，具體包括：

將所述數據源提供的路徑點序列輸入至德洛內三角化算法中，得到所述尋路網格數據；

其中，所述尋路網格數據包括三角網序列Mesh，所述三角網序列Mesh中包括多個三角形Triangle，所述三角形的三個頂點分別對應三個路徑點。

3.根據權利要求2所述的高效分級尋路方法，其特征在于，所述根據Astar尋路算法在所述宏觀尋路網格數據上計算得到從起始查詢點與目標查詢點之間的初步宏觀尋路路徑數據，具體包括：

根據起始查詢點位置，判斷所述起始查詢點處于所述宏觀尋路網格數據中的哪個三角形中，并計算得到所述起始查詢點距離該三角形中最近的首個路徑點；

根據目標查詢點位置，判斷所述目標查詢點處于所述宏觀尋路網格數據中的哪個三角形中，并計算得到所述目標查詢點距離該三角形中最近的末尾路徑點；

根據AStar尋路算法，在所述宏觀尋路網格數據中計算得到從所述首個路徑點到末尾路徑點之間的初步宏觀尋路路徑數據。

4.根據權利要求3所述的高效分級尋路方法，其特征在于，所述對所述初步宏觀尋路路徑數據進行處理得到最終宏觀尋路路徑數據，具體包括：

分析判斷所述首個路徑點與所述宏觀尋路路徑數據中的第二個路徑點是否屬于同一三角形，如果屬于同一三角形則舍棄所述首個路徑點；

分析判斷所述末尾路徑點與所述宏觀尋路路徑數據中的倒數第二個路徑點是否屬于同一三角形，如果屬于同一三角形則舍棄所述末尾路徑點；

獲取分析處理后的最終宏觀尋路路徑數據。

5.根據權利要求3所述的高效分級尋路方法，其特征在于，所述根據所述最終宏觀尋路路徑數據，結合所述標準尋路網格數據，分段進行微觀標準尋路，具體包括：

對于所述最終宏觀尋路路徑數據中的多個路徑點，將相鄰兩點依次進行分組并對應進行分段，結合所述標準尋路網格數據，根據AStar尋路算法計算出每個分段之間的分段標準尋路路徑數據，即；

根據AStar尋路算法計算出所述起始查詢點與所述首個路徑點之間的首段標準尋路路徑數據；

根據AStar尋路算法計算出所述末尾路徑點與所述目標查詢點之間的末段標準尋路路徑數據。

6.根據權利要求5所述的高效分級尋路方法，其特征在于，所述合并分段微觀標準尋路結果，得到最終標準尋路路徑數據，具體包括：

獲取所述分段標準尋路路徑數據、首段標準尋路路徑數據與末段標準尋路路徑數據；

按照首段標準尋路路徑數據、分段標準尋路路徑數據與末段標準尋路路徑數據順序進行合并處理，得到最終標準尋路路徑數據。