空間分析技術在數字城管系統中的應用

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

關鍵詞：空間分析；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 引言

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

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

2 Dijkstra最優路徑算法

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

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

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

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

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

3.1 優化搜索實現過程

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

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

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

3.2 優化搜索算法流程

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

4 系統應用實例界面

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

■

圖3 最優路徑查詢交互界面圖4 最佳路徑實現示意圖

5 結束語

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

致謝：在此感謝廈門智?？萍加邢薰镜念I導及公司的同事們，謝謝他們在整個項目開展過程中的支持和鼓勵。

參考文獻:

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