[發明專利]路徑網絡圖生成方法及裝置、電子設備和存儲介質

有效

• 申請號: 202010532971.6
• 申請日: 2020-06-12
• 公開（公告）號: CN111678527B
• 公開（公告）日: 2022-04-12
• 發明（設計）人: 陳建興;潘余昌
• 申請（專利權）人: 北京京東乾石科技有限公司
• 主分類號: G01C21/32
• 分類號: G01C21/32
• 代理公司: 北京律智知識產權代理有限公司 11438
• 代理人: 王輝;闞梓瑄

1.一種路徑網絡圖生成方法，其特征在于，包括：

獲取初始路徑拓撲圖，并基于所述初始路徑拓撲圖確定起點集合和終點集合；所述起點集合基于物理起點與起點搜索范圍確定，所述終點集合基于物理終點與終點搜索范圍確定；

確定所述初始路徑拓撲圖中的可分裂節點，對所述可分裂節點進行分裂處理，以生成分裂路徑子圖；

根據所述起點集合和所述終點集合分別確定虛擬起點和虛擬終點，并根據所述虛擬起點、所述虛擬終點和所述分裂路徑子圖生成虛擬路徑子圖；

將所述虛擬路徑子圖和所述分裂路徑子圖添加至所述初始路徑拓撲圖中，以生成目標路徑拓撲圖。

2.根據權利要求1所述的路徑網絡圖生成方法，其特征在于，所述基于所述初始路徑拓撲圖確定起點集合和終點集合，包括：

確定物理起點的起點位置坐標，并獲取所述物理起點的起點搜索范圍；

根據所述起點位置坐標和所述起點搜索范圍確定與所述物理起點對應的多個起始節點，并根據所述多個起始節點生成所述起點集合；

確定物理終點的終點位置坐標，并獲取所述物理終點的終點搜索范圍；

根據所述終點位置坐標和所述終點搜索范圍確定與所述物理終點對應的多個終止節點，并根據所述多個終止節點生成所述終點集合。

3.根據權利要求1所述的路徑網絡圖生成方法，其特征在于，所述確定所述初始路徑拓撲圖中的可分裂節點，對所述可分裂節點進行分裂處理，以生成分裂路徑子圖，包括：

判斷物理起點和物理終點是否處于同一目標節點；

如果所述物理起點和所述物理終點處于同一目標節點，則將所述目標節點確定為所述可分裂節點；

對所述可分裂節點進行分裂處理，以生成第一分裂節點和第二分裂節點；

確定與所述目標節點關聯的關聯節點，并根據所述關聯節點生成所述第一分裂節點和所述第二分裂節點分別對應的分裂連接邊；

根據所述第一分裂節點、所述第二分裂節點和所述分裂連接邊生成所述分裂路徑子圖。

4.根據權利要求3所述的路徑網絡圖生成方法，其特征在于，所述分裂連接邊包括第一分裂連接邊、第二分裂連接邊和第三分裂連接邊，所述根據所述關聯節點生成所述第一分裂節點和所述第二分裂節點分別對應的分裂連接邊，包括：

分別確定與所述關聯節點對應的前驅節點和后繼節點；

生成所述前驅節點與所述第一分裂節點之間的所述第一分裂連接邊，并將所述第一分裂連接邊對應的第一邊代價添加至所述第一分裂連接邊；

生成所述前驅節點與所述第二分裂節點之間的所述第二分裂連接邊，并將所述第二分裂連接邊對應的第二邊代價添加至所述第二分裂連接邊；

生成所述第一分裂節點與所述第二分裂節點之間的所述第三分裂連接邊，并將所述第三分裂連接邊對應的第三邊代價添加至所述第三分裂連接邊。

5.根據權利要求1所述的路徑網絡圖生成方法，其特征在于，所述虛擬路徑子圖包括分裂節點，所述根據所述虛擬起點、所述虛擬終點和所述分裂路徑子圖生成虛擬路徑子圖，包括：

根據所述虛擬起點、所述虛擬終點和所述分裂節點確定虛擬連接邊；

確定所述虛擬連接邊對應的虛擬邊代價，并將所述虛擬邊代價添加至所述虛擬連接邊；

根據所述虛擬起點、所述虛擬終點和所述虛擬連接邊生成所述虛擬路徑子圖。

6.根據權利要求5所述的路徑網絡圖生成方法，其特征在于，所述虛擬連接邊包括第一虛擬連接邊和第二虛擬連接邊，所述根據所述虛擬起點、所述虛擬終點和所述分裂節點確定虛擬連接邊，包括：

確定與所述虛擬起點關聯的第一關聯節點；其中，所述第一關聯節點包括所述起點集合中的各起始節點以及第一分裂節點；

生成所述虛擬起點與所述第一關聯節點之間的第一虛擬連接邊；

確定與所述虛擬終點關聯的第二關聯節點；其中，所述第二關聯節點包括所述終點集合中的各終止節點以及第二分裂節點；

生成所述虛擬起點與所述第二關聯節點之間的第二虛擬連接邊。