[發明專利]一種面向復雜地表空間的行人步行導航路徑規劃方法

有效

• 申請號: 201910448974.9
• 申請日: 2019-05-28
• 公開（公告）號: CN110132260B
• 公開（公告）日: 2022-06-07
• 發明（設計）人: 王結臣;張文涵;遲瑤;錢天陸;盛彩英
• 申請（專利權）人: 南京大學
• 主分類號: G01C21/00
• 分類號: G01C21/00
• 代理公司: 南京同澤專利事務所(特殊普通合伙) 32245
• 代理人: 蔡晶晶

1.一種面向復雜地表空間的行人步行導航路徑規劃方法，包括以下步驟：

第一步：建立通行代價表——針對路徑優選時的不同情況，建立包括ID號、行人類型、地表類型、地形坡度和通行代價六項在內的通行代價表；所述行人類型包括成人、老弱、兒童；地表類型分為：平地、道路、草地、河流、建筑物；地形坡度的范圍在-90°~90°之間；通行代價則包括通過每公里所花費的時間和/或體力；

第二步：建立不規則三角網——根據導航數據對地表多邊形單元的邊界進行采樣生成離散點，并加入通行路徑的起始點和終止點，構成平面點集；基于平面點集生成不規則三角網；

第三步：計算不規則三角網各邊的通行代價——結合土地利用類型、DEM數據和通行代價表，獲取三角網各邊的地表類型、地形坡度，從而獲得三角網各邊的通行代價；三角網各邊的地表類型、地形坡度通行代價獲取方法具體如下：

地表類型：將土地利用類型數據與生成的三角網進行疊置，找出每條邊的中點像元及其八鄰域像元所屬地表類型，如果九個像元的地表類型都相同，則該邊為該地表類型；如果九個像元的地表類型不相同，則將該邊歸為這九個像元的地表類型種通行性較高的那類地表類型；

地形坡度：利用DEM數據與不規則三角網進行疊置，確定每條邊的兩個端點的高程值，并計算每條邊兩個端點的水平距離，通過每條邊兩個端點的高程差和水平距離確定每條邊的地形坡度；

通行代價：結合三角網各邊的地表類型和地形坡度，通過查詢通行代價表，確定用戶指定行人類型下的三角網各邊的通行代價，所述用戶指定行人類型由用戶選擇；

第四步：計算最優路徑——根據第二步中的起始點和終止點，結合三角網各邊的通行代價，計算最優路徑。

2.根據權利要求1所述的一種面向復雜地表空間的行人步行導航路徑規劃方法，其特征在于：所述第一步中，對于行人類型、地表類型、地形坡度的各種組合分別建立對應的通行代價表，使用數字代碼代表通行代價表中的行人類型、地表類型、地形坡度和通行代價，以簡化通行代價表。

3.根據權利要求1所述的一種面向復雜地表空間的行人步行導航路徑規劃方法，其特征在于：所述第二步中，利用并行自適應細分方法將所述平面點集劃分為若干沿x軸和y軸交替的互不重疊、點數大致相同的子集，分別針對各子集中的點建立不規則三角網并進行拼接，進而完成不規則三角網的構建。

4.根據權利要求3所述的一種面向復雜地表空間的行人步行導航路徑規劃方法，其特征在于：所述第二步中，利用Guibas-Stolfi分治算法在各子集中并行地建立Delaunay三角形。

5.根據權利要求1所述的一種面向復雜地表空間的行人步行導航路徑規劃方法，其特征在于：第二步中，根據導航數據對地表多邊形單元的邊界進行密集采樣生成離散點集，所述進行密集采樣的最小距離設置為1m，最大距離設置為5m。

6.根據權利要求1所述的一種面向復雜地表空間的行人步行導航路徑規劃方法，其特征在于：第四步中，利用相鄰節點低值傳遞方法計算最優路徑。

7.根據權利要求1所述的一種面向復雜地表空間的行人步行導航路徑規劃方法，其特征在于：初次完成第四步后，得到了初始最優路徑，在初始最優路徑所涉的不規則三角形內部進行網點加密，對加密后的網點生成不規則三角網，并重復所述第三步和第四步，得到優化的最優路徑。

8.根據權利要求1所述的一種面向復雜地表空間的行人步行導航路徑規劃方法，其特征在于：所述導航數據是由地圖數據軟件提供。