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

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

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

本文編號：2522359