[發(fā)明專利]路網拓撲圖的劃分方法、裝置、介質及設備

有效

• 申請?zhí)枺?/td>: 202111128111.7
• 申請日: 2021-09-26
• 公開（公告）號: CN113569369B
• 公開（公告）日: 2022-01-07
• 發(fā)明（設計）人: 張龍;李偉征;張明
• 申請（專利權）人: 騰訊科技（深圳）有限公司
• 主分類號: G06F30/18
• 分類號: G06F30/18;G06F111/02
• 代理公司: 廣州三環(huán)專利商標代理有限公司 44202
• 代理人: 熊永強;賈允

1.一種路網拓撲圖的劃分方法，其特征在于，所述方法包括：

獲取當前版本路網數據的第一頂層路網拓撲圖，以及獲取前一版本路網數據的第二頂層路網拓撲圖的劃分結果；所述劃分結果包括頂點和所述頂點對應的單元圖；所述頂點為所述第二頂層路網拓撲圖中的道路標記點，所述單元圖為所述第二頂層路網拓撲圖劃分后的路網拓撲子圖，所述單元圖包含有限數量的所述頂點；

根據所述劃分結果，確定所述第一頂層路網拓撲圖中每個道路連通分支的第一頂點集合和第二頂點集合；所述第一頂點集合中的第一頂點為所述劃分結果中的所述頂點；所述第二頂點集合中的第二頂點為所述道路連通分支中除去所述第一頂點的剩余頂點；

在所述道路連通分支的第一頂點集合為非空集時，確定所述第二頂點的關聯第一頂點，并根據所述關聯第一頂點對應的單元圖確定所述第二頂點對應的單元圖；所述關聯第一頂點與所述第二頂點連通且所述關聯第一頂點屬于所述第一頂點集合；

根據所述道路連通分支中所述第一頂點、所述第一頂點對應的單元圖、所述第二頂點以及所述第二頂點對應的單元圖，得到所述第一頂層路網拓撲圖的劃分結果。

2.根據權利要求1所述的路網拓撲圖的劃分方法，其特征在于，所述根據所述劃分結果，確定所述第一頂層路網拓撲圖中每個道路連通分支的第一頂點集合和第二頂點集合，包括：

對所述第一頂層路網拓撲圖進行分解，得到一個或多個道路連通分支；

對每個所述道路連通分支進行掃描，得到每個所述道路連通分支對應的分支頂點；

根據所述劃分結果確定每個所述道路連通分支對應的分支頂點的劃分狀態(tài)；所述劃分狀態(tài)指示所述劃分結果中是否包含所述分支頂點；

根據每個所述道路連通分支對應的分支頂點的劃分狀態(tài)，從每個所述道路連通分支的分支頂點中確定每個所述道路連通分支的第一頂點集合和第二頂點集合；所述第一頂點集合中的第一頂點為所述劃分結果中的所述頂點；所述第二頂點集合中的第二頂點為相應道路連通分支中除去所述第一頂點的剩余頂點。

3.根據權利要求1所述的路網拓撲圖的劃分方法，其特征在于，所述在所述道路連通分支的第一頂點集合為非空集時，確定所述第二頂點的關聯第一頂點，并根據所述關聯第一頂點對應的單元圖確定所述第二頂點對應的單元圖，包括：

基于泛洪法，從所述道路連通分支的第一頂點集合中確定所述第二頂點的所述關聯第一頂點；所述關聯第一頂點與所述第二頂點連通；

根據所述劃分結果，確定所述關聯第一頂點對應的單元圖；

根據所述關聯第一頂點對應的單元圖的單元標識，確定所述第二頂點對應的單元圖的單元標識。

4.根據權利要求1所述的路網拓撲圖的劃分方法，其特征在于，所述方法還包括：

在所述道路連通分支的第一頂點集合為空集時，創(chuàng)建目標單元圖；

構建所述道路連通分支中所述第二頂點與所述目標單元圖的對應關系；

根據所述道路連通分支中所述第二頂點與所述目標單元圖的對應關系，確定所述第一頂層路網拓撲圖的劃分結果。

5.根據權利要求1所述的路網拓撲圖的劃分方法，其特征在于，所述方法還包括：

基于啟發(fā)式自然割劃分算法，對所述當前版本路網數據的第一剩余層路網拓撲圖進行劃分，得到所述第一剩余層路網拓撲圖的劃分結果；所述第一剩余層路網拓撲圖為所述當前版本路網數據中除所述第一頂層路網拓撲圖之外的路網拓撲圖；

根據所述第一頂層路網拓撲圖的劃分結果和所述第一剩余層路網拓撲圖的劃分結果，得到所述當前版本路網數據的路網拓撲圖多層劃分結果。

6.根據權利要求1所述的路網拓撲圖的劃分方法，其特征在于，所述方法還包括：

獲取前一版本路網數據的第二頂層路網拓撲圖的劃分結果；所述劃分結果包括頂點和所述頂點對應的單元圖；

根據所述劃分結果，構建所述頂點與對應的所述單元圖的映射關系；

將所述映射關系存儲在哈希表中，以根據所述哈希表確定所述第一頂層路網拓撲圖的劃分結果。