劉子恒1,2,侯英姿1,2，王方雄1,2，張翔3

　?。?.遼寧師范大學(xué) 遼寧省自然地理與空間信息科學(xué)重點實驗室，遼寧 大連 116029；2.遼寧師范大學(xué) 城市與環(huán)境學(xué)院，遼寧 大連 116029；3.大連市城市規(guī)劃設(shè)計研究院，遼寧 大連 116011）

　　摘要：研究了城市管網(wǎng)3DGIS的連通分析方法，利用廣度優(yōu)先搜索算法根據(jù)管網(wǎng)流向信息進(jìn)行正向和反向搜索來遍歷管網(wǎng)結(jié)點，基于SuperMap iObjects開發(fā)實現(xiàn)了管網(wǎng)3DGIS的連通性分析、上下游追蹤、共同上下游查找、最短路徑分析、查找源和匯等連通分析功能。

　　關(guān)鍵詞：連通分析；廣度優(yōu)先遍歷算法；SuperMap iObjects；管網(wǎng)3DGIS

0引言

　　隨著城市建設(shè)步伐的加快，城市管網(wǎng)系統(tǒng)建設(shè)愈加龐雜，而管網(wǎng)連通性分析的可靠性和便捷性對可燃、易爆等管網(wǎng)系統(tǒng)的管理維護(hù)要求更加嚴(yán)格。在計算管網(wǎng)可靠性上，不同時期不同學(xué)者對城市管網(wǎng)的連通性進(jìn)行了大量研究［1］。參考文獻(xiàn)［2］在MapInfo中實現(xiàn)了以圖論為基礎(chǔ)的動態(tài)淘汰算法的管網(wǎng)連通分析，但對有向管網(wǎng)的流向來源沒有說明；參考文獻(xiàn)［3］通過對數(shù)據(jù)結(jié)構(gòu)變更來改寫圖的連通性算法以縮短運(yùn)算時間，提高網(wǎng)絡(luò)連通可靠性；參考文獻(xiàn)［4］通過圖論和模糊數(shù)學(xué)理論解決管網(wǎng)連通可靠性問題。為了更好地實現(xiàn)管網(wǎng)連通分析下的追蹤分析、路徑分析，解決連通分析中的管網(wǎng)流向和網(wǎng)絡(luò)拓?fù)潢P(guān)系，本文以設(shè)施網(wǎng)絡(luò)模型為基礎(chǔ)，依靠管網(wǎng)有向圖和管網(wǎng)鄰接矩陣模型，將廣度優(yōu)先遍歷（BFS）算法與SuperMap iObjects組件技術(shù)相結(jié)合，實現(xiàn)管網(wǎng)連通分析功能。

1管網(wǎng)連通分析方法

　　1.1設(shè)施網(wǎng)絡(luò)模型

　　設(shè)施網(wǎng)絡(luò)模型（BuildNetwork）是指根據(jù)網(wǎng)絡(luò)中的拓?fù)潢P(guān)系以及源和匯的網(wǎng)絡(luò)位置確定介質(zhì)流向，按照一定的拓?fù)湟?guī)則建立的網(wǎng)絡(luò)模型。管網(wǎng)的設(shè)施網(wǎng)絡(luò)模型采用管網(wǎng)邏輯模型和管網(wǎng)幾何模型來表達(dá)管網(wǎng)拓?fù)湫畔⒑凸芫W(wǎng)流向。SuperMap SDX+空間數(shù)據(jù)庫引擎采用圖庫與分布式空間數(shù)據(jù)存儲方式，存儲各種關(guān)系的空間幾何對象，支持拓?fù)潢P(guān)系和三維數(shù)據(jù)存儲能力，形成空間數(shù)據(jù)和幾何數(shù)據(jù)一體化的空間數(shù)據(jù)庫。管網(wǎng)邏輯模型由管網(wǎng)結(jié)點數(shù)據(jù)和弧段數(shù)據(jù)拓?fù)錁?gòu)網(wǎng)而成，利用屬性表信息來表達(dá)網(wǎng)絡(luò)的連通性，具體可以通過數(shù)據(jù)集一對一和一對多的ID關(guān)聯(lián)值來表達(dá)邏輯模型和幾何模型中弧段（Edge）數(shù)據(jù)集和結(jié)點(Node)數(shù)據(jù)集的拓?fù)潢P(guān)系［5］。然后將管網(wǎng)模型中的閥門點、檢修井等構(gòu)建為管網(wǎng)幾何模型中的節(jié)點數(shù)據(jù)集，將管網(wǎng)模型中的管線構(gòu)建為幾何模型中的弧段數(shù)據(jù)集，管網(wǎng)中介質(zhì)的流向以源、匯數(shù)據(jù)集的網(wǎng)絡(luò)位置確定，以Direction字段值表示。在構(gòu)建設(shè)施網(wǎng)絡(luò)模型時，根據(jù)管網(wǎng)源（source）、匯點（sink）的幾何信息創(chuàng)建管網(wǎng)數(shù)據(jù)集的BuildNetwork,自動創(chuàng)建Direction屬性字段（如圖1（b））。

　　1.2管網(wǎng)鄰接矩陣

　　廣度優(yōu)先搜索算法（BreadthFirst Search,BFS）是管網(wǎng)空間分析常用的一種方法，目的是遍歷圖中所有結(jié)點進(jìn)行目標(biāo)查詢，并以此為基礎(chǔ)衍生出其他算法［6］。BFS算法實質(zhì)上是以源點W為起點，向外搜索與起點距離為d（1，2，3，…）的未被訪問的鄰接頂點p1，p2，p3，…，pi，然后分別以這些頂點為起點搜索距離為d+1的其他未被搜索過的頂點，直到所有頂點都被搜索到為止。

　　所有管網(wǎng)在遍歷時要以有向圖為基礎(chǔ)，構(gòu)建非對稱矩陣。通過設(shè)施網(wǎng)絡(luò)模型可以構(gòu)建管網(wǎng)有向圖，并根據(jù)流向信息對管網(wǎng)的每條管道構(gòu)建非對稱矩陣，其中管道環(huán)路在矩陣中是對稱的。管網(wǎng)鄰接矩陣的建立過程如下：（1）定義管網(wǎng)模型的起始點、終止點和流向字段信息；（2）根據(jù)管網(wǎng)有向圖圖例，表達(dá)管網(wǎng)介質(zhì)流動方向，即包括起點到終點、終點到起點、管網(wǎng)環(huán)路、不連通等；（3）結(jié)合設(shè)施網(wǎng)絡(luò)模型Direction字段值與流向關(guān)系，構(gòu)建鄰接矩陣S，圖內(nèi)管點間關(guān)系用二維數(shù)組S［m］［n］存儲，m，n表示管點序號；（4）根據(jù)廣度優(yōu)先搜索算法，當(dāng)S［m］［n］=1時，則有流向Pm→Pn。以管點0為起點，在鄰接矩陣中有S［0］［3］=0，S［3］［0］=1，判斷管點0的上游是管點3，不參與搜索，則BFS算法下的管網(wǎng)有向圖遍歷順序為0-1-2-4-5。管網(wǎng)有向圖鄰接矩陣的建立過程如圖1所示。

　　1.3管網(wǎng)連通分析算法

　　通過BFS算法搜索每個管點是否為目標(biāo)點來判斷管網(wǎng)的連通性，而對于有向管網(wǎng)來說，在判斷管段兩端的管網(wǎng)是否連通的基礎(chǔ)上，還需標(biāo)識出管點的連通路徑［7］。根據(jù)管網(wǎng)流向特征，如果某段管線連通，則該連通管段下游管段的所有上游管段均經(jīng)過該管段，即利用BFS算法反向搜索管點并記錄管段連通的路徑［8］。搜索與起點P0鄰接的上游管點，當(dāng)S［m］［0］=1時，則Pm的上游鄰接管點為P0，這在管網(wǎng)環(huán)路中同樣成立， BFS算法反向搜索具體流程如圖2（cmpPoint為已搜索過的管點，wilPoint為即將搜索的鄰接管點，nonPoint為未搜索過的管點）。

2管網(wǎng)連通分析功能實現(xiàn)

　　城市燃?xì)夤芫W(wǎng)連通分析功能的實現(xiàn)以 SuperMap iObjects組件技術(shù)為支撐，在有向管網(wǎng)鄰接矩陣的基礎(chǔ)上，通過管網(wǎng)設(shè)施網(wǎng)絡(luò)數(shù)據(jù)模型，以BFS算法為基礎(chǔ)根據(jù)管網(wǎng)流向進(jìn)行正向和反向搜索，實現(xiàn)管網(wǎng)系統(tǒng)的連通性分析、上下游追蹤、共同上下游查找、最短路徑分析、查找源和匯等。

　　2.1管網(wǎng)連通性分析

　　連通性分析主要是判斷管點間管網(wǎng)的連通性，通過利用BFS算法判斷燃?xì)夤芫W(wǎng)的兩個管點之間是否連通，并在MapControl中標(biāo)識出連通的路徑。根據(jù)流向字段信息關(guān)系（SmFNode、SmTNode、Direction），用二維數(shù)組array記錄所有管網(wǎng)鄰接矩陣的管點，通過調(diào)用FacilityAnalystResult類的FindPathFromNodes方法獲取SmFNode、SmTNode的ID字段值和QueryParameter類庫定義的SQL查詢語句匹配管網(wǎng)閥門的OnlyID，記錄符合條件的ID數(shù)組，然后利用FindConnected EdgesFromNodes方法獲取與節(jié)點ID數(shù)組連通的設(shè)施網(wǎng)絡(luò)模型弧段，用GeoStyle類記錄線狀路徑的風(fēng)格屬性；在SceneControl中通過Point3D定義相對應(yīng)的管點，用GeoStyle3D類設(shè)置三維場景中管點風(fēng)格符號。分析結(jié)果如圖3（兩個管點均在管網(wǎng)環(huán)路上）。

　　2.2管網(wǎng)上下游追蹤

　　燃?xì)夤芫W(wǎng)上下游追蹤分為上游追蹤和下游追蹤，使用BFS算法基于流向進(jìn)行正向和反向搜索計算并標(biāo)識出燃?xì)夤芫W(wǎng)目標(biāo)要素的上游和下游路徑。具體通過調(diào)用Point2D和Point3D分別在MapControl和SceneControl中選取一個管點，并使用GeoStyle和GeoStyle3D類設(shè)置點狀符號風(fēng)格；利用FacilityAnalystResult類的TraceUp FromNode和TraceDownFromNode方法，分別根據(jù)給定的nodeID進(jìn)行上下游追蹤，利用BFS算法查找該節(jié)點的上下游連通節(jié)點，利用FindConnectedEdgesFromNodes查找并返回與節(jié)點連通的弧段集合，用GeoStyle類記錄并設(shè)置線狀符號風(fēng)格屬性。上游追蹤分析結(jié)果如圖4?！?/p>

　　2.3管網(wǎng)共同上下游查找

　　共同上下游查找，即查找兩個管點的共同上游和共同下游，并標(biāo)識出查找路徑。在mapControl和SceneControl窗口分別通過Point2D和Point3D定義兩個管點，并設(shè)置GeoStyle和GeoStyle3D類的點狀符號風(fēng)格，通過FacilityAnalyst 類調(diào)用FacilityAnalystResult、FindCommonAncestorsFromNodes和FindCommonCatchmentsFromNodes方法，查找兩管點的共同上下游弧段，并返回弧段集合，用GeoStyle類設(shè)置弧段路徑風(fēng)格符號。查找共同下游結(jié)果如圖5。

　　2.4最短路徑分析

　　最短路徑分析是指在設(shè)施網(wǎng)絡(luò)模型中，根據(jù)管網(wǎng)流向和管網(wǎng)長度權(quán)值來計算最短路徑的過程。最短路徑的計算以管段的長度值為參考，即通過給定的起始點，根據(jù)流向信息和BFS算法采用正向和反向搜索遍歷到終止點的路徑，根據(jù)長度權(quán)值選擇最短返回路線。首先根據(jù)給定的起始點和終止點ID，利用BuildFacilityNetworkDirections方法正反BFS搜索，直到搜索到終止點ID,通過FacilityAnalyst類調(diào)用FacilityAnalystResult和 FindPathFromNodes方法，根據(jù)SmLength權(quán)值獲取到最短路徑。

　　2.5查找源和匯

　　查找源和匯指在設(shè)施網(wǎng)絡(luò)模型中根據(jù)指定的管點，按照流向信息查找流向該管點最近的源點或下游匯點。首先判斷該管點ID所在的管段，根據(jù)流向Direction字段信息使用反向BFS搜索算法查找最近的源點，使用正向BFS算法查找該管點的下游匯點。具體通過給定管點ID匹配管線起始點或終止點ID并判斷該管線流向，利用反向BFS算法記錄所有符合條件的管點ID并存儲在二維數(shù)組中，通過調(diào)用FacilityAnalystResult類的FindSourceFromNode方法查找流向該管點的源點，并在FindConnectedEdgesFromNodes中查找與管點相連通的管段集合，在GeoStyle中設(shè)置結(jié)果顯示風(fēng)格。查找源點結(jié)果如圖6。

3結(jié)束語

　　管網(wǎng)3DGIS的連通分析，首先要解決管網(wǎng)數(shù)據(jù)模型的拓?fù)潢P(guān)系，其次針對管網(wǎng)介質(zhì)的流動性，分析管網(wǎng)流向?qū)B通分析的影響?；诹飨虻脑O(shè)施網(wǎng)絡(luò)模型在燃?xì)夤芫W(wǎng)連通分析中，利用BFS基礎(chǔ)算法，采用正向和反向搜索遍歷管網(wǎng)中管點和管段關(guān)系，解決了燃?xì)夤芫W(wǎng)在流向和環(huán)路上的連通分析問題，包括管網(wǎng)的連通性分析、上下游追蹤、共同上下游查找、最短路徑分析、查找源和匯等連通分析功能，對管網(wǎng)系統(tǒng)的優(yōu)化管理、提高可靠性和運(yùn)行效率提供了可行性方法。

參考文獻(xiàn)

　?。?］ OSTFELD A，ASCE M.Water distribution systems connectivity analysis［J］. Journal of Water Resources Planning and Management, 2005, 131(1): 5866.

　　［2］ 段琪慶,劉寒芳,薛冰.數(shù)字管網(wǎng)連通分析的淘汰算法與實現(xiàn)［J］.測繪科學(xué),2008（S1）:168169.

　?。?］ 陸鳴盛,沈成康.圖的連通性快速算法［J］. 同濟(jì)大學(xué)學(xué)報(自然科學(xué)版),2001,29（4）:436439.