【摘要】：基于道路網(wǎng)的結(jié)構(gòu)分析,提出了一種高等級(jí)道路網(wǎng)拓?fù)渥詣?dòng)保持方法,適用于任意提取的高等級(jí)路網(wǎng)。首先根據(jù)道路的連通關(guān)系生成對(duì)偶圖,利用最小生成樹(shù)保持道路網(wǎng)的整體連通性;然后使用廣度優(yōu)先搜索和最短路徑計(jì)算進(jìn)行懸掛弧段連接和合理路徑連接,保持高等級(jí)道路網(wǎng)的導(dǎo)航連通性;最后通過(guò)實(shí)驗(yàn)驗(yàn)證了本文方法所保持的道路網(wǎng)拓?fù)浣Y(jié)構(gòu)的有效性。實(shí)驗(yàn)結(jié)果表明,通過(guò)本方法保持的拓?fù)潢P(guān)系能夠保持道路網(wǎng)的整體連通性,反映道路網(wǎng)的高等級(jí)結(jié)構(gòu)模式特征,而且與基于原始劃分的高等級(jí)道路網(wǎng)所規(guī)劃的最短路徑相比,拓?fù)渥詣?dòng)保持后的高等級(jí)道路網(wǎng)能夠合理地反映道路結(jié)點(diǎn)之間的導(dǎo)航路徑規(guī)劃。
【圖文】：

。１．１整體連通性保持方法１．１．１生成道路網(wǎng)的對(duì)偶圖本文所設(shè)計(jì)的道路連通性保持算法基于對(duì)偶圖，即將道路網(wǎng)中的每條道路作為對(duì)偶圖中的結(jié)點(diǎn)，而將道路之間的連通關(guān)系作為對(duì)偶圖中結(jié)點(diǎn)之間的邊。如圖１（ａ）所示，，在對(duì)偶圖中，將通過(guò)屬性、形態(tài)或結(jié)構(gòu)特征分析而保留的高層級(jí)道路標(biāo)記為“固定點(diǎn)（黑點(diǎn)）”，低等級(jí)道路為“待刪點(diǎn)（白點(diǎn)）”。通過(guò)對(duì)偶圖的轉(zhuǎn)化，整體連通性保持便可抽象為通過(guò)選取適當(dāng)?shù)摹鞍c(diǎn)”，使得圖中全部的“黑點(diǎn)”仍能保持一個(gè)連通的整體，并將剩余的“白點(diǎn)”全部刪除。圖１道路網(wǎng)連通性保持算法示意圖Ｆｉｇ．１ＧｒａｐｈｉｃＥｘａｍｐｌｅｓｏｆＲｏａｄＮｅｔｗｏｒｋＣｏｎｎｅｃｔｉｖｉｔｙＡｌｇｏｒｉｔｈｍ１．１．２算法描述基于對(duì)偶圖，使用克魯斯卡爾最小生成樹(shù)（ｍｉｎｉｍｕｍｓｐａｎｎｉｎｇｔｒｅｅ，ＭＳＴ）算法［１０］，具體實(shí)現(xiàn)過(guò)程如下。１）計(jì)算最小生成樹(shù)。對(duì)“黑點(diǎn)”之間邊的權(quán)重賦為０，其他邊按照通達(dá)性賦予相應(yīng)的權(quán)重。如果缺少交通量信息，可將“白點(diǎn)”連接的權(quán)重全部賦為１，結(jié)果如圖１（ｂ）所示。由于對(duì)“黑點(diǎn)”之間邊的權(quán)值賦予０，在樹(shù)的生成過(guò)程中，會(huì)首先盡可能地將“黑點(diǎn)”連接起來(lái)。最后得到的生成樹(shù)中必定包含將無(wú)法直接連通的“黑點(diǎn)”連接起來(lái)的“白點(diǎn)”。２）迭代刪除度為１的“白點(diǎn)”。第１）步的最小生成樹(shù)包含需要保留的整體連通道路，但不是所有的道路都起到了連通作用，需要進(jìn)行篩眩遍歷所有的“白點(diǎn)”，判斷每一個(gè)“白點(diǎn)”的連接數(shù)，并刪除連接數(shù)為１的“白點(diǎn)”，計(jì)算過(guò)程如圖１（ｃ）所示。由于最小生成樹(shù)中沒(méi)有環(huán)，因此最后保留的便是起到連通“黑點(diǎn)”作用的“

）。若匹配成功，則將在已選路徑上的路段都提升為與懸掛弧段相同的等級(jí)。這樣就可以很好地保留道路網(wǎng)的區(qū)域模式，同時(shí)也去除了懸掛弧段，增強(qiáng)了道路網(wǎng)的整體連通性。４）重復(fù)步驟２）、３），直至所有懸掛結(jié)點(diǎn)計(jì)算完畢。１．２．２合理路徑連接導(dǎo)航規(guī)劃中應(yīng)當(dāng)盡量避免繞路，首先應(yīng)對(duì)繞路進(jìn)行定義，即最大的最短路徑閾值。研究發(fā)現(xiàn)，格網(wǎng)模式是道路網(wǎng)中普遍存在的一種區(qū)域結(jié)構(gòu)模式，即區(qū)域由兩組相互正交的平行道路相交而成［１１］。該模式可以用來(lái)指導(dǎo)兩點(diǎn)之間最大的最短路徑閾值的設(shè)定。如圖２所示的起止點(diǎn)，黑色路徑為格網(wǎng)區(qū)域中的最短路徑，即曼哈頓距離（Ｍａｎｈａｔｔａｎｄｉｓｔａｎｃｅ）［１２］，而灰色路徑則存在繞遠(yuǎn)。因此，本文認(rèn)為格網(wǎng)模式中兩點(diǎn)之間的最短路徑最長(zhǎng)的應(yīng)為兩點(diǎn)之間的最大曼哈頓距離，即兩點(diǎn)之間直線距離的i幔脖�。哇E擦降闃渚嗬朧疽饌跡疲椋紓玻牛幔恚穡歟澹螅錚媯模椋媯媯澹潁澹睿簦模椋螅簦幔睿悖澹螅攏澹簦鰨澹澹睿裕鰨錚校錚椋睿簦罌悸塹降纜吠械那蚨轡還嬖蛐巫矗砑硬脅瞀�，两甸槷间最短路径的桩岓阈謸�(dān)蟮募撲閎縭劍ǎ保┧荊海螅劍╥幔玻牛

本文編號(hào)：2522359