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

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

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

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

0引言

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

1管網連通分析方法

　　1.1設施網絡模型

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

　　1.2管網鄰接矩陣

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

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

　　1.3管網連通分析算法

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

2管網連通分析功能實現

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

　　2.1管網連通性分析

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

　　2.2管網上下游追蹤

　　燃氣管網上下游追蹤分為上游追蹤和下游追蹤，使用BFS算法基于流向進行正向和反向搜索計算并標識出燃氣管網目標要素的上游和下游路徑。具體通過調用Point2D和Point3D分別在MapControl和SceneControl中選取一個管點，并使用GeoStyle和GeoStyle3D類設置點狀符號風格；利用FacilityAnalystResult類的TraceUp FromNode和TraceDownFromNode方法，分別根據給定的nodeID進行上下游追蹤，利用BFS算法查找該節(jié)點的上下游連通節(jié)點，利用FindConnectedEdgesFromNodes查找并返回與節(jié)點連通的弧段集合，用GeoStyle類記錄并設置線狀符號風格屬性。上游追蹤分析結果如圖4。　

　　2.3管網共同上下游查找

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

　　2.4最短路徑分析

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

　　2.5查找源和匯

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

3結束語

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

參考文獻

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

　?。?］ 段琪慶,劉寒芳,薛冰.數字管網連通分析的淘汰算法與實現［J］.測繪科學,2008（S1）:168169.

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