城市排水GIS系統拓撲模型的建立

王 萌，史明昌,2

(1. 北京林業大學水土保持學院，北京 100083； 2. 北京地拓科技發展有限公司，北京 100084)

城市排水GIS系統拓撲模型的建立

王 萌1，史明昌1,2

(1. 北京林業大學水土保持學院，北京 100083； 2. 北京地拓科技發展有限公司，北京 100084)

當前的排水管網拓撲模型由于忽略了排水管網的細節特征，致使拓撲關系過于簡單，不能完成特定排水業務模型空間分析，在一定程度上阻礙了排水GIS系統的發展?；趫D論理論，本文提出了城市排水GIS系統細致拓撲模型。首先，基于面向對象方法提出拓撲概念模型和邏輯模型，增加其拓撲關系描述的細節規則，以實現對客觀世界的真實模擬。然后在數據結構設計中，采用十字鏈表作為存儲結構，將其改進并與R+樹進行關聯生成空間索引。在空間分析中，本文基于R+索引和十字鏈表提出了空間查詢和路徑分析典型算法。最后以鎮江市城市排水管網地理信息系統開發為例，對拓撲模型進行了開發實踐。試驗結果表明，本文提出的拓撲模型可以更真實模擬客觀世界，提供更多種空間分析，完成海量數據快速訪問，為實現城市排水GIS系統海量數據的高效空間分析提供解決方案。

排水GIS；空間分析；拓撲模型；R+樹；十字鏈表

隨著建設智慧城市與海綿城市戰略的推進，GIS以其強大的數據管理功能和空間分析特性[1]，在城市排水管理信息系統建設中方興未艾[2]。目前，國內外排水業務模型的研究取得了較為豐碩的成果[3-4]，為城市內澇的模擬、仿真、預警，以及排水管網的科學管理提供解決方案，是未來排水信息化的發展方向。相應的，排水GIS系統也日臻完善，許多城市建立了GIS排水系統，如北京、無錫、南京、太原等城市應用GIS技術設計開發了城市地下管網或城市排水管理信息系統[5]，這種系統實現了管網的信息化管理，能夠進行查詢分析與可視化表達，在一定程度上取代了原有落后的人工管理模式[6]。然而，隨著管理者對排水信息化需求的提高，近年來，希望通過GIS和業務模型相結合的、可實現“地上-地下”一體化空間分析的排水系統越來越受到管理者與學者的關注。這種系統在仿真程度上又提高了一個層次，可以獲得更多的基于空間的非空間信息，如發掘專業信息并應用到防洪決策中[7]。

拓撲模型是對地理實體拓撲關系的抽象描述，是進行空間分析的基礎和依據，直接決定了空間分析的效率[8]。城市排水管網埋在地下，具有隱蔽性和交錯復雜性，它通常是一個由上萬、甚至百萬以上節點組成的有向網絡，其地面覆有各種管網附屬設施。隨著地下管網建設的擴張，基于GIS的管網數據拓撲模型受到嚴峻考驗，這是因為傳統排水系統數據結構可擴充性有限，獲取信息過度依賴于增加數據屬性，數據結構沒有與索引建立聯系，當數據量巨大時，運用SQL語句進行空間查詢和運算會導致系統響應時間長，效率十分低下[9]。

因此，本文運用面向對象的方法建立城市排水GIS系統精細拓撲模型，提出新的拓撲規則，建立管網十字鏈表數據結構，利用R+樹建立空間索引，并以此為基礎提出管網空間分析算法。以鎮江排水系統開發為例，實現了拓撲建模和典型空間分析算法，為城市排水GIS系統拓撲建模提供了一個新方法。

1 拓撲模型

1.1 概念模型

排水系統設施實體包括管線及其附屬設施，分別具有不同的靜態和動態特征，它們均可抽象為對象。在傳統排水管網數據中，排水管網因其單向、無環的特點，通常被抽象為一張有向枝狀圖，各類設施根據圖論原理被抽象為“管線”和“節點”兩類對象。其中節點類包括檢查井、泵站、堰、蓄水池、雨水口、出水口和分流井等設施，管線類包括排水管和排水渠等。事實上，某些節點類對象常存在于地表匯水區或受納體之中，因此排水系統還應包括地表匯水區或受納體面狀區域，這里命名為起始面域類和終止面域類。通過對管網拓撲特征的分析可以發現，不同節點類實體的拓撲特征存在明顯差異。具體表現在：①雨水口必須為管線起點，與地表匯水區是拓撲包含關系；②出水口必須為管線終點，與受納體是拓撲包含關系；③雨水口節點只能存在下游管線；④出水口節點上有且僅有一條管道相連，且只能是上游管線；⑤分流井有且只有兩條下游管線，而其他節點最多有一段下游管線；⑥三通井有三條管線連接，四通井有四條管線連接，五通及以上以此類推；⑦管網系統至少應有一個出水口節點。

為了保證拓撲模型的準確性，根據上述拓撲特征差異，本文將節點進一步細分為多類節點，包括起始節點、終止節點、二通節點、三通節點、四通節點、多通節點和分流節點幾類，這些節點可位于起始面域或終止面域，對應的拓撲關系概念模型如圖1所示。同時，根據排水信息系統業務要求，調蓄池被視為二通節點，蓄水引管作為其上游管線和下游管線。

這里規定雨水箅、閘門、閥門等附屬設施，不單獨作為要素表達，而是被隱性包含在各類對象中，不直接作為某類拓撲對象表示，也不能與其他對象直接拓撲連接。也就是排水管網設施抽象的各類對象，均是以某種簡單對象為主，并包含相應附屬設施對象的復雜對象。如雨水口對象是包含雨水口和雨水箅在內的復雜對象，統一抽象為起始節點類對象處理，而雨水箅不參與拓撲建模。

圖1 拓撲關系概念模型

1.2 邏輯結構

根據面向對象程序設計方法，對面域、節點和管線三類對象進行描述，采用統一建模語言將各類關系進行拓撲表達，所得類間邏輯關系如圖2所示。除此之外，還需規定每類對象的拓撲規則。在圖2中，定義拓撲規則為：管線類Pineline是一組管線對象的集合，每條管線必須有且只有兩個節點對象與之相關聯。起始節點類StartNode是一組起始節點的集合，一個起始節點無上游管線，有且只有一條下游管線，起始面域與起始節點是一對多的拓撲包含關系。二通節點類CockNode是一組二通節點的集合，一個二通節點有且僅有兩條管線與之拓撲關聯，一條為上游管線，一條為下游管線。三通節點類TconnectorNode是一組三通節點的集合，一個三通節點有且僅有3條管線與之拓撲關聯，2條為上游管線，1條為下游管線。四通節點類FourconnectorNode是一組四通節點的集合，一個四通節點有且只有4條管線與之拓撲關聯，3條為上游管線，1條為下游管線。多通節點類MultipleNode的集合是一組多通節點的集合，一個多通節點有p(p>4,p∈Z*)條管線與之拓撲關聯，p-1條為上游管線，一條為下游管線。分流節點類是一組分流節點的集合，一個分流節點有q(q>2,q∈Z*)條管線與之拓撲關聯，q-2條為上游管線，兩條為下游管線。終止節點類EndNode是一組終止節點的集合，一個終止節點無下游管線，有r(r∈Z*)條上游管線與之拓撲關聯。起始面域類StartArea是一組起始面域的集合，一個起始面域可以包含多個起始節點。終止面域類EndArea是一組終止面域的集合，一個終止面域可以包含多個終止節點。排水管網拓撲模型是由以上所有類及類之間的拓撲關系構成。

圖2 邏輯模型

1.3 存儲結構

1.3.1 排水GIS數據結構

目前，在給水、電力等行業管網的應用中，圖的存儲主要采用鄰接矩陣和鄰接表兩種結構[10]。由于鄰接矩陣會隨著數據量的增加出現數據冗余，鄰接表只能存儲下游邊數據，因此二者不是理想的排水GIS數據結構。相比之下，十字鏈表是一種結合了有向圖鄰接表和逆鄰接表的鏈式結構[11]，可以同時存儲節點的上游和下游信息，且建立十字鏈表的時間復雜度和建立鄰接表是相同的[12]，因此十字鏈表作為排水系統拓撲模型是比較合適的。

弧結點有兩個數據域tailvex和headvex，分別指示弧的上下游兩個關聯節點在有向圖中的位置，兩個鏈域hlink和tlink，分別指向弧頭或弧尾相同的下一條弧，info域用于指向該弧的相關信息。頂點結點是鏈表的頭結點，由一個數據域和兩個鏈域構成，頂點數據域data用于存儲與節點相關的信息，鏈域firstin和firstout分別指向該節點的第一個上游或下游弧。圖3為圖1拓撲模型的十字鏈表結構。

頂點結點的firstin鏈域和firstout鏈域分別指向該節點的上游和下游節點。由此可以得出：起始節點(V1、V2、V6、V8)的firstin鏈域為空，除分流節點(V5)firstout鏈域指向兩個弧結點、終止節點(V9、V10)firstout鏈域為空之外，其他類節點的firstout鏈域均僅指向一個對應于該節點的弧結點。

弧結點鏈域的數量表示與該節點關聯的管線條數。hlink鏈域指向弧頭相同的下一條弧，即依次指向某頂點的所有上游弧結點，直到指向的弧結點的hlink鏈域為空。同理tlink鏈域依次指向某頂點的所有下游弧結點。因此，對于二通節點(V3)，其上游和下游指向的弧結點個數均為1；三通節點(V7)指向的上游弧結點個數為2，下游弧結點個數為1；四通節點(V4)指向的上游弧結點個數為3，下游弧結點個數為1；多通節點以此類推。

1.3.2 R+樹索引

十字鏈表用于空間分析，傳統的方法是SQL查詢，將按鏈表一直拉到底，可以生成相應方向的路徑[13]。這種方法雖然簡單，但是并不高效，尤其是數據量達到城市級時，計算方法緩慢，因此需要改進。由于R+樹對數據項和索引項的填充個數沒有嚴格的限制，中間結點之間不能相互重疊，當搜索某個對象的時候，從多個結點都可以定位到該對象[14]，因此可以通過改造十字鏈表實現索引。

圖3 排水管網十字鏈表

十字鏈表若支持R+樹索引，尚需解決二個問題：①鏈表的數據域必須增加索引信息；②建立鏈表組合結構，將索引信息賦予十字鏈表數據域。第1個問題比較簡單，可以在鏈表數據結構中增加索引，也就是在定點結點data域下增加指向所屬R+樹的指針WhichRPlus，即VertexNode->data->WhichRPlus=Null，待R+樹建立后賦予相應信息。

R+樹索引的數據為對象，前述的節點、管線、面域結構需要統一數據結構，作為R+樹葉結點的訪問對象，由于面域結構與節點是重合關聯的，而節點隱含于弧段結構中，因此封裝對象可統一為管線組合結構，它最少包括一條管線(圖4中R15內數據)，最多可包括多條管線(圖4中R3內數據)。文獻[7]封裝了Larcl管線結構，因此可將Larcl管線結構再次封裝，建立適合于R+樹索引的數據結構。葉結點數據可以通過聲明一個PipelineCompound類實現，聲明代碼如下：

Class PipelineCompound

{

CArrayLarclID; ∥組成PipelineCompound的Larcl對象ID集合

long larclNum; ∥Larcl對象數目

long PipelineCompoundID; ∥PipelineCompound的ID

CRect Rect; ∥PipelineCompound的MBR

CRect upRect; ∥PipelineCompound上層樹的MBR

CRect downRect; ∥PipelineCompound下層樹的MBR

bool isVisitedFLAG; ∥是否被訪問過

bool isIndexCompleted; ∥索引是否建立

bool isIndexCleared; ∥索引是否被清除

bool isRegistered；∥是否對頂點結點注冊索引

};

圖4 排水管網的R+索引

PipelineCompound類是葉結點數據對象，由于管線數據Larcl封裝其內，因此可以對管線數據和十字鏈表數據進行訪問，更新鏈表數據結構中info信息。R+樹生成后，區域內的排水管線R+樹如圖5所示，其中只有葉結點R3、R10、R11、R12、R13、R14、R15包含PipelineCompound類數據，其他非葉結點存儲最小外接矩形MBR和指向下、上級結點的指針。由于R+樹中不允許中間結點重合，搜索時可以不用遍歷各個結點，因此速度較R樹索引有所提升。

2 空間分析算法

2.1 空間查詢

空間查詢包括節點的上下游節點查詢、節點的上下游管線查詢、管線的上下游節點查詢和管線的上下游管線查詢。基于R+索引的查詢算法過程為：首先通過查詢區域確定R+樹結點PipelineCompound數據，進而訪問十字鏈表結構的管線數據和弧段數據，最終完成查詢。以節點Vi的上下游查詢算法為例，首先通過R+樹搜索到PipelineCompound對象，然后找到十字鏈表中節點Vi對應的頂點結點，其firstin域指向的邊結點為Vi的上游管線，該邊結點的tailvex鏈域指向的頂點結點為Vi的上游節點，firstout域指向的邊結點為Vi的下游管線，該邊結點的headvex鏈域指向的頂點結點為Vi的下游節點。

圖5 連通性分析算法

2.2 路徑分析

城市排水GIS系統空間分析的核心是管網的路徑分析，GIS排水系統應能提供對管網網絡拓撲結構進行連通性分析、上下游分析，并能提供管網橫縱斷面圖的瀏覽查詢功能[7]。將空間分析與排水業務模型[15]結合還可獲得更多類型的空間分析，如當暴雨來臨時，對排水過程進行仿真模擬，以確認積水的排除時間并考慮是否啟用其他輔助排水措施。在諸多空間分析中，排水管網的連通性分析是一項非常重要的內容，管網的連通性是進行管網水力計算的先決條件，也是爆管分析的重要環節[16]。圖5描述了基于排水GIS系統的連通性分析算法流程。

3 模型應用

基于前述的地下管網拓撲模型及算法，本文以鎮江市城市排水管網地理信息系統開發為例，在VC++編程環境中，利用GIS組件開發了城市排水GIS系統。系統的空間分析模塊包括上下游分析、連通性分析、淹沒分析、縱斷面分析和水質分析，突破了排水GIS系統地下資產管理的局限性，實現了“地上-地下”一體化的排水分析理念?？臻g分析模塊是以拓撲數據模型為核心，開發業務模型接口，一并封裝為DLL插件，在分析時調用插件對空間數據庫中的排水系統數據進行計算。

圖6為鎮江市排水GIS系統連通性分析界面，應用本文描述的拓撲模型，采用十字鏈表數據結構實現了節點的上下游節點查詢、節點的上下游管線查詢算法，程序運行前需要設定管線的起點和終點，然后按照前文描述的過程進行查找，最終確定起終點路徑的聯通性。如圖6從管線始節點Y74813開始，沿著向右路徑尋找到終節點Y50437，歷經9個節點、10段管線，可以發現，本文提出的拓撲模型能夠有效進行排水管網的連通性分析。

圖6 鎮江市城市排水GIS系統

為了檢驗R+索引的效率，這里以一定面積范圍內的某條管線段搜索為例，分別在SQL和R+索引中對時間效率進行評價，其評價結果見表1。從表1分析可得，在面積較小的范圍內，如0.67、1.46 km2，傳統SQL查詢和R+索引查詢差距不大，SQL甚至略優于R+索引，但隨著面積的增加(管線數據量增加)，R+索引查詢顯示出較大優勢，當面積為12.59 km2時，R+索引訪問效率是SQL的3倍多。因此，在數據量較大條件下，R+索引比SQL具有更高的數據訪問效率。

表1 R+索引效率分析

4 結 語

隨著城市排水管網信息化的發展，用戶需要GIS排水系統更加智能化，能夠為排水管理輔助信息和解決方案，傳統的GIS排水系統由于拓撲模型簡單，無法完成這些細節需求。因此，本文采用面向對象方法描述城市排水GIS系統拓撲模型，構建了基于R+樹的空間索引，研究了GIS排水系統的空間分析典型算法，得出結論如下：

(1) 本文細化了傳統“管線”與“節點”模型，并提出相應拓撲規則，如將節點分為起始節點、終止節點、二通節點等幾類，規定其上、下游拓撲規則。此外，首次將匯水區和受納體等地表對象封裝為“起始面域”“終止面域”納入拓撲模型中考慮，為實現“地上-地下”的一體化分析提供基礎。試驗證明，細化的GIS管線拓撲模型更貼近客觀世界，這種拓撲關系可提供更豐富的空間分析類型，便于建立水務模型空間分析。

(2) 為避免海量排水管網數據SQL查詢引起的響應時間延長、效率低下問題，本文基于地下管網數據建立了R+索引，提出了管線復合體結構，作為索引的基本對象。同時改進了十字鏈表數據結構，使之與R+索引關聯，提高了訪問管線數據的效率，為空間分析與數據動態更新提供技術依據，這對于海量數據的訪問與更新具有重要意義。

(3) 節點查詢是管線查詢與空間分析的基礎，系統開發試驗表明，基于R+索引下的十字鏈表可將有向圖鄰接表和逆鄰接表結合起來，能夠進行雙向訪問，可以很好地完成各種管線路徑分析，并保證分析結果的正確性，如地下管網連通性分析等。

[1] SCHOLTEN H J,STILLWELL J.Geographical Information Systems for Urban and Regional Planning[M]. Netherlands:Springer Science & Business Media, 2013.

[2] 馬駿, 劉興坡. 城市排水GIS 數據分析與組織[J]. 中國市政工程,2006(3):36-38.

[3] GREENE R, AGBENOWOSI N, LOGANATHAN G V. GIS-based Approach to Sewer System Design[J]. Journal of Surveying Engineering, 1999, 125(1): 36-57.

[4] SAEGROV S,SCHILLING W.Computer Aided Rehabilitation of Sewer and Storm Water Networks[J]. Bridges, 2002, 10(40644): 88.

[5] 路玲玲,吳曉明,任杰. 城市地下管網信息管理問題研究[J].地域研究與開發,2008, 27(2):47-50.

[6] 趙新華,李瓊.城市排水管網信息GIS管理系統設計[J].中國給水排水, 2002, 18(9): 55-57.

[7] 彭歡.城市排水 GIS 系統研究[D].北京:北京林業大學,2014.

[8] 張小蘭,陳曉翔,黃敏. 面向指路標志系統的交通網絡數據模型及應用[J]. 地理與地理信息科學,2006(6):45-47,74.

[9] 程雷陽.電力GIS電網拓撲模型的研究與實現[D].北京:華北電力大學, 2013.

[10] 張靜文, 周杉. 面向對象技術實現活動網絡圖及關鍵路徑算法[J]. 計算機工程與應用, 2016, 52(4): 234-237.

[11] 蔚潔. 車輛監控導航系統中最短路徑的實時性研究[D]. 石家莊:河北師范大學, 2007.

[12] DROZDER A. Data Structures and Algorithms in C++[M]. 3rded. Hoboken：John Wiley & Sons Inc, 2006.

[13] 楊思吉, 吳保國. 森林資源時空數據異步更新與回溯算法研究[J]. 地理與地理信息科學, 2014, 30(3): 37-41.

[14] 張澤寶. 空間數據庫的索引技術研究[D].哈爾濱:哈爾濱工程大學,2009:24-28.

[15] 李亞君. 基于 GIS 的三維地下管網爆管分析及其系統的設計與實現[D].成都:電子科技大學, 2015.

[16] 鄭云龍, 鄒大偉, 李紅艷. 基于 SuperMap 平臺下的排水規劃管理系統開發[J]. 測繪與空間地理信息, 2013, 36(11): 159-161.

Study on Topology Model of Urban Drainage GIS System

WANG Meng1,SHI Mingchang1,2

(1. School of Soil and Water Conservation, Beijing Forestry University, Beijing 100083, China;2. Beijing Datum Technology Development Ltd., Beijing 100084, China)

Current drainage network topology model is too simple to complete the spatial analysis for specific drainage business because of neglecting the details of the drainage network.To some extent,it hinderes the development of the drainage GIS system.Based on graph theory, the detailed topology model of urban drainage GIS system was presented in this paper.Firstly,on the basis of the object oriented method, topological concept model and logical model were put forward, which the detailed rules of the topological relation were increased so as to really simulate the objective world.In the design of data structure,orthogonal list was adopted as a storage structure,and it was also improved as well as linked with R+tree in order to generate spatial index.During spatial analysis designing, the typical algorithm of spatial query and path analysis based on R+index and orthogonal list was presented .With the example for development of Zhenjiang city drainage network geographic information system, the practice was carried out.Experiments show that the topology model proposed in this paper can better simulate the objective world,provide more spatial analysis, realize rapid access to huge data,and make a solution for efficient space analysis of city drainage system GIS that combined with huge data.

drainage GIS; spatial analysis; topology model; R+tree; orthogonal list

王萌，史明昌.城市排水GIS系統拓撲模型的建立[J].測繪通報，2017(8)：129-134.

10.13474/j.cnki.11-2246.2017.0270.

2016-10-24

國家水體污染控制與治理科技重大專項(2013ZX07304)

王萌(1991—)，女，碩士生，主要從事3S系統集成與開發。 E-mail： wm_20161010@163.com

P208

A

0494-0911(2017)08-0129-06