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

《GIS網(wǎng)絡(luò)分析功能及實現(xiàn).doc》由會員分享，可在線閱讀，更多相關(guān)《GIS網(wǎng)絡(luò)分析功能及實現(xiàn).doc（5頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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