[發(fā)明專利]路網(wǎng)拓?fù)鋱D的劃分方法、裝置、介質(zhì)及設(shè)備

有效

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

1.一種路網(wǎng)拓?fù)鋱D的劃分方法，其特征在于，所述方法包括：

獲取當(dāng)前版本路網(wǎng)數(shù)據(jù)的第一頂層路網(wǎng)拓?fù)鋱D，以及獲取前一版本路網(wǎng)數(shù)據(jù)的第二頂層路網(wǎng)拓?fù)鋱D的劃分結(jié)果；所述劃分結(jié)果包括頂點(diǎn)和所述頂點(diǎn)對(duì)應(yīng)的單元圖；所述頂點(diǎn)為所述第二頂層路網(wǎng)拓?fù)鋱D中的道路標(biāo)記點(diǎn)，所述單元圖為所述第二頂層路網(wǎng)拓?fù)鋱D劃分后的路網(wǎng)拓?fù)渥訄D，所述單元圖包含有限數(shù)量的所述頂點(diǎn)；

根據(jù)所述劃分結(jié)果，確定所述第一頂層路網(wǎng)拓?fù)鋱D中每個(gè)道路連通分支的第一頂點(diǎn)集合和第二頂點(diǎn)集合；所述第一頂點(diǎn)集合中的第一頂點(diǎn)為所述劃分結(jié)果中的所述頂點(diǎn)；所述第二頂點(diǎn)集合中的第二頂點(diǎn)為所述道路連通分支中除去所述第一頂點(diǎn)的剩余頂點(diǎn)；

在所述道路連通分支的第一頂點(diǎn)集合為非空集時(shí)，確定所述第二頂點(diǎn)的關(guān)聯(lián)第一頂點(diǎn)，并根據(jù)所述關(guān)聯(lián)第一頂點(diǎn)對(duì)應(yīng)的單元圖確定所述第二頂點(diǎn)對(duì)應(yīng)的單元圖；所述關(guān)聯(lián)第一頂點(diǎn)與所述第二頂點(diǎn)連通且所述關(guān)聯(lián)第一頂點(diǎn)屬于所述第一頂點(diǎn)集合；

根據(jù)所述道路連通分支中所述第一頂點(diǎn)、所述第一頂點(diǎn)對(duì)應(yīng)的單元圖、所述第二頂點(diǎn)以及所述第二頂點(diǎn)對(duì)應(yīng)的單元圖，得到所述第一頂層路網(wǎng)拓?fù)鋱D的劃分結(jié)果。

2.根據(jù)權(quán)利要求1所述的路網(wǎng)拓?fù)鋱D的劃分方法，其特征在于，所述根據(jù)所述劃分結(jié)果，確定所述第一頂層路網(wǎng)拓?fù)鋱D中每個(gè)道路連通分支的第一頂點(diǎn)集合和第二頂點(diǎn)集合，包括：

對(duì)所述第一頂層路網(wǎng)拓?fù)鋱D進(jìn)行分解，得到一個(gè)或多個(gè)道路連通分支；

對(duì)每個(gè)所述道路連通分支進(jìn)行掃描，得到每個(gè)所述道路連通分支對(duì)應(yīng)的分支頂點(diǎn)；

根據(jù)所述劃分結(jié)果確定每個(gè)所述道路連通分支對(duì)應(yīng)的分支頂點(diǎn)的劃分狀態(tài)；所述劃分狀態(tài)指示所述劃分結(jié)果中是否包含所述分支頂點(diǎn)；

根據(jù)每個(gè)所述道路連通分支對(duì)應(yīng)的分支頂點(diǎn)的劃分狀態(tài)，從每個(gè)所述道路連通分支的分支頂點(diǎn)中確定每個(gè)所述道路連通分支的第一頂點(diǎn)集合和第二頂點(diǎn)集合；所述第一頂點(diǎn)集合中的第一頂點(diǎn)為所述劃分結(jié)果中的所述頂點(diǎn)；所述第二頂點(diǎn)集合中的第二頂點(diǎn)為相應(yīng)道路連通分支中除去所述第一頂點(diǎn)的剩余頂點(diǎn)。

3.根據(jù)權(quán)利要求1所述的路網(wǎng)拓?fù)鋱D的劃分方法，其特征在于，所述在所述道路連通分支的第一頂點(diǎn)集合為非空集時(shí)，確定所述第二頂點(diǎn)的關(guān)聯(lián)第一頂點(diǎn)，并根據(jù)所述關(guān)聯(lián)第一頂點(diǎn)對(duì)應(yīng)的單元圖確定所述第二頂點(diǎn)對(duì)應(yīng)的單元圖，包括：

基于泛洪法，從所述道路連通分支的第一頂點(diǎn)集合中確定所述第二頂點(diǎn)的所述關(guān)聯(lián)第一頂點(diǎn)；所述關(guān)聯(lián)第一頂點(diǎn)與所述第二頂點(diǎn)連通；

根據(jù)所述劃分結(jié)果，確定所述關(guān)聯(lián)第一頂點(diǎn)對(duì)應(yīng)的單元圖；

根據(jù)所述關(guān)聯(lián)第一頂點(diǎn)對(duì)應(yīng)的單元圖的單元標(biāo)識(shí)，確定所述第二頂點(diǎn)對(duì)應(yīng)的單元圖的單元標(biāo)識(shí)。

4.根據(jù)權(quán)利要求1所述的路網(wǎng)拓?fù)鋱D的劃分方法，其特征在于，所述方法還包括：

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

構(gòu)建所述道路連通分支中所述第二頂點(diǎn)與所述目標(biāo)單元圖的對(duì)應(yīng)關(guān)系；

根據(jù)所述道路連通分支中所述第二頂點(diǎn)與所述目標(biāo)單元圖的對(duì)應(yīng)關(guān)系，確定所述第一頂層路網(wǎng)拓?fù)鋱D的劃分結(jié)果。

5.根據(jù)權(quán)利要求1所述的路網(wǎng)拓?fù)鋱D的劃分方法，其特征在于，所述方法還包括：

基于啟發(fā)式自然割劃分算法，對(duì)所述當(dāng)前版本路網(wǎng)數(shù)據(jù)的第一剩余層路網(wǎng)拓?fù)鋱D進(jìn)行劃分，得到所述第一剩余層路網(wǎng)拓?fù)鋱D的劃分結(jié)果；所述第一剩余層路網(wǎng)拓?fù)鋱D為所述當(dāng)前版本路網(wǎng)數(shù)據(jù)中除所述第一頂層路網(wǎng)拓?fù)鋱D之外的路網(wǎng)拓?fù)鋱D；

根據(jù)所述第一頂層路網(wǎng)拓?fù)鋱D的劃分結(jié)果和所述第一剩余層路網(wǎng)拓?fù)鋱D的劃分結(jié)果，得到所述當(dāng)前版本路網(wǎng)數(shù)據(jù)的路網(wǎng)拓?fù)鋱D多層劃分結(jié)果。

6.根據(jù)權(quán)利要求1所述的路網(wǎng)拓?fù)鋱D的劃分方法，其特征在于，所述方法還包括：

獲取前一版本路網(wǎng)數(shù)據(jù)的第二頂層路網(wǎng)拓?fù)鋱D的劃分結(jié)果；所述劃分結(jié)果包括頂點(diǎn)和所述頂點(diǎn)對(duì)應(yīng)的單元圖；

根據(jù)所述劃分結(jié)果，構(gòu)建所述頂點(diǎn)與對(duì)應(yīng)的所述單元圖的映射關(guān)系；

將所述映射關(guān)系存儲(chǔ)在哈希表中，以根據(jù)所述哈希表確定所述第一頂層路網(wǎng)拓?fù)鋱D的劃分結(jié)果。