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

有效

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

本申請(qǐng)公開(kāi)了路網(wǎng)拓?fù)鋱D的劃分方法、裝置、介質(zhì)及設(shè)備，涉及智慧交通領(lǐng)域，包括：獲取當(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)的單元圖；根據(jù)劃分結(jié)果確定第一頂層路網(wǎng)拓?fù)鋱D中道路連通分支的第一頂點(diǎn)集合和第二頂點(diǎn)集合；第一頂點(diǎn)集合中的第一頂點(diǎn)為劃分結(jié)果中的頂點(diǎn)；確定第二頂點(diǎn)的關(guān)聯(lián)第一頂點(diǎn)并根據(jù)關(guān)聯(lián)第一頂點(diǎn)對(duì)應(yīng)的單元圖確定第二頂點(diǎn)對(duì)應(yīng)的單元圖；根據(jù)道路連通分支中第一頂點(diǎn)、第一頂點(diǎn)對(duì)應(yīng)的單元圖、第二頂點(diǎn)和第二頂點(diǎn)對(duì)應(yīng)的單元圖，得到第一頂層路網(wǎng)拓?fù)鋱D的劃分結(jié)果。本申請(qǐng)能夠有效地加快對(duì)路網(wǎng)拓?fù)鋱D的劃分，減少路網(wǎng)數(shù)據(jù)的編譯時(shí)間。

技術(shù)領(lǐng)域

本申請(qǐng)涉及智慧交通技術(shù)領(lǐng)域，具體涉及路網(wǎng)拓?fù)鋱D的劃分方法、裝置、介質(zhì)及設(shè)備。

背景技術(shù)

為了提高路線(xiàn)規(guī)劃的速度，目前的路線(xiàn)規(guī)劃引擎都采用路網(wǎng)拓?fù)鋱D多層劃分的方案。如目前最常用的CRP（Customizable Route Planning，可定制的路線(xiàn)規(guī)劃）引擎采用PUNCH（Partitioning Using Natural Cut Heuristics，使用自然割啟發(fā)式進(jìn)行劃分）算法來(lái)對(duì)多層路網(wǎng)拓?fù)鋱D進(jìn)行全量式的劃分。

但這種全量式的劃分方式極大地增加了路網(wǎng)拓?fù)鋱D的劃分時(shí)間，降低路網(wǎng)數(shù)據(jù)更新的時(shí)效，從而影響以路網(wǎng)數(shù)據(jù)為基礎(chǔ)的應(yīng)用服務(wù)。

發(fā)明內(nèi)容

為了提升路網(wǎng)拓?fù)鋱D的劃分效率，本申請(qǐng)?zhí)峁┝寺肪W(wǎng)拓?fù)鋱D的劃分方法、裝置、介質(zhì)及設(shè)備。所述技術(shù)方案如下：

第一方面，本申請(qǐng)?zhí)峁┝艘环N路網(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é)果。

第二方面，本申請(qǐng)?zhí)峁┝艘环N路網(wǎng)拓?fù)鋱D的劃分裝置，所述裝置包括：

數(shù)據(jù)獲取模塊，用于獲取當(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)；

頂點(diǎn)分類(lèi)模塊，用于根據(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)劃分模塊，用于在所述道路連通分支的第一頂點(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)集合；