城市排水GIS系統(tǒng)拓?fù)淠Ｐ偷慕?/h1>
2017-08-30 10:09:10史明昌
測(cè)繪通報(bào) 2017年8期
王 萌，史明昌,2
(1. 北京林業(yè)大學(xué)水土保持學(xué)院，北京 100083； 2. 北京地拓科技發(fā)展有限公司，北京 100084)
城市排水GIS系統(tǒng)拓?fù)淠Ｐ偷慕?/p>
王 萌1，史明昌1,2
(1. 北京林業(yè)大學(xué)水土保持學(xué)院，北京 100083； 2. 北京地拓科技發(fā)展有限公司，北京 100084)
當(dāng)前的排水管網(wǎng)拓?fù)淠Ｐ陀捎诤雎粤伺潘芫W(wǎng)的細(xì)節(jié)特征，致使拓?fù)潢P(guān)系過于簡(jiǎn)單，不能完成特定排水業(yè)務(wù)模型空間分析，在一定程度上阻礙了排水GIS系統(tǒng)的發(fā)展?；趫D論理論，本文提出了城市排水GIS系統(tǒng)細(xì)致拓?fù)淠Ｐ?。首先，基于面向?qū)ο蠓椒ㄌ岢鐾負(fù)涓拍钅Ｐ秃瓦壿嬆Ｐ?，增加其拓?fù)潢P(guān)系描述的細(xì)節(jié)規(guī)則，以實(shí)現(xiàn)對(duì)客觀世界的真實(shí)模擬。然后在數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)中，采用十字鏈表作為存儲(chǔ)結(jié)構(gòu)，將其改進(jìn)并與R+樹進(jìn)行關(guān)聯(lián)生成空間索引。在空間分析中，本文基于R+索引和十字鏈表提出了空間查詢和路徑分析典型算法。最后以鎮(zhèn)江市城市排水管網(wǎng)地理信息系統(tǒng)開發(fā)為例，對(duì)拓?fù)淠Ｐ瓦M(jìn)行了開發(fā)實(shí)踐。試驗(yàn)結(jié)果表明，本文提出的拓?fù)淠Ｐ涂梢愿鎸?shí)模擬客觀世界，提供更多種空間分析，完成海量數(shù)據(jù)快速訪問，為實(shí)現(xiàn)城市排水GIS系統(tǒng)海量數(shù)據(jù)的高效空間分析提供解決方案。
排水GIS；空間分析；拓?fù)淠Ｐ?；R+樹；十字鏈表
隨著建設(shè)智慧城市與海綿城市戰(zhàn)略的推進(jìn)，GIS以其強(qiáng)大的數(shù)據(jù)管理功能和空間分析特性[1]，在城市排水管理信息系統(tǒng)建設(shè)中方興未艾[2]。目前，國(guó)內(nèi)外排水業(yè)務(wù)模型的研究取得了較為豐碩的成果[3-4]，為城市內(nèi)澇的模擬、仿真、預(yù)警，以及排水管網(wǎng)的科學(xué)管理提供解決方案，是未來排水信息化的發(fā)展方向。相應(yīng)的，排水GIS系統(tǒng)也日臻完善，許多城市建立了GIS排水系統(tǒng)，如北京、無錫、南京、太原等城市應(yīng)用GIS技術(shù)設(shè)計(jì)開發(fā)了城市地下管網(wǎng)或城市排水管理信息系統(tǒng)[5]，這種系統(tǒng)實(shí)現(xiàn)了管網(wǎng)的信息化管理，能夠進(jìn)行查詢分析與可視化表達(dá)，在一定程度上取代了原有落后的人工管理模式[6]。然而，隨著管理者對(duì)排水信息化需求的提高，近年來，希望通過GIS和業(yè)務(wù)模型相結(jié)合的、可實(shí)現(xiàn)“地上-地下”一體化空間分析的排水系統(tǒng)越來越受到管理者與學(xué)者的關(guān)注。這種系統(tǒng)在仿真程度上又提高了一個(gè)層次，可以獲得更多的基于空間的非空間信息，如發(fā)掘?qū)I(yè)信息并應(yīng)用到防洪決策中[7]。
拓?fù)淠Ｐ褪菍?duì)地理實(shí)體拓?fù)潢P(guān)系的抽象描述，是進(jìn)行空間分析的基礎(chǔ)和依據(jù)，直接決定了空間分析的效率[8]。城市排水管網(wǎng)埋在地下，具有隱蔽性和交錯(cuò)復(fù)雜性，它通常是一個(gè)由上萬、甚至百萬以上節(jié)點(diǎn)組成的有向網(wǎng)絡(luò)，其地面覆有各種管網(wǎng)附屬設(shè)施。隨著地下管網(wǎng)建設(shè)的擴(kuò)張，基于GIS的管網(wǎng)數(shù)據(jù)拓?fù)淠Ｐ褪艿絿?yán)峻考驗(yàn)，這是因?yàn)閭鹘y(tǒng)排水系統(tǒng)數(shù)據(jù)結(jié)構(gòu)可擴(kuò)充性有限，獲取信息過度依賴于增加數(shù)據(jù)屬性，數(shù)據(jù)結(jié)構(gòu)沒有與索引建立聯(lián)系，當(dāng)數(shù)據(jù)量巨大時(shí)，運(yùn)用SQL語句進(jìn)行空間查詢和運(yùn)算會(huì)導(dǎo)致系統(tǒng)響應(yīng)時(shí)間長(zhǎng)，效率十分低下[9]。
因此，本文運(yùn)用面向?qū)ο蟮姆椒ń⒊鞘信潘瓽IS系統(tǒng)精細(xì)拓?fù)淠Ｐ?，提出新的拓?fù)湟?guī)則，建立管網(wǎng)十字鏈表數(shù)據(jù)結(jié)構(gòu)，利用R+樹建立空間索引，并以此為基礎(chǔ)提出管網(wǎng)空間分析算法。以鎮(zhèn)江排水系統(tǒng)開發(fā)為例，實(shí)現(xiàn)了拓?fù)浣：偷湫涂臻g分析算法，為城市排水GIS系統(tǒng)拓?fù)浣Ｌ峁┝艘粋€(gè)新方法。
1 拓?fù)淠Ｐ?/h2>
1.1 概念模型
排水系統(tǒng)設(shè)施實(shí)體包括管線及其附屬設(shè)施，分別具有不同的靜態(tài)和動(dòng)態(tài)特征，它們均可抽象為對(duì)象。在傳統(tǒng)排水管網(wǎng)數(shù)據(jù)中，排水管網(wǎng)因其單向、無環(huán)的特點(diǎn)，通常被抽象為一張有向枝狀圖，各類設(shè)施根據(jù)圖論原理被抽象為“管線”和“節(jié)點(diǎn)”兩類對(duì)象。其中節(jié)點(diǎn)類包括檢查井、泵站、堰、蓄水池、雨水口、出水口和分流井等設(shè)施，管線類包括排水管和排水渠等。事實(shí)上，某些節(jié)點(diǎn)類對(duì)象常存在于地表匯水區(qū)或受納體之中，因此排水系統(tǒng)還應(yīng)包括地表匯水區(qū)或受納體面狀區(qū)域，這里命名為起始面域類和終止面域類。通過對(duì)管網(wǎng)拓?fù)涮卣鞯姆治隹梢园l(fā)現(xiàn)，不同節(jié)點(diǎn)類實(shí)體的拓?fù)涮卣鞔嬖诿黠@差異。具體表現(xiàn)在：①雨水口必須為管線起點(diǎn)，與地表匯水區(qū)是拓?fù)浒P(guān)系；②出水口必須為管線終點(diǎn)，與受納體是拓?fù)浒P(guān)系；③雨水口節(jié)點(diǎn)只能存在下游管線；④出水口節(jié)點(diǎn)上有且僅有一條管道相連，且只能是上游管線；⑤分流井有且只有兩條下游管線，而其他節(jié)點(diǎn)最多有一段下游管線；⑥三通井有三條管線連接，四通井有四條管線連接，五通及以上以此類推；⑦管網(wǎng)系統(tǒng)至少應(yīng)有一個(gè)出水口節(jié)點(diǎn)。
為了保證拓?fù)淠Ｐ偷臏?zhǔn)確性，根據(jù)上述拓?fù)涮卣鞑町?，本文將?jié)點(diǎn)進(jìn)一步細(xì)分為多類節(jié)點(diǎn)，包括起始節(jié)點(diǎn)、終止節(jié)點(diǎn)、二通節(jié)點(diǎn)、三通節(jié)點(diǎn)、四通節(jié)點(diǎn)、多通節(jié)點(diǎn)和分流節(jié)點(diǎn)幾類，這些節(jié)點(diǎn)可位于起始面域或終止面域，對(duì)應(yīng)的拓?fù)潢P(guān)系概念模型如圖1所示。同時(shí)，根據(jù)排水信息系統(tǒng)業(yè)務(wù)要求，調(diào)蓄池被視為二通節(jié)點(diǎn)，蓄水引管作為其上游管線和下游管線。
這里規(guī)定雨水箅、閘門、閥門等附屬設(shè)施，不單獨(dú)作為要素表達(dá)，而是被隱性包含在各類對(duì)象中，不直接作為某類拓?fù)鋵?duì)象表示，也不能與其他對(duì)象直接拓?fù)溥B接。也就是排水管網(wǎng)設(shè)施抽象的各類對(duì)象，均是以某種簡(jiǎn)單對(duì)象為主，并包含相應(yīng)附屬設(shè)施對(duì)象的復(fù)雜對(duì)象。如雨水口對(duì)象是包含雨水口和雨水箅在內(nèi)的復(fù)雜對(duì)象，統(tǒng)一抽象為起始節(jié)點(diǎn)類對(duì)象處理，而雨水箅不參與拓?fù)浣！?/p>
圖1 拓?fù)潢P(guān)系概念模型
1.2 邏輯結(jié)構(gòu)
根據(jù)面向?qū)ο蟪绦蛟O(shè)計(jì)方法，對(duì)面域、節(jié)點(diǎn)和管線三類對(duì)象進(jìn)行描述，采用統(tǒng)一建模語言將各類關(guān)系進(jìn)行拓?fù)浔磉_(dá)，所得類間邏輯關(guān)系如圖2所示。除此之外，還需規(guī)定每類對(duì)象的拓?fù)湟?guī)則。在圖2中，定義拓?fù)湟?guī)則為：管線類Pineline是一組管線對(duì)象的集合，每條管線必須有且只有兩個(gè)節(jié)點(diǎn)對(duì)象與之相關(guān)聯(lián)。起始節(jié)點(diǎn)類StartNode是一組起始節(jié)點(diǎn)的集合，一個(gè)起始節(jié)點(diǎn)無上游管線，有且只有一條下游管線，起始面域與起始節(jié)點(diǎn)是一對(duì)多的拓?fù)浒P(guān)系。二通節(jié)點(diǎn)類CockNode是一組二通節(jié)點(diǎn)的集合，一個(gè)二通節(jié)點(diǎn)有且僅有兩條管線與之拓?fù)潢P(guān)聯(lián)，一條為上游管線，一條為下游管線。三通節(jié)點(diǎn)類TconnectorNode是一組三通節(jié)點(diǎn)的集合，一個(gè)三通節(jié)點(diǎn)有且僅有3條管線與之拓?fù)潢P(guān)聯(lián)，2條為上游管線，1條為下游管線。四通節(jié)點(diǎn)類FourconnectorNode是一組四通節(jié)點(diǎn)的集合，一個(gè)四通節(jié)點(diǎn)有且只有4條管線與之拓?fù)潢P(guān)聯(lián)，3條為上游管線，1條為下游管線。多通節(jié)點(diǎn)類MultipleNode的集合是一組多通節(jié)點(diǎn)的集合，一個(gè)多通節(jié)點(diǎn)有p(p>4,p∈Z*)條管線與之拓?fù)潢P(guān)聯(lián)，p-1條為上游管線，一條為下游管線。分流節(jié)點(diǎn)類是一組分流節(jié)點(diǎn)的集合，一個(gè)分流節(jié)點(diǎn)有q(q>2,q∈Z*)條管線與之拓?fù)潢P(guān)聯(lián)，q-2條為上游管線，兩條為下游管線。終止節(jié)點(diǎn)類EndNode是一組終止節(jié)點(diǎn)的集合，一個(gè)終止節(jié)點(diǎn)無下游管線，有r(r∈Z*)條上游管線與之拓?fù)潢P(guān)聯(lián)。起始面域類StartArea是一組起始面域的集合，一個(gè)起始面域可以包含多個(gè)起始節(jié)點(diǎn)。終止面域類EndArea是一組終止面域的集合，一個(gè)終止面域可以包含多個(gè)終止節(jié)點(diǎn)。排水管網(wǎng)拓?fù)淠Ｐ褪怯梢陨纤蓄惣邦愔g的拓?fù)潢P(guān)系構(gòu)成。
圖2 邏輯模型
1.3 存儲(chǔ)結(jié)構(gòu)
1.3.1 排水GIS數(shù)據(jù)結(jié)構(gòu)
目前，在給水、電力等行業(yè)管網(wǎng)的應(yīng)用中，圖的存儲(chǔ)主要采用鄰接矩陣和鄰接表兩種結(jié)構(gòu)[10]。由于鄰接矩陣會(huì)隨著數(shù)據(jù)量的增加出現(xiàn)數(shù)據(jù)冗余，鄰接表只能存儲(chǔ)下游邊數(shù)據(jù)，因此二者不是理想的排水GIS數(shù)據(jù)結(jié)構(gòu)。相比之下，十字鏈表是一種結(jié)合了有向圖鄰接表和逆鄰接表的鏈?zhǔn)浇Y(jié)構(gòu)[11]，可以同時(shí)存儲(chǔ)節(jié)點(diǎn)的上游和下游信息，且建立十字鏈表的時(shí)間復(fù)雜度和建立鄰接表是相同的[12]，因此十字鏈表作為排水系統(tǒng)拓?fù)淠Ｐ褪潜容^合適的。
弧結(jié)點(diǎn)有兩個(gè)數(shù)據(jù)域tailvex和headvex，分別指示弧的上下游兩個(gè)關(guān)聯(lián)節(jié)點(diǎn)在有向圖中的位置，兩個(gè)鏈域hlink和tlink，分別指向弧頭或弧尾相同的下一條弧，info域用于指向該弧的相關(guān)信息。頂點(diǎn)結(jié)點(diǎn)是鏈表的頭結(jié)點(diǎn)，由一個(gè)數(shù)據(jù)域和兩個(gè)鏈域構(gòu)成，頂點(diǎn)數(shù)據(jù)域data用于存儲(chǔ)與節(jié)點(diǎn)相關(guān)的信息，鏈域firstin和firstout分別指向該節(jié)點(diǎn)的第一個(gè)上游或下游弧。圖3為圖1拓?fù)淠Ｐ偷氖宙湵斫Y(jié)構(gòu)。
頂點(diǎn)結(jié)點(diǎn)的firstin鏈域和firstout鏈域分別指向該節(jié)點(diǎn)的上游和下游節(jié)點(diǎn)。由此可以得出：起始節(jié)點(diǎn)(V1、V2、V6、V8)的firstin鏈域?yàn)榭?，除分流?jié)點(diǎn)(V5)firstout鏈域指向兩個(gè)弧結(jié)點(diǎn)、終止節(jié)點(diǎn)(V9、V10)firstout鏈域?yàn)榭罩猓渌惞?jié)點(diǎn)的firstout鏈域均僅指向一個(gè)對(duì)應(yīng)于該節(jié)點(diǎn)的弧結(jié)點(diǎn)。
弧結(jié)點(diǎn)鏈域的數(shù)量表示與該節(jié)點(diǎn)關(guān)聯(lián)的管線條數(shù)。hlink鏈域指向弧頭相同的下一條弧，即依次指向某頂點(diǎn)的所有上游弧結(jié)點(diǎn)，直到指向的弧結(jié)點(diǎn)的hlink鏈域?yàn)榭铡Ｍ韙link鏈域依次指向某頂點(diǎn)的所有下游弧結(jié)點(diǎn)。因此，對(duì)于二通節(jié)點(diǎn)(V3)，其上游和下游指向的弧結(jié)點(diǎn)個(gè)數(shù)均為1；三通節(jié)點(diǎn)(V7)指向的上游弧結(jié)點(diǎn)個(gè)數(shù)為2，下游弧結(jié)點(diǎn)個(gè)數(shù)為1；四通節(jié)點(diǎn)(V4)指向的上游弧結(jié)點(diǎn)個(gè)數(shù)為3，下游弧結(jié)點(diǎn)個(gè)數(shù)為1；多通節(jié)點(diǎn)以此類推。
1.3.2 R+樹索引
十字鏈表用于空間分析，傳統(tǒng)的方法是SQL查詢，將按鏈表一直拉到底，可以生成相應(yīng)方向的路徑[13]。這種方法雖然簡(jiǎn)單，但是并不高效，尤其是數(shù)據(jù)量達(dá)到城市級(jí)時(shí)，計(jì)算方法緩慢，因此需要改進(jìn)。由于R+樹對(duì)數(shù)據(jù)項(xiàng)和索引項(xiàng)的填充個(gè)數(shù)沒有嚴(yán)格的限制，中間結(jié)點(diǎn)之間不能相互重疊，當(dāng)搜索某個(gè)對(duì)象的時(shí)候，從多個(gè)結(jié)點(diǎn)都可以定位到該對(duì)象[14]，因此可以通過改造十字鏈表實(shí)現(xiàn)索引。
圖3 排水管網(wǎng)十字鏈表
十字鏈表若支持R+樹索引，尚需解決二個(gè)問題：①鏈表的數(shù)據(jù)域必須增加索引信息；②建立鏈表組合結(jié)構(gòu)，將索引信息賦予十字鏈表數(shù)據(jù)域。第1個(gè)問題比較簡(jiǎn)單，可以在鏈表數(shù)據(jù)結(jié)構(gòu)中增加索引，也就是在定點(diǎn)結(jié)點(diǎn)data域下增加指向所屬R+樹的指針WhichRPlus，即VertexNode->data->WhichRPlus=Null，待R+樹建立后賦予相應(yīng)信息。
R+樹索引的數(shù)據(jù)為對(duì)象，前述的節(jié)點(diǎn)、管線、面域結(jié)構(gòu)需要統(tǒng)一數(shù)據(jù)結(jié)構(gòu)，作為R+樹葉結(jié)點(diǎn)的訪問對(duì)象，由于面域結(jié)構(gòu)與節(jié)點(diǎn)是重合關(guān)聯(lián)的，而節(jié)點(diǎn)隱含于弧段結(jié)構(gòu)中，因此封裝對(duì)象可統(tǒng)一為管線組合結(jié)構(gòu)，它最少包括一條管線(圖4中R15內(nèi)數(shù)據(jù))，最多可包括多條管線(圖4中R3內(nèi)數(shù)據(jù))。文獻(xiàn)[7]封裝了Larcl管線結(jié)構(gòu)，因此可將Larcl管線結(jié)構(gòu)再次封裝，建立適合于R+樹索引的數(shù)據(jù)結(jié)構(gòu)。葉結(jié)點(diǎn)數(shù)據(jù)可以通過聲明一個(gè)PipelineCompound類實(shí)現(xiàn)，聲明代碼如下：
Class PipelineCompound
{
CArrayLarclID; ∥組成PipelineCompound的Larcl對(duì)象ID集合
long larclNum; ∥Larcl對(duì)象數(shù)目
long PipelineCompoundID; ∥PipelineCompound的ID
CRect Rect; ∥PipelineCompound的MBR
CRect upRect; ∥PipelineCompound上層樹的MBR
CRect downRect; ∥PipelineCompound下層樹的MBR
bool isVisitedFLAG; ∥是否被訪問過
bool isIndexCompleted; ∥索引是否建立
bool isIndexCleared; ∥索引是否被清除
bool isRegistered；∥是否對(duì)頂點(diǎn)結(jié)點(diǎn)注冊(cè)索引
};
圖4 排水管網(wǎng)的R+索引
PipelineCompound類是葉結(jié)點(diǎn)數(shù)據(jù)對(duì)象，由于管線數(shù)據(jù)Larcl封裝其內(nèi)，因此可以對(duì)管線數(shù)據(jù)和十字鏈表數(shù)據(jù)進(jìn)行訪問，更新鏈表數(shù)據(jù)結(jié)構(gòu)中info信息。R+樹生成后，區(qū)域內(nèi)的排水管線R+樹如圖5所示，其中只有葉結(jié)點(diǎn)R3、R10、R11、R12、R13、R14、R15包含PipelineCompound類數(shù)據(jù)，其他非葉結(jié)點(diǎn)存儲(chǔ)最小外接矩形MBR和指向下、上級(jí)結(jié)點(diǎn)的指針。由于R+樹中不允許中間結(jié)點(diǎn)重合，搜索時(shí)可以不用遍歷各個(gè)結(jié)點(diǎn)，因此速度較R樹索引有所提升。
2 空間分析算法
2.1 空間查詢
空間查詢包括節(jié)點(diǎn)的上下游節(jié)點(diǎn)查詢、節(jié)點(diǎn)的上下游管線查詢、管線的上下游節(jié)點(diǎn)查詢和管線的上下游管線查詢?；赗+索引的查詢算法過程為：首先通過查詢區(qū)域確定R+樹結(jié)點(diǎn)PipelineCompound數(shù)據(jù)，進(jìn)而訪問十字鏈表結(jié)構(gòu)的管線數(shù)據(jù)和弧段數(shù)據(jù)，最終完成查詢。以節(jié)點(diǎn)Vi的上下游查詢算法為例，首先通過R+樹搜索到PipelineCompound對(duì)象，然后找到十字鏈表中節(jié)點(diǎn)Vi對(duì)應(yīng)的頂點(diǎn)結(jié)點(diǎn)，其firstin域指向的邊結(jié)點(diǎn)為Vi的上游管線，該邊結(jié)點(diǎn)的tailvex鏈域指向的頂點(diǎn)結(jié)點(diǎn)為Vi的上游節(jié)點(diǎn)，firstout域指向的邊結(jié)點(diǎn)為Vi的下游管線，該邊結(jié)點(diǎn)的headvex鏈域指向的頂點(diǎn)結(jié)點(diǎn)為Vi的下游節(jié)點(diǎn)。
圖5 連通性分析算法
2.2 路徑分析
城市排水GIS系統(tǒng)空間分析的核心是管網(wǎng)的路徑分析，GIS排水系統(tǒng)應(yīng)能提供對(duì)管網(wǎng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行連通性分析、上下游分析，并能提供管網(wǎng)橫縱斷面圖的瀏覽查詢功能[7]。將空間分析與排水業(yè)務(wù)模型[15]結(jié)合還可獲得更多類型的空間分析，如當(dāng)暴雨來臨時(shí)，對(duì)排水過程進(jìn)行仿真模擬，以確認(rèn)積水的排除時(shí)間并考慮是否啟用其他輔助排水措施。在諸多空間分析中，排水管網(wǎng)的連通性分析是一項(xiàng)非常重要的內(nèi)容，管網(wǎng)的連通性是進(jìn)行管網(wǎng)水力計(jì)算的先決條件，也是爆管分析的重要環(huán)節(jié)[16]。圖5描述了基于排水GIS系統(tǒng)的連通性分析算法流程。
3 模型應(yīng)用
基于前述的地下管網(wǎng)拓?fù)淠Ｐ图八惴ǎ疚囊枣?zhèn)江市城市排水管網(wǎng)地理信息系統(tǒng)開發(fā)為例，在VC++編程環(huán)境中，利用GIS組件開發(fā)了城市排水GIS系統(tǒng)。系統(tǒng)的空間分析模塊包括上下游分析、連通性分析、淹沒分析、縱斷面分析和水質(zhì)分析，突破了排水GIS系統(tǒng)地下資產(chǎn)管理的局限性，實(shí)現(xiàn)了“地上-地下”一體化的排水分析理念?？臻g分析模塊是以拓?fù)鋽?shù)據(jù)模型為核心，開發(fā)業(yè)務(wù)模型接口，一并封裝為DLL插件，在分析時(shí)調(diào)用插件對(duì)空間數(shù)據(jù)庫(kù)中的排水系統(tǒng)數(shù)據(jù)進(jìn)行計(jì)算。
圖6為鎮(zhèn)江市排水GIS系統(tǒng)連通性分析界面，應(yīng)用本文描述的拓?fù)淠Ｐ停捎檬宙湵頂?shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)了節(jié)點(diǎn)的上下游節(jié)點(diǎn)查詢、節(jié)點(diǎn)的上下游管線查詢算法，程序運(yùn)行前需要設(shè)定管線的起點(diǎn)和終點(diǎn)，然后按照前文描述的過程進(jìn)行查找，最終確定起終點(diǎn)路徑的聯(lián)通性。如圖6從管線始節(jié)點(diǎn)Y74813開始，沿著向右路徑尋找到終節(jié)點(diǎn)Y50437，歷經(jīng)9個(gè)節(jié)點(diǎn)、10段管線，可以發(fā)現(xiàn)，本文提出的拓?fù)淠Ｐ湍軌蛴行нM(jìn)行排水管網(wǎng)的連通性分析。
圖6 鎮(zhèn)江市城市排水GIS系統(tǒng)
為了檢驗(yàn)R+索引的效率，這里以一定面積范圍內(nèi)的某條管線段搜索為例，分別在SQL和R+索引中對(duì)時(shí)間效率進(jìn)行評(píng)價(jià)，其評(píng)價(jià)結(jié)果見表1。從表1分析可得，在面積較小的范圍內(nèi)，如0.67、1.46 km2，傳統(tǒng)SQL查詢和R+索引查詢差距不大，SQL甚至略優(yōu)于R+索引，但隨著面積的增加(管線數(shù)據(jù)量增加)，R+索引查詢顯示出較大優(yōu)勢(shì)，當(dāng)面積為12.59 km2時(shí)，R+索引訪問效率是SQL的3倍多。因此，在數(shù)據(jù)量較大條件下，R+索引比SQL具有更高的數(shù)據(jù)訪問效率。
表1 R+索引效率分析
4 結(jié) 語
隨著城市排水管網(wǎng)信息化的發(fā)展，用戶需要GIS排水系統(tǒng)更加智能化，能夠?yàn)榕潘芾磔o助信息和解決方案，傳統(tǒng)的GIS排水系統(tǒng)由于拓?fù)淠Ｐ秃?jiǎn)單，無法完成這些細(xì)節(jié)需求。因此，本文采用面向?qū)ο蠓椒枋龀鞘信潘瓽IS系統(tǒng)拓?fù)淠Ｐ?，?gòu)建了基于R+樹的空間索引，研究了GIS排水系統(tǒng)的空間分析典型算法，得出結(jié)論如下：
(1) 本文細(xì)化了傳統(tǒng)“管線”與“節(jié)點(diǎn)”模型，并提出相應(yīng)拓?fù)湟?guī)則，如將節(jié)點(diǎn)分為起始節(jié)點(diǎn)、終止節(jié)點(diǎn)、二通節(jié)點(diǎn)等幾類，規(guī)定其上、下游拓?fù)湟?guī)則。此外，首次將匯水區(qū)和受納體等地表對(duì)象封裝為“起始面域”“終止面域”納入拓?fù)淠Ｐ椭锌紤]，為實(shí)現(xiàn)“地上-地下”的一體化分析提供基礎(chǔ)。試驗(yàn)證明，細(xì)化的GIS管線拓?fù)淠Ｐ透N近客觀世界，這種拓?fù)潢P(guān)系可提供更豐富的空間分析類型，便于建立水務(wù)模型空間分析。
(2) 為避免海量排水管網(wǎng)數(shù)據(jù)SQL查詢引起的響應(yīng)時(shí)間延長(zhǎng)、效率低下問題，本文基于地下管網(wǎng)數(shù)據(jù)建立了R+索引，提出了管線復(fù)合體結(jié)構(gòu)，作為索引的基本對(duì)象。同時(shí)改進(jìn)了十字鏈表數(shù)據(jù)結(jié)構(gòu)，使之與R+索引關(guān)聯(lián)，提高了訪問管線數(shù)據(jù)的效率，為空間分析與數(shù)據(jù)動(dòng)態(tài)更新提供技術(shù)依據(jù)，這對(duì)于海量數(shù)據(jù)的訪問與更新具有重要意義。
(3) 節(jié)點(diǎn)查詢是管線查詢與空間分析的基礎(chǔ)，系統(tǒng)開發(fā)試驗(yàn)表明，基于R+索引下的十字鏈表可將有向圖鄰接表和逆鄰接表結(jié)合起來，能夠進(jìn)行雙向訪問，可以很好地完成各種管線路徑分析，并保證分析結(jié)果的正確性，如地下管網(wǎng)連通性分析等。
[1] SCHOLTEN H J,STILLWELL J.Geographical Information Systems for Urban and Regional Planning[M]. Netherlands:Springer Science & Business Media, 2013.
[2] 馬駿, 劉興坡. 城市排水GIS 數(shù)據(jù)分析與組織[J]. 中國(guó)市政工程,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] 路玲玲,吳曉明,任杰. 城市地下管網(wǎng)信息管理問題研究[J].地域研究與開發(fā),2008, 27(2):47-50.
[6] 趙新華,李瓊.城市排水管網(wǎng)信息GIS管理系統(tǒng)設(shè)計(jì)[J].中國(guó)給水排水, 2002, 18(9): 55-57.
[7] 彭歡.城市排水 GIS 系統(tǒng)研究[D].北京:北京林業(yè)大學(xué),2014.
[8] 張小蘭,陳曉翔,黃敏. 面向指路標(biāo)志系統(tǒng)的交通網(wǎng)絡(luò)數(shù)據(jù)模型及應(yīng)用[J]. 地理與地理信息科學(xué),2006(6):45-47,74.
[9] 程雷陽(yáng).電力GIS電網(wǎng)拓?fù)淠Ｐ偷难芯颗c實(shí)現(xiàn)[D].北京:華北電力大學(xué), 2013.
[10] 張靜文, 周杉. 面向?qū)ο蠹夹g(shù)實(shí)現(xiàn)活動(dòng)網(wǎng)絡(luò)圖及關(guān)鍵路徑算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2016, 52(4): 234-237.
[11] 蔚潔. 車輛監(jiān)控導(dǎo)航系統(tǒng)中最短路徑的實(shí)時(shí)性研究[D]. 石家莊:河北師范大學(xué), 2007.
[12] DROZDER A. Data Structures and Algorithms in C++[M]. 3rded. Hoboken：John Wiley & Sons Inc, 2006.
[13] 楊思吉, 吳保國(guó). 森林資源時(shí)空數(shù)據(jù)異步更新與回溯算法研究[J]. 地理與地理信息科學(xué), 2014, 30(3): 37-41.
[14] 張澤寶. 空間數(shù)據(jù)庫(kù)的索引技術(shù)研究[D].哈爾濱:哈爾濱工程大學(xué),2009:24-28.
[15] 李亞君. 基于 GIS 的三維地下管網(wǎng)爆管分析及其系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].成都:電子科技大學(xué), 2015.
[16] 鄭云龍, 鄒大偉, 李紅艷. 基于 SuperMap 平臺(tái)下的排水規(guī)劃管理系統(tǒng)開發(fā)[J]. 測(cè)繪與空間地理信息, 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系統(tǒng)拓?fù)淠Ｐ偷慕J].測(cè)繪通報(bào)，2017(8)：129-134.
10.13474/j.cnki.11-2246.2017.0270.
2016-10-24
國(guó)家水體污染控制與治理科技重大專項(xiàng)(2013ZX07304)
王萌(1991—)，女，碩士生，主要從事3S系統(tǒng)集成與開發(fā)。 E-mail： wm_20161010@163.com
P208
A
0494-0911(2017)08-0129-06
猜你喜歡
自然生態(tài)修復(fù)理念在城市排水規(guī)劃中的應(yīng)用建材發(fā)展導(dǎo)向(2021年18期)2021-11-05 09:20:18 基于二進(jìn)制鏈表的粗糙集屬性約簡(jiǎn)成都信息工程大學(xué)學(xué)報(bào)(2019年2期)2019-08-28 10:00:46 跟麥咭學(xué)編程第二課堂(課外活動(dòng)版)(2019年12期)2019-02-10 03:59:37 基于鏈表多分支路徑樹的云存儲(chǔ)數(shù)據(jù)完整性驗(yàn)證機(jī)制成都信息工程大學(xué)學(xué)報(bào)(2018年1期)2018-05-31 08:40:25 Ladyzhenskaya流體力學(xué)方程組的確定模與確定結(jié)點(diǎn)個(gè)數(shù)估計(jì)數(shù)學(xué)物理學(xué)報(bào)(2018年1期)2018-03-26 08:16:42 鏈表方式集中器抄表的設(shè)計(jì)電測(cè)與儀表(2014年1期)2014-04-04 12:00:22 基于Raspberry PI為結(jié)點(diǎn)的天氣云測(cè)量網(wǎng)絡(luò)實(shí)現(xiàn)電子設(shè)計(jì)工程(2014年12期)2014-02-27 11:58:23 城市排水防澇的管理性措施研究城市道橋與防洪(2014年11期)2014-02-27 07:30:13 深層隧道排水系統(tǒng)在城市排水規(guī)劃中的應(yīng)用城市道橋與防洪(2014年5期)2014-02-27 07:26:30 陜西省城市排水管網(wǎng)5年增加2283km城市道橋與防洪(2013年5期)2013-03-11 15:16:33
王 萌，史明昌,2
(1. 北京林業(yè)大學(xué)水土保持學(xué)院，北京 100083； 2. 北京地拓科技發(fā)展有限公司，北京 100084)
城市排水GIS系統(tǒng)拓?fù)淠Ｐ偷慕?/p>
王 萌1，史明昌1,2
(1. 北京林業(yè)大學(xué)水土保持學(xué)院，北京 100083； 2. 北京地拓科技發(fā)展有限公司，北京 100084)
當(dāng)前的排水管網(wǎng)拓?fù)淠Ｐ陀捎诤雎粤伺潘芫W(wǎng)的細(xì)節(jié)特征，致使拓?fù)潢P(guān)系過于簡(jiǎn)單，不能完成特定排水業(yè)務(wù)模型空間分析，在一定程度上阻礙了排水GIS系統(tǒng)的發(fā)展?；趫D論理論，本文提出了城市排水GIS系統(tǒng)細(xì)致拓?fù)淠Ｐ?。首先，基于面向?qū)ο蠓椒ㄌ岢鐾負(fù)涓拍钅Ｐ秃瓦壿嬆Ｐ?，增加其拓?fù)潢P(guān)系描述的細(xì)節(jié)規(guī)則，以實(shí)現(xiàn)對(duì)客觀世界的真實(shí)模擬。然后在數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)中，采用十字鏈表作為存儲(chǔ)結(jié)構(gòu)，將其改進(jìn)并與R+樹進(jìn)行關(guān)聯(lián)生成空間索引。在空間分析中，本文基于R+索引和十字鏈表提出了空間查詢和路徑分析典型算法。最后以鎮(zhèn)江市城市排水管網(wǎng)地理信息系統(tǒng)開發(fā)為例，對(duì)拓?fù)淠Ｐ瓦M(jìn)行了開發(fā)實(shí)踐。試驗(yàn)結(jié)果表明，本文提出的拓?fù)淠Ｐ涂梢愿鎸?shí)模擬客觀世界，提供更多種空間分析，完成海量數(shù)據(jù)快速訪問，為實(shí)現(xiàn)城市排水GIS系統(tǒng)海量數(shù)據(jù)的高效空間分析提供解決方案。
排水GIS；空間分析；拓?fù)淠Ｐ?；R+樹；十字鏈表
隨著建設(shè)智慧城市與海綿城市戰(zhàn)略的推進(jìn)，GIS以其強(qiáng)大的數(shù)據(jù)管理功能和空間分析特性[1]，在城市排水管理信息系統(tǒng)建設(shè)中方興未艾[2]。目前，國(guó)內(nèi)外排水業(yè)務(wù)模型的研究取得了較為豐碩的成果[3-4]，為城市內(nèi)澇的模擬、仿真、預(yù)警，以及排水管網(wǎng)的科學(xué)管理提供解決方案，是未來排水信息化的發(fā)展方向。相應(yīng)的，排水GIS系統(tǒng)也日臻完善，許多城市建立了GIS排水系統(tǒng)，如北京、無錫、南京、太原等城市應(yīng)用GIS技術(shù)設(shè)計(jì)開發(fā)了城市地下管網(wǎng)或城市排水管理信息系統(tǒng)[5]，這種系統(tǒng)實(shí)現(xiàn)了管網(wǎng)的信息化管理，能夠進(jìn)行查詢分析與可視化表達(dá)，在一定程度上取代了原有落后的人工管理模式[6]。然而，隨著管理者對(duì)排水信息化需求的提高，近年來，希望通過GIS和業(yè)務(wù)模型相結(jié)合的、可實(shí)現(xiàn)“地上-地下”一體化空間分析的排水系統(tǒng)越來越受到管理者與學(xué)者的關(guān)注。這種系統(tǒng)在仿真程度上又提高了一個(gè)層次，可以獲得更多的基于空間的非空間信息，如發(fā)掘?qū)I(yè)信息并應(yīng)用到防洪決策中[7]。
拓?fù)淠Ｐ褪菍?duì)地理實(shí)體拓?fù)潢P(guān)系的抽象描述，是進(jìn)行空間分析的基礎(chǔ)和依據(jù)，直接決定了空間分析的效率[8]。城市排水管網(wǎng)埋在地下，具有隱蔽性和交錯(cuò)復(fù)雜性，它通常是一個(gè)由上萬、甚至百萬以上節(jié)點(diǎn)組成的有向網(wǎng)絡(luò)，其地面覆有各種管網(wǎng)附屬設(shè)施。隨著地下管網(wǎng)建設(shè)的擴(kuò)張，基于GIS的管網(wǎng)數(shù)據(jù)拓?fù)淠Ｐ褪艿絿?yán)峻考驗(yàn)，這是因?yàn)閭鹘y(tǒng)排水系統(tǒng)數(shù)據(jù)結(jié)構(gòu)可擴(kuò)充性有限，獲取信息過度依賴于增加數(shù)據(jù)屬性，數(shù)據(jù)結(jié)構(gòu)沒有與索引建立聯(lián)系，當(dāng)數(shù)據(jù)量巨大時(shí)，運(yùn)用SQL語句進(jìn)行空間查詢和運(yùn)算會(huì)導(dǎo)致系統(tǒng)響應(yīng)時(shí)間長(zhǎng)，效率十分低下[9]。
因此，本文運(yùn)用面向?qū)ο蟮姆椒ń⒊鞘信潘瓽IS系統(tǒng)精細(xì)拓?fù)淠Ｐ?，提出新的拓?fù)湟?guī)則，建立管網(wǎng)十字鏈表數(shù)據(jù)結(jié)構(gòu)，利用R+樹建立空間索引，并以此為基礎(chǔ)提出管網(wǎng)空間分析算法。以鎮(zhèn)江排水系統(tǒng)開發(fā)為例，實(shí)現(xiàn)了拓?fù)浣：偷湫涂臻g分析算法，為城市排水GIS系統(tǒng)拓?fù)浣Ｌ峁┝艘粋€(gè)新方法。
1 拓?fù)淠Ｐ?/h2>
1.1 概念模型
排水系統(tǒng)設(shè)施實(shí)體包括管線及其附屬設(shè)施，分別具有不同的靜態(tài)和動(dòng)態(tài)特征，它們均可抽象為對(duì)象。在傳統(tǒng)排水管網(wǎng)數(shù)據(jù)中，排水管網(wǎng)因其單向、無環(huán)的特點(diǎn)，通常被抽象為一張有向枝狀圖，各類設(shè)施根據(jù)圖論原理被抽象為“管線”和“節(jié)點(diǎn)”兩類對(duì)象。其中節(jié)點(diǎn)類包括檢查井、泵站、堰、蓄水池、雨水口、出水口和分流井等設(shè)施，管線類包括排水管和排水渠等。事實(shí)上，某些節(jié)點(diǎn)類對(duì)象常存在于地表匯水區(qū)或受納體之中，因此排水系統(tǒng)還應(yīng)包括地表匯水區(qū)或受納體面狀區(qū)域，這里命名為起始面域類和終止面域類。通過對(duì)管網(wǎng)拓?fù)涮卣鞯姆治隹梢园l(fā)現(xiàn)，不同節(jié)點(diǎn)類實(shí)體的拓?fù)涮卣鞔嬖诿黠@差異。具體表現(xiàn)在：①雨水口必須為管線起點(diǎn)，與地表匯水區(qū)是拓?fù)浒P(guān)系；②出水口必須為管線終點(diǎn)，與受納體是拓?fù)浒P(guān)系；③雨水口節(jié)點(diǎn)只能存在下游管線；④出水口節(jié)點(diǎn)上有且僅有一條管道相連，且只能是上游管線；⑤分流井有且只有兩條下游管線，而其他節(jié)點(diǎn)最多有一段下游管線；⑥三通井有三條管線連接，四通井有四條管線連接，五通及以上以此類推；⑦管網(wǎng)系統(tǒng)至少應(yīng)有一個(gè)出水口節(jié)點(diǎn)。
為了保證拓?fù)淠Ｐ偷臏?zhǔn)確性，根據(jù)上述拓?fù)涮卣鞑町?，本文將?jié)點(diǎn)進(jìn)一步細(xì)分為多類節(jié)點(diǎn)，包括起始節(jié)點(diǎn)、終止節(jié)點(diǎn)、二通節(jié)點(diǎn)、三通節(jié)點(diǎn)、四通節(jié)點(diǎn)、多通節(jié)點(diǎn)和分流節(jié)點(diǎn)幾類，這些節(jié)點(diǎn)可位于起始面域或終止面域，對(duì)應(yīng)的拓?fù)潢P(guān)系概念模型如圖1所示。同時(shí)，根據(jù)排水信息系統(tǒng)業(yè)務(wù)要求，調(diào)蓄池被視為二通節(jié)點(diǎn)，蓄水引管作為其上游管線和下游管線。
這里規(guī)定雨水箅、閘門、閥門等附屬設(shè)施，不單獨(dú)作為要素表達(dá)，而是被隱性包含在各類對(duì)象中，不直接作為某類拓?fù)鋵?duì)象表示，也不能與其他對(duì)象直接拓?fù)溥B接。也就是排水管網(wǎng)設(shè)施抽象的各類對(duì)象，均是以某種簡(jiǎn)單對(duì)象為主，并包含相應(yīng)附屬設(shè)施對(duì)象的復(fù)雜對(duì)象。如雨水口對(duì)象是包含雨水口和雨水箅在內(nèi)的復(fù)雜對(duì)象，統(tǒng)一抽象為起始節(jié)點(diǎn)類對(duì)象處理，而雨水箅不參與拓?fù)浣！?/p>
圖1 拓?fù)潢P(guān)系概念模型
1.2 邏輯結(jié)構(gòu)
根據(jù)面向?qū)ο蟪绦蛟O(shè)計(jì)方法，對(duì)面域、節(jié)點(diǎn)和管線三類對(duì)象進(jìn)行描述，采用統(tǒng)一建模語言將各類關(guān)系進(jìn)行拓?fù)浔磉_(dá)，所得類間邏輯關(guān)系如圖2所示。除此之外，還需規(guī)定每類對(duì)象的拓?fù)湟?guī)則。在圖2中，定義拓?fù)湟?guī)則為：管線類Pineline是一組管線對(duì)象的集合，每條管線必須有且只有兩個(gè)節(jié)點(diǎn)對(duì)象與之相關(guān)聯(lián)。起始節(jié)點(diǎn)類StartNode是一組起始節(jié)點(diǎn)的集合，一個(gè)起始節(jié)點(diǎn)無上游管線，有且只有一條下游管線，起始面域與起始節(jié)點(diǎn)是一對(duì)多的拓?fù)浒P(guān)系。二通節(jié)點(diǎn)類CockNode是一組二通節(jié)點(diǎn)的集合，一個(gè)二通節(jié)點(diǎn)有且僅有兩條管線與之拓?fù)潢P(guān)聯(lián)，一條為上游管線，一條為下游管線。三通節(jié)點(diǎn)類TconnectorNode是一組三通節(jié)點(diǎn)的集合，一個(gè)三通節(jié)點(diǎn)有且僅有3條管線與之拓?fù)潢P(guān)聯(lián)，2條為上游管線，1條為下游管線。四通節(jié)點(diǎn)類FourconnectorNode是一組四通節(jié)點(diǎn)的集合，一個(gè)四通節(jié)點(diǎn)有且只有4條管線與之拓?fù)潢P(guān)聯(lián)，3條為上游管線，1條為下游管線。多通節(jié)點(diǎn)類MultipleNode的集合是一組多通節(jié)點(diǎn)的集合，一個(gè)多通節(jié)點(diǎn)有p(p>4,p∈Z*)條管線與之拓?fù)潢P(guān)聯(lián)，p-1條為上游管線，一條為下游管線。分流節(jié)點(diǎn)類是一組分流節(jié)點(diǎn)的集合，一個(gè)分流節(jié)點(diǎn)有q(q>2,q∈Z*)條管線與之拓?fù)潢P(guān)聯(lián)，q-2條為上游管線，兩條為下游管線。終止節(jié)點(diǎn)類EndNode是一組終止節(jié)點(diǎn)的集合，一個(gè)終止節(jié)點(diǎn)無下游管線，有r(r∈Z*)條上游管線與之拓?fù)潢P(guān)聯(lián)。起始面域類StartArea是一組起始面域的集合，一個(gè)起始面域可以包含多個(gè)起始節(jié)點(diǎn)。終止面域類EndArea是一組終止面域的集合，一個(gè)終止面域可以包含多個(gè)終止節(jié)點(diǎn)。排水管網(wǎng)拓?fù)淠Ｐ褪怯梢陨纤蓄惣邦愔g的拓?fù)潢P(guān)系構(gòu)成。
圖2 邏輯模型
1.3 存儲(chǔ)結(jié)構(gòu)
1.3.1 排水GIS數(shù)據(jù)結(jié)構(gòu)
目前，在給水、電力等行業(yè)管網(wǎng)的應(yīng)用中，圖的存儲(chǔ)主要采用鄰接矩陣和鄰接表兩種結(jié)構(gòu)[10]。由于鄰接矩陣會(huì)隨著數(shù)據(jù)量的增加出現(xiàn)數(shù)據(jù)冗余，鄰接表只能存儲(chǔ)下游邊數(shù)據(jù)，因此二者不是理想的排水GIS數(shù)據(jù)結(jié)構(gòu)。相比之下，十字鏈表是一種結(jié)合了有向圖鄰接表和逆鄰接表的鏈?zhǔn)浇Y(jié)構(gòu)[11]，可以同時(shí)存儲(chǔ)節(jié)點(diǎn)的上游和下游信息，且建立十字鏈表的時(shí)間復(fù)雜度和建立鄰接表是相同的[12]，因此十字鏈表作為排水系統(tǒng)拓?fù)淠Ｐ褪潜容^合適的。
弧結(jié)點(diǎn)有兩個(gè)數(shù)據(jù)域tailvex和headvex，分別指示弧的上下游兩個(gè)關(guān)聯(lián)節(jié)點(diǎn)在有向圖中的位置，兩個(gè)鏈域hlink和tlink，分別指向弧頭或弧尾相同的下一條弧，info域用于指向該弧的相關(guān)信息。頂點(diǎn)結(jié)點(diǎn)是鏈表的頭結(jié)點(diǎn)，由一個(gè)數(shù)據(jù)域和兩個(gè)鏈域構(gòu)成，頂點(diǎn)數(shù)據(jù)域data用于存儲(chǔ)與節(jié)點(diǎn)相關(guān)的信息，鏈域firstin和firstout分別指向該節(jié)點(diǎn)的第一個(gè)上游或下游弧。圖3為圖1拓?fù)淠Ｐ偷氖宙湵斫Y(jié)構(gòu)。
頂點(diǎn)結(jié)點(diǎn)的firstin鏈域和firstout鏈域分別指向該節(jié)點(diǎn)的上游和下游節(jié)點(diǎn)。由此可以得出：起始節(jié)點(diǎn)(V1、V2、V6、V8)的firstin鏈域?yàn)榭?，除分流?jié)點(diǎn)(V5)firstout鏈域指向兩個(gè)弧結(jié)點(diǎn)、終止節(jié)點(diǎn)(V9、V10)firstout鏈域?yàn)榭罩猓渌惞?jié)點(diǎn)的firstout鏈域均僅指向一個(gè)對(duì)應(yīng)于該節(jié)點(diǎn)的弧結(jié)點(diǎn)。
弧結(jié)點(diǎn)鏈域的數(shù)量表示與該節(jié)點(diǎn)關(guān)聯(lián)的管線條數(shù)。hlink鏈域指向弧頭相同的下一條弧，即依次指向某頂點(diǎn)的所有上游弧結(jié)點(diǎn)，直到指向的弧結(jié)點(diǎn)的hlink鏈域?yàn)榭铡Ｍ韙link鏈域依次指向某頂點(diǎn)的所有下游弧結(jié)點(diǎn)。因此，對(duì)于二通節(jié)點(diǎn)(V3)，其上游和下游指向的弧結(jié)點(diǎn)個(gè)數(shù)均為1；三通節(jié)點(diǎn)(V7)指向的上游弧結(jié)點(diǎn)個(gè)數(shù)為2，下游弧結(jié)點(diǎn)個(gè)數(shù)為1；四通節(jié)點(diǎn)(V4)指向的上游弧結(jié)點(diǎn)個(gè)數(shù)為3，下游弧結(jié)點(diǎn)個(gè)數(shù)為1；多通節(jié)點(diǎn)以此類推。
1.3.2 R+樹索引
十字鏈表用于空間分析，傳統(tǒng)的方法是SQL查詢，將按鏈表一直拉到底，可以生成相應(yīng)方向的路徑[13]。這種方法雖然簡(jiǎn)單，但是并不高效，尤其是數(shù)據(jù)量達(dá)到城市級(jí)時(shí)，計(jì)算方法緩慢，因此需要改進(jìn)。由于R+樹對(duì)數(shù)據(jù)項(xiàng)和索引項(xiàng)的填充個(gè)數(shù)沒有嚴(yán)格的限制，中間結(jié)點(diǎn)之間不能相互重疊，當(dāng)搜索某個(gè)對(duì)象的時(shí)候，從多個(gè)結(jié)點(diǎn)都可以定位到該對(duì)象[14]，因此可以通過改造十字鏈表實(shí)現(xiàn)索引。
圖3 排水管網(wǎng)十字鏈表
十字鏈表若支持R+樹索引，尚需解決二個(gè)問題：①鏈表的數(shù)據(jù)域必須增加索引信息；②建立鏈表組合結(jié)構(gòu)，將索引信息賦予十字鏈表數(shù)據(jù)域。第1個(gè)問題比較簡(jiǎn)單，可以在鏈表數(shù)據(jù)結(jié)構(gòu)中增加索引，也就是在定點(diǎn)結(jié)點(diǎn)data域下增加指向所屬R+樹的指針WhichRPlus，即VertexNode->data->WhichRPlus=Null，待R+樹建立后賦予相應(yīng)信息。
R+樹索引的數(shù)據(jù)為對(duì)象，前述的節(jié)點(diǎn)、管線、面域結(jié)構(gòu)需要統(tǒng)一數(shù)據(jù)結(jié)構(gòu)，作為R+樹葉結(jié)點(diǎn)的訪問對(duì)象，由于面域結(jié)構(gòu)與節(jié)點(diǎn)是重合關(guān)聯(lián)的，而節(jié)點(diǎn)隱含于弧段結(jié)構(gòu)中，因此封裝對(duì)象可統(tǒng)一為管線組合結(jié)構(gòu)，它最少包括一條管線(圖4中R15內(nèi)數(shù)據(jù))，最多可包括多條管線(圖4中R3內(nèi)數(shù)據(jù))。文獻(xiàn)[7]封裝了Larcl管線結(jié)構(gòu)，因此可將Larcl管線結(jié)構(gòu)再次封裝，建立適合于R+樹索引的數(shù)據(jù)結(jié)構(gòu)。葉結(jié)點(diǎn)數(shù)據(jù)可以通過聲明一個(gè)PipelineCompound類實(shí)現(xiàn)，聲明代碼如下：
Class PipelineCompound
{
CArray
long larclNum; ∥Larcl對(duì)象數(shù)目
long PipelineCompoundID; ∥PipelineCompound的ID
CRect Rect; ∥PipelineCompound的MBR
CRect upRect; ∥PipelineCompound上層樹的MBR
CRect downRect; ∥PipelineCompound下層樹的MBR
bool isVisitedFLAG; ∥是否被訪問過
bool isIndexCompleted; ∥索引是否建立
bool isIndexCleared; ∥索引是否被清除
bool isRegistered；∥是否對(duì)頂點(diǎn)結(jié)點(diǎn)注冊(cè)索引
};
圖4 排水管網(wǎng)的R+索引
PipelineCompound類是葉結(jié)點(diǎn)數(shù)據(jù)對(duì)象，由于管線數(shù)據(jù)Larcl封裝其內(nèi)，因此可以對(duì)管線數(shù)據(jù)和十字鏈表數(shù)據(jù)進(jìn)行訪問，更新鏈表數(shù)據(jù)結(jié)構(gòu)中info信息。R+樹生成后，區(qū)域內(nèi)的排水管線R+樹如圖5所示，其中只有葉結(jié)點(diǎn)R3、R10、R11、R12、R13、R14、R15包含PipelineCompound類數(shù)據(jù)，其他非葉結(jié)點(diǎn)存儲(chǔ)最小外接矩形MBR和指向下、上級(jí)結(jié)點(diǎn)的指針。由于R+樹中不允許中間結(jié)點(diǎn)重合，搜索時(shí)可以不用遍歷各個(gè)結(jié)點(diǎn)，因此速度較R樹索引有所提升。
2 空間分析算法
2.1 空間查詢
空間查詢包括節(jié)點(diǎn)的上下游節(jié)點(diǎn)查詢、節(jié)點(diǎn)的上下游管線查詢、管線的上下游節(jié)點(diǎn)查詢和管線的上下游管線查詢?；赗+索引的查詢算法過程為：首先通過查詢區(qū)域確定R+樹結(jié)點(diǎn)PipelineCompound數(shù)據(jù)，進(jìn)而訪問十字鏈表結(jié)構(gòu)的管線數(shù)據(jù)和弧段數(shù)據(jù)，最終完成查詢。以節(jié)點(diǎn)Vi的上下游查詢算法為例，首先通過R+樹搜索到PipelineCompound對(duì)象，然后找到十字鏈表中節(jié)點(diǎn)Vi對(duì)應(yīng)的頂點(diǎn)結(jié)點(diǎn)，其firstin域指向的邊結(jié)點(diǎn)為Vi的上游管線，該邊結(jié)點(diǎn)的tailvex鏈域指向的頂點(diǎn)結(jié)點(diǎn)為Vi的上游節(jié)點(diǎn)，firstout域指向的邊結(jié)點(diǎn)為Vi的下游管線，該邊結(jié)點(diǎn)的headvex鏈域指向的頂點(diǎn)結(jié)點(diǎn)為Vi的下游節(jié)點(diǎn)。
圖5 連通性分析算法
2.2 路徑分析
城市排水GIS系統(tǒng)空間分析的核心是管網(wǎng)的路徑分析，GIS排水系統(tǒng)應(yīng)能提供對(duì)管網(wǎng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行連通性分析、上下游分析，并能提供管網(wǎng)橫縱斷面圖的瀏覽查詢功能[7]。將空間分析與排水業(yè)務(wù)模型[15]結(jié)合還可獲得更多類型的空間分析，如當(dāng)暴雨來臨時(shí)，對(duì)排水過程進(jìn)行仿真模擬，以確認(rèn)積水的排除時(shí)間并考慮是否啟用其他輔助排水措施。在諸多空間分析中，排水管網(wǎng)的連通性分析是一項(xiàng)非常重要的內(nèi)容，管網(wǎng)的連通性是進(jìn)行管網(wǎng)水力計(jì)算的先決條件，也是爆管分析的重要環(huán)節(jié)[16]。圖5描述了基于排水GIS系統(tǒng)的連通性分析算法流程。
3 模型應(yīng)用
基于前述的地下管網(wǎng)拓?fù)淠Ｐ图八惴ǎ疚囊枣?zhèn)江市城市排水管網(wǎng)地理信息系統(tǒng)開發(fā)為例，在VC++編程環(huán)境中，利用GIS組件開發(fā)了城市排水GIS系統(tǒng)。系統(tǒng)的空間分析模塊包括上下游分析、連通性分析、淹沒分析、縱斷面分析和水質(zhì)分析，突破了排水GIS系統(tǒng)地下資產(chǎn)管理的局限性，實(shí)現(xiàn)了“地上-地下”一體化的排水分析理念?？臻g分析模塊是以拓?fù)鋽?shù)據(jù)模型為核心，開發(fā)業(yè)務(wù)模型接口，一并封裝為DLL插件，在分析時(shí)調(diào)用插件對(duì)空間數(shù)據(jù)庫(kù)中的排水系統(tǒng)數(shù)據(jù)進(jìn)行計(jì)算。
圖6為鎮(zhèn)江市排水GIS系統(tǒng)連通性分析界面，應(yīng)用本文描述的拓?fù)淠Ｐ停捎檬宙湵頂?shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)了節(jié)點(diǎn)的上下游節(jié)點(diǎn)查詢、節(jié)點(diǎn)的上下游管線查詢算法，程序運(yùn)行前需要設(shè)定管線的起點(diǎn)和終點(diǎn)，然后按照前文描述的過程進(jìn)行查找，最終確定起終點(diǎn)路徑的聯(lián)通性。如圖6從管線始節(jié)點(diǎn)Y74813開始，沿著向右路徑尋找到終節(jié)點(diǎn)Y50437，歷經(jīng)9個(gè)節(jié)點(diǎn)、10段管線，可以發(fā)現(xiàn)，本文提出的拓?fù)淠Ｐ湍軌蛴行нM(jìn)行排水管網(wǎng)的連通性分析。
圖6 鎮(zhèn)江市城市排水GIS系統(tǒng)
為了檢驗(yàn)R+索引的效率，這里以一定面積范圍內(nèi)的某條管線段搜索為例，分別在SQL和R+索引中對(duì)時(shí)間效率進(jìn)行評(píng)價(jià)，其評(píng)價(jià)結(jié)果見表1。從表1分析可得，在面積較小的范圍內(nèi)，如0.67、1.46 km2，傳統(tǒng)SQL查詢和R+索引查詢差距不大，SQL甚至略優(yōu)于R+索引，但隨著面積的增加(管線數(shù)據(jù)量增加)，R+索引查詢顯示出較大優(yōu)勢(shì)，當(dāng)面積為12.59 km2時(shí)，R+索引訪問效率是SQL的3倍多。因此，在數(shù)據(jù)量較大條件下，R+索引比SQL具有更高的數(shù)據(jù)訪問效率。
表1 R+索引效率分析
4 結(jié) 語
隨著城市排水管網(wǎng)信息化的發(fā)展，用戶需要GIS排水系統(tǒng)更加智能化，能夠?yàn)榕潘芾磔o助信息和解決方案，傳統(tǒng)的GIS排水系統(tǒng)由于拓?fù)淠Ｐ秃?jiǎn)單，無法完成這些細(xì)節(jié)需求。因此，本文采用面向?qū)ο蠓椒枋龀鞘信潘瓽IS系統(tǒng)拓?fù)淠Ｐ?，?gòu)建了基于R+樹的空間索引，研究了GIS排水系統(tǒng)的空間分析典型算法，得出結(jié)論如下：
(1) 本文細(xì)化了傳統(tǒng)“管線”與“節(jié)點(diǎn)”模型，并提出相應(yīng)拓?fù)湟?guī)則，如將節(jié)點(diǎn)分為起始節(jié)點(diǎn)、終止節(jié)點(diǎn)、二通節(jié)點(diǎn)等幾類，規(guī)定其上、下游拓?fù)湟?guī)則。此外，首次將匯水區(qū)和受納體等地表對(duì)象封裝為“起始面域”“終止面域”納入拓?fù)淠Ｐ椭锌紤]，為實(shí)現(xiàn)“地上-地下”的一體化分析提供基礎(chǔ)。試驗(yàn)證明，細(xì)化的GIS管線拓?fù)淠Ｐ透N近客觀世界，這種拓?fù)潢P(guān)系可提供更豐富的空間分析類型，便于建立水務(wù)模型空間分析。
(2) 為避免海量排水管網(wǎng)數(shù)據(jù)SQL查詢引起的響應(yīng)時(shí)間延長(zhǎng)、效率低下問題，本文基于地下管網(wǎng)數(shù)據(jù)建立了R+索引，提出了管線復(fù)合體結(jié)構(gòu)，作為索引的基本對(duì)象。同時(shí)改進(jìn)了十字鏈表數(shù)據(jù)結(jié)構(gòu)，使之與R+索引關(guān)聯(lián)，提高了訪問管線數(shù)據(jù)的效率，為空間分析與數(shù)據(jù)動(dòng)態(tài)更新提供技術(shù)依據(jù)，這對(duì)于海量數(shù)據(jù)的訪問與更新具有重要意義。
(3) 節(jié)點(diǎn)查詢是管線查詢與空間分析的基礎(chǔ)，系統(tǒng)開發(fā)試驗(yàn)表明，基于R+索引下的十字鏈表可將有向圖鄰接表和逆鄰接表結(jié)合起來，能夠進(jìn)行雙向訪問，可以很好地完成各種管線路徑分析，并保證分析結(jié)果的正確性，如地下管網(wǎng)連通性分析等。
[1] SCHOLTEN H J,STILLWELL J.Geographical Information Systems for Urban and Regional Planning[M]. Netherlands:Springer Science & Business Media, 2013.
[2] 馬駿, 劉興坡. 城市排水GIS 數(shù)據(jù)分析與組織[J]. 中國(guó)市政工程,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] 路玲玲,吳曉明,任杰. 城市地下管網(wǎng)信息管理問題研究[J].地域研究與開發(fā),2008, 27(2):47-50.
[6] 趙新華,李瓊.城市排水管網(wǎng)信息GIS管理系統(tǒng)設(shè)計(jì)[J].中國(guó)給水排水, 2002, 18(9): 55-57.
[7] 彭歡.城市排水 GIS 系統(tǒng)研究[D].北京:北京林業(yè)大學(xué),2014.
[8] 張小蘭,陳曉翔,黃敏. 面向指路標(biāo)志系統(tǒng)的交通網(wǎng)絡(luò)數(shù)據(jù)模型及應(yīng)用[J]. 地理與地理信息科學(xué),2006(6):45-47,74.
[9] 程雷陽(yáng).電力GIS電網(wǎng)拓?fù)淠Ｐ偷难芯颗c實(shí)現(xiàn)[D].北京:華北電力大學(xué), 2013.
[10] 張靜文, 周杉. 面向?qū)ο蠹夹g(shù)實(shí)現(xiàn)活動(dòng)網(wǎng)絡(luò)圖及關(guān)鍵路徑算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2016, 52(4): 234-237.
[11] 蔚潔. 車輛監(jiān)控導(dǎo)航系統(tǒng)中最短路徑的實(shí)時(shí)性研究[D]. 石家莊:河北師范大學(xué), 2007.
[12] DROZDER A. Data Structures and Algorithms in C++[M]. 3rded. Hoboken：John Wiley & Sons Inc, 2006.
[13] 楊思吉, 吳保國(guó). 森林資源時(shí)空數(shù)據(jù)異步更新與回溯算法研究[J]. 地理與地理信息科學(xué), 2014, 30(3): 37-41.
[14] 張澤寶. 空間數(shù)據(jù)庫(kù)的索引技術(shù)研究[D].哈爾濱:哈爾濱工程大學(xué),2009:24-28.
[15] 李亞君. 基于 GIS 的三維地下管網(wǎng)爆管分析及其系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].成都:電子科技大學(xué), 2015.
[16] 鄭云龍, 鄒大偉, 李紅艷. 基于 SuperMap 平臺(tái)下的排水規(guī)劃管理系統(tǒng)開發(fā)[J]. 測(cè)繪與空間地理信息, 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系統(tǒng)拓?fù)淠Ｐ偷慕J].測(cè)繪通報(bào)，2017(8)：129-134.
10.13474/j.cnki.11-2246.2017.0270.
2016-10-24
國(guó)家水體污染控制與治理科技重大專項(xiàng)(2013ZX07304)
王萌(1991—)，女，碩士生，主要從事3S系統(tǒng)集成與開發(fā)。 E-mail： wm_20161010@163.com
P208
A
0494-0911(2017)08-0129-06
猜你喜歡
建材發(fā)展導(dǎo)向(2021年18期)2021-11-05 09:20:18
成都信息工程大學(xué)學(xué)報(bào)(2019年2期)2019-08-28 10:00:46
第二課堂(課外活動(dòng)版)(2019年12期)2019-02-10 03:59:37
成都信息工程大學(xué)學(xué)報(bào)(2018年1期)2018-05-31 08:40:25
數(shù)學(xué)物理學(xué)報(bào)(2018年1期)2018-03-26 08:16:42
電測(cè)與儀表(2014年1期)2014-04-04 12:00:22
電子設(shè)計(jì)工程(2014年12期)2014-02-27 11:58:23
城市道橋與防洪(2014年11期)2014-02-27 07:30:13
城市道橋與防洪(2014年5期)2014-02-27 07:26:30
城市道橋與防洪(2013年5期)2013-03-11 15:16:33
