GIS網(wǎng)絡(luò)分析功能及實(shí)現(xiàn).doc

GIS網(wǎng)絡(luò)分析功能的實(shí)現(xiàn)摘要:網(wǎng)絡(luò)分析作為的重要功能,在電子導(dǎo)航、交通旅游、城市規(guī)劃以及電力、通訊等各種管網(wǎng)、管線的布局設(shè)計中發(fā)揮了重要的作用。隨著系統(tǒng)集成應(yīng)用的不斷深入,為了滿足用戶的應(yīng)用需求,我們通過二次開發(fā)的手段,為一些平臺定制了網(wǎng)絡(luò)分析功能。利用經(jīng)典的Dijkstra算法,結(jié)合數(shù)據(jù)和平臺特點(diǎn),通過簡單的程序設(shè)計可以實(shí)現(xiàn)復(fù)雜的網(wǎng)絡(luò)分析功能。 關(guān)鍵詞:網(wǎng)絡(luò)分析;Dijkstra算法;網(wǎng)絡(luò)拓?fù)潢P(guān)系 網(wǎng)絡(luò)分析作為GIS應(yīng)用最主要的功能之一,在電子導(dǎo)航、交通旅游、城市規(guī)劃以及電力、通訊等各種管網(wǎng)、管線的布局設(shè)計中發(fā)揮了重要的作用。隨著計算機(jī)及測繪技術(shù)的不斷發(fā)展,地理信息產(chǎn)業(yè)得以蓬勃發(fā)展,近幾年來我中心面向社會的GIS應(yīng)用開發(fā)不斷增多,逐漸形成以MapObject和 MapGuide為主流的GIS應(yīng)用開發(fā)體系。MapGuide是Autodesk公司的商業(yè)webgis產(chǎn)品,該產(chǎn)品合理的分配了客戶機(jī)和服務(wù)器的運(yùn)算,實(shí)現(xiàn)了矢量數(shù)據(jù)的直接訪問,優(yōu)良的性能、可擴(kuò)展性強(qiáng),是webgis應(yīng)用的首選產(chǎn)品之一。MapObject是美國ESRI生產(chǎn)的控件式GIS系統(tǒng),它性能穩(wěn)定,價格適中,是目前非常流行的GIS系統(tǒng)開發(fā)平臺。但這兩個系統(tǒng)都沒有現(xiàn)成的網(wǎng)絡(luò)分析功能,為了滿足用戶的應(yīng)用需求,我們通過二次開發(fā)為MapGuide和MapObject分別定制了網(wǎng)絡(luò)分析功能。 網(wǎng)絡(luò)分析中最基本最關(guān)鍵的問題是最短路徑問題。最短路徑不僅僅指一般地理意義上的距離最短,還可以引申到其他的度量,如時間、費(fèi)用、線路容量等。相應(yīng)地,最短路徑問題就成為最快路徑問題、最低費(fèi)用問題等。其實(shí),無論是距離最短、時間最快還是費(fèi)用最低,它們的核心算法都是最短路徑算法。 最短路徑的求解,必須把現(xiàn)實(shí)生活中的道路、管線等各種網(wǎng)絡(luò)抽象成一種數(shù)學(xué)結(jié)構(gòu),這種抽象出來的數(shù)學(xué)結(jié)構(gòu)被稱為網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。于是各種網(wǎng)絡(luò)分析技術(shù)實(shí)現(xiàn)的關(guān)鍵在于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的建立和高效能最短路徑算法。下面我們就這兩個問題進(jìn)行深入探討。 1最短路徑算法 最短路徑算法,關(guān)鍵是將一個物理網(wǎng)絡(luò)結(jié)構(gòu)抽象為一個數(shù)學(xué)網(wǎng)絡(luò)結(jié)構(gòu),再利用數(shù)學(xué)方法進(jìn)行求解。 1.1算法選擇 在數(shù)學(xué)和計算機(jī)領(lǐng)域網(wǎng)絡(luò)被抽象為圖,再利用圖論的方法計算最短路徑。目前提出的基于圖論的最短路徑的算法大約有17種。經(jīng)專家測試,其中有3種效果比較好,它們分別是:TQQ、DKA以及DKD。其中TQQ算法的基礎(chǔ)是圖增長理論;后兩種算法則是基于Dijkstra的算法。Dijkstra算法是經(jīng)典的最短路徑算法,目前多數(shù)系統(tǒng)解決最短路徑問題采用了Dijkstra算法為理論基礎(chǔ),只是不同系統(tǒng)對Dijkstra算法采用了不同的實(shí)現(xiàn)方法。 1.2經(jīng)典Dijkstra算法的主要思想Dijkstra算法的基本思路是:將頂點(diǎn)分成兩個集合S和T,已求出最短路的點(diǎn)置于S中,其它點(diǎn)置于T中。開始時S中僅含起點(diǎn)vs,其它點(diǎn)全在T中,隨著求最短路迭代工作的進(jìn)行,S中的點(diǎn)逐漸增多,當(dāng)終點(diǎn)vt也被納入S中時,迭代結(jié)束。為了便于計算和區(qū)分各頂點(diǎn)是否已進(jìn)入集合S,給已求出到起點(diǎn)最短路的點(diǎn)vk賦以標(biāo)號。這個標(biāo)號由兩部分組成,記為(d(vs,vk),i)其中i為vk到起點(diǎn)最短路上的前點(diǎn),d(vs,vk為從起點(diǎn)vs到vk的最短路長。因每個標(biāo)號含有兩部分,故稱為雙標(biāo)號法。最短路徑算法的基本過程如下:(1)給始點(diǎn)vs賦以標(biāo)號(0,s),并置vs于置,其它頂點(diǎn)于集合T中。 (2)對圖G里起點(diǎn)在S中終點(diǎn)在T中的邊ei,計算: d(vs,vk)=mimd(vs,vi)+minjWijvis,vjT并將vk置于S中,同時賦給它標(biāo)號(d(vsvk),i)。 (3)重復(fù)步驟(2),當(dāng)vtS時計算結(jié)束vt的第一個標(biāo)號給出vsvt的最短路長;利用第 二個標(biāo)號反向追蹤,可得最短路徑。 2網(wǎng)絡(luò)拓?fù)潢P(guān)系的獲取與高效訪問 要想用計算機(jī)程序?qū)崿F(xiàn)Dijkstra算法,關(guān)鍵技術(shù)是用什么樣的方式抽象出網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),及節(jié)點(diǎn)與節(jié)點(diǎn)的連通關(guān)系,并對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行高效能訪問。 2.1拓?fù)潢P(guān)系的獲取 GIS中的數(shù)據(jù)(如道路、管網(wǎng)、水系等)要進(jìn)行最短路徑的計算,就必須首先將其按結(jié)點(diǎn)和邊的關(guān)系抽象為圖的結(jié)構(gòu),這在GIS中稱為構(gòu)建網(wǎng)絡(luò)的拓?fù)潢P(guān)系。只有建立了拓?fù)潢P(guān)系,我們才能進(jìn)行網(wǎng)絡(luò)路徑分析。GIS數(shù)據(jù)通常是圖形數(shù)據(jù)和屬性數(shù)據(jù)的有機(jī)集合。在ARC/INFO下利用命令CLEAN對道路網(wǎng)數(shù)據(jù)構(gòu)建網(wǎng)絡(luò)拓?fù)?我們可以看到屬 性表,其屬性數(shù)據(jù)中包括_Fnode(起點(diǎn))和_Tnode(終點(diǎn))兩個屬性項。該屬性表中包含了一個完備的網(wǎng)絡(luò)拓?fù)潢P(guān)系,即記錄了該圖擁有多少個節(jié)點(diǎn),又記錄了節(jié)點(diǎn)與節(jié)點(diǎn)的連通關(guān)系,不同的_Fnode、_Tnode標(biāo)號代表不同的節(jié)點(diǎn),及一條線的起始節(jié)點(diǎn)和終止節(jié)點(diǎn),擁有相同節(jié)點(diǎn)的線相連,從該表大家應(yīng)該很清楚的看出道路網(wǎng)的拓?fù)浣Y(jié)構(gòu)。構(gòu)建網(wǎng)絡(luò)拓?fù)涫且粋€復(fù)雜的過程,在搭建用戶應(yīng)用系統(tǒng)時,一般使用ARC/INFO等專業(yè)軟件事先構(gòu)件好網(wǎng)絡(luò)拓?fù)潢P(guān)系,使用時只需訪問GIS數(shù)據(jù)的屬性表即可。 2.2網(wǎng)絡(luò)拓?fù)潢P(guān)系的高效訪問 利用上面的屬性表我們可以有效的解讀出一個網(wǎng)絡(luò)拓?fù)潢P(guān)系,在按標(biāo)記法實(shí)現(xiàn)Dijkstra算法的過程中,核心步驟就是從未標(biāo)記的點(diǎn)中選擇一個權(quán)值最小的弧段,即上面所述算法的2)3)步。這是一個循環(huán)比較的過程,如果不采用任何技巧,要選擇一個權(quán)值最小的弧段就必須對屬性表進(jìn)行多次掃描,在大數(shù)據(jù)量的情況下,這無疑是一個制約計算速度的瓶頸。下面主要就如何從含拓?fù)潢P(guān)系的屬性表中解析一個簡潔高效的網(wǎng)絡(luò)拓?fù)浯鎯Y(jié)構(gòu)進(jìn)行討論。在數(shù)學(xué)和計算機(jī)領(lǐng)域中網(wǎng)絡(luò)拓?fù)浔怀橄鬄閳D,所以其基礎(chǔ)是圖的存儲表示。一般而言,無向圖可以用鄰接矩陣和鄰接多重表來表示,而有向圖則可以用鄰接表和十字鏈表表示,其優(yōu)缺點(diǎn)的比較見表2。 綜合以上4種存儲結(jié)構(gòu)的優(yōu)缺點(diǎn),我們采用了兩個數(shù)組來存儲網(wǎng)絡(luò)圖,一個用來存儲和弧段相關(guān)的數(shù)據(jù)(Net-ArcList),另一個則存儲和頂點(diǎn)相關(guān)的數(shù)據(jù)(Net-NodeIndex)。Net-ArcList用一個數(shù)組維護(hù)并且以弧段起點(diǎn)的點(diǎn)號來順序排列,同一起點(diǎn)的弧段按權(quán)值排序。這個數(shù)組類似于鄰接矩陣的壓縮存儲方式,其內(nèi)容則具有鄰接多重表的特點(diǎn),即一條邊以兩頂點(diǎn)表示。Net-NodeIndex則相當(dāng)于一個記錄了頂點(diǎn)出度的索引表,通過它可以很容易地得到此頂點(diǎn)的出度和與它相連的第一條弧段在弧段數(shù)組中的位置。這樣就可以以最快速度搜索出與任意節(jié)點(diǎn)相連的邊在頂點(diǎn)已編號的情況下,建立Net-ArcList和Net-NodeIndex兩個表以及對Net-ArcList的排序其時間復(fù)雜度共為O(2n+lgn),否則為O(m+2n+lgn)。這個結(jié)構(gòu)所需的空間也是必要條件下最小的,記錄了m個頂點(diǎn)以及n條邊的相關(guān)信息,與鄰接多重表是相同的。利用表1所提供的屬性表,有向圖只需對Fode進(jìn)行一次排序和一次索引,即可得到上面的兩個數(shù)組,對與無向圖則稍復(fù)雜一點(diǎn)。最后我們所要作的事情就是進(jìn)行算法2)3)步的循環(huán)求解最短路徑。我們利用該方法在Vb開發(fā)環(huán)境中針對MapObject定制了具有網(wǎng)絡(luò)分析功能的動態(tài)連接庫;在ASP.Net開發(fā)環(huán)境下,利用ASP.NetWeb服務(wù)為MapGuide成功 的定制了網(wǎng)絡(luò)路徑分析服務(wù)器。在算法的具體實(shí)現(xiàn)中我們還吸收了Moore-Pape算法的優(yōu)點(diǎn),使運(yùn)算速度有了進(jìn)一步提高,經(jīng)測試,2萬個節(jié)點(diǎn),25000條路全部遍歷,平均只需1秒。完全可以滿足用戶在速度方面的需求。