空間分析技術(shù)在數(shù)字城管系統(tǒng)中的應用

摘要：空間分析在GIS中扮演著越來越重要的角色。該文以廈門市數(shù)字城市信息管理系統(tǒng)為研究對象，該系統(tǒng)在大屏幕監(jiān)督指揮子系統(tǒng)中運用了GIS技術(shù)，同時基于GIS實際需求使用了改進的空間分析算法以便實現(xiàn)系統(tǒng)功能。改進的空間算法以傳統(tǒng)空間分析算法為基礎，針對空間數(shù)據(jù)量龐大檢索緩慢的問題，提出了一種基于方向性的最短路徑搜索方法。

關鍵詞：空間分析；Dijkstra；最短路徑搜索

中圖分類號：TP312文獻標識碼：A文章編號：1009-3044(2009)04-0984-02

Space Analyse Technology Use in Digital City Management

LIU Dong-po1， LIU Fa-neng2

(1.Department of Antomation， Xiamen University， Xiamen 361001，China; 2.Xiamen Zhiyu Technology Co.Ltd， Xiamen 361002， China)

Abstract: space analyse tech is play more and more important in GIS. This article bases on XIAMEN digital city management system， this system use GIS tech in her big screen supervise and guide vice system， and use improved arithmetic to achieve system function. The improved arithmetic bases on the original arithmetic and direct to the space large data search slowly， comes out with a method baess on the direction for the shortcut search.

Key words:space analyse; Dijkstra; shortcut search

1 引言

最短路徑算法是計算機科學與地理信息科學等領域的研究熱點。它是資源分配、區(qū)位分析、路線設計等優(yōu)化問題的基礎。很多網(wǎng)絡相關問題均可納入最短路徑問題的范疇之中，如時間、費用、線路容量等。相應地，最短路徑問題就成為最快路徑問題、最低費用問題等[1]。由于最短路徑問題在實際中常用于汽車導航系統(tǒng)以及各種應急系統(tǒng)(如110報警、119火警以及醫(yī)療救護系統(tǒng))等，這些系統(tǒng)一般要求計算出到出事地點的最佳路線的時間很短，在行車過程中還需要實時計算出車輛前方的行駛路線，這就決定了最短路徑問題的實現(xiàn)應該是高效率的。其實，無論是距離最短，時間最快，還是費用最低，它們的核心算法都是最短路徑算法。

經(jīng)典的理論與不斷發(fā)展完善的計算機數(shù)據(jù)結(jié)構(gòu)及算法的有效結(jié)合使得新的最短路徑算法不斷涌現(xiàn)。經(jīng)典的最短路徑算法[1]——Dijkstra（狄克斯特拉）算法采用的數(shù)據(jù)結(jié)構(gòu)及其實現(xiàn)方法由于受到當時計算機硬件發(fā)展水平的限制，將空間存儲問題放到了一個很重要的位置，以犧牲適當?shù)臅r間效率來換取空間節(jié)省。目前，空間存儲問題已不是要考慮的主要問題，因此有必要對已有的算法重新進行考慮并進行改進，可以用空間換時間來提高最短路徑算法的效率。

2 Dijkstra最優(yōu)路徑算法

設G=(V，E)是一個帶權(quán)有向圖，如何求出從G的某個源點V到其余每一個頂點的最短路徑，狄克斯特拉于1959年提出了解決此問題的一般算法，其基本思想是：

把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示），第二組為其余未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。

在算法實現(xiàn)過程中，核心步驟就是從U中選擇一個權(quán)值最小的結(jié)點，加入到S中。這是一個循環(huán)比較的過程，如果不采用任何技巧，U中的頂點將以無序的形式存放在一個鏈表或數(shù)組中。那么要選擇一個權(quán)值最小的弧段就必須把所有的點都掃描一遍，在大數(shù)據(jù)量的情況下，這無疑是一個制約計算速度的瓶頸。另外，對GIS中的道路數(shù)據(jù)進行最短路徑計算，首先必須將其按結(jié)點和邊的關系抽象為圖的結(jié)構(gòu)，這在GIS中稱為構(gòu)建網(wǎng)絡的拓撲關系。如果用一個矩陣來表示這個網(wǎng)絡，不但所需空間巨大，而且效率會很低。下面將對以上問題提出解決辦法。

3 基于方向性的最短路徑搜索方法

最短路徑算法產(chǎn)生于計算機科學及運籌學，因只考慮網(wǎng)絡的拓撲特征或階段特征，而忽略了網(wǎng)絡的空間分布特征，導致其搜索過程缺乏方向性，得到的是一棵以源點為根的最短路徑樹。即使構(gòu)造此路徑樹的過程在到達終止結(jié)點后即結(jié)束，此方法依然有大量計算是冗余的。為了解決Dijkstra算法效率的這個瓶頸問題，可以通過減少臨時標記結(jié)點數(shù)量的方法使算法得到優(yōu)化?；诖?，提出了采用方向性限制搜索的方法，通過減少臨時標記點數(shù)量來提高計算效率。

3.1 優(yōu)化搜索實現(xiàn)過程

具體實現(xiàn)過程為，從永久標記點Vk開始，尋找與其直接連接的所有結(jié)點。此時將Vk點作為直角坐標系下的原點，以Vk點與終點Vt的連線方向作為直角坐標系的X軸方向，由此就可以確定一個與永久標記點Vk和終點Vt有關的有向二維空間。如圖1所示。

在圖1中，與永久標記點Vk直接連接的結(jié)點有四個，將其編號為(1)～(4)，根據(jù)永久標記點Vk和終點Vt的位置關系，我們把二維空間分為四個象限。由于在定義數(shù)據(jù)結(jié)構(gòu)時，己經(jīng)存儲了每個結(jié)點的坐標信息，因此，在這里就可以直接使用這些數(shù)據(jù)。

根據(jù)三角形余弦定理，a2= b2＋c2－2bc×cosθ，其中a、b、c分別為三角形三個邊的長度，θ為邊長為b和c的兩個邊的夾角。我們令b為與永久標記點Vk直接連接的線段的長度，令c為永久標記點Vk與終點Vt的連線長度，θ角為這兩條線之間的夾角。在圖1中，以1號點為例，它是一個與永久標記點Vk直接連接的點，對應的a， b， c三條邊和θ角的均為圖中標識所示。首先，根據(jù)邊的權(quán)值直接得到b的值，再根據(jù)地圖屬性表中SpointX， SpointY和EpointX，EpointY四個域的域值，得到三角形三個頂點的坐標值，進而求得a和c的值，最后利用余弦定理就可以解出θ。對方向性的要求，也就是要求臨時標記點要位于直角坐標系的第一象限和第四象限，即θ值小于或等于90度。在所有的與永久標記結(jié)點直接連接的點中，我們只選擇符合方向性要求的點作為臨時標記點。顯然在圖1中我們只選擇(1)、(2)兩個點標一記為臨時標一記結(jié)點，排除了(3)，(4)兩點。

3.2 優(yōu)化搜索算法流程

圖2為改進算法的流程圖，其中包括了直接插入排序過程和方向性搜索過程。在實際應用中，還包括根據(jù)己有的GIS數(shù)據(jù)，按定義的數(shù)據(jù)結(jié)構(gòu)建立相應的數(shù)據(jù)拓撲關系，然后根據(jù)己有的拓撲結(jié)構(gòu)實現(xiàn)最短路徑的算法。

4 系統(tǒng)應用實例界面

根據(jù)上面提出的改進后的Dijkstra優(yōu)化算法，系統(tǒng)在空間移動信息服務系統(tǒng)中實現(xiàn)了城市交通道路規(guī)劃功能。此功能的實現(xiàn)過程為，當用戶需要最佳路徑時，首先在地圖上確定起點和終點的位置，并查找起點和終點對應位置的結(jié)點編號，繼而向GIS服務器發(fā)出路徑規(guī)劃請求，服務器接到用戶請求后，利用優(yōu)化搜索算法計算出最短路徑，再將規(guī)劃結(jié)果返回到客戶端，客戶端根據(jù)得到的數(shù)據(jù)在地圖中顯示出規(guī)劃結(jié)果，如圖4所示。

■

圖3 最優(yōu)路徑查詢交互界面圖4 最佳路徑實現(xiàn)示意圖

5 結(jié)束語

本文主要描述了傳統(tǒng)空間分析技術(shù)及數(shù)字城管系統(tǒng)中所應用的改進型的空間分析技術(shù)。針對傳統(tǒng)空間分析技術(shù)中關于搜索過程缺乏方向性的問題，為了降低算法復雜度，提高算法效率，我們提出了基于方向性的最短路徑搜索方法，該算法非常易于編程實現(xiàn)。這些算法最后都成功地應用于廈門市數(shù)字城市信息管理系統(tǒng)。

致謝：在此感謝廈門智裕科技有限公司的領導及公司的同事們，謝謝他們在整個項目開展過程中的支持和鼓勵。

參考文獻:

[1] 張宏，溫永寧，劉愛利，等.地理信息系統(tǒng)算法基礎[D].北京：科學出版社，2006.06.