劉子恒1,2,侯英姿1,2,王方雄1,2,張翔3
?。?.遼寧師范大學(xué) 遼寧省自然地理與空間信息科學(xué)重點(diǎn)實(shí)驗(yàn)室,遼寧 大連 116029;2.遼寧師范大學(xué) 城市與環(huán)境學(xué)院,遼寧 大連 116029;3.大連市城市規(guī)劃設(shè)計(jì)研究院,遼寧 大連 116011)
摘要:研究了城市管網(wǎng)3DGIS的連通分析方法,利用廣度優(yōu)先搜索算法根據(jù)管網(wǎng)流向信息進(jìn)行正向和反向搜索來(lái)遍歷管網(wǎng)結(jié)點(diǎn),基于SuperMap iObjects開(kāi)發(fā)實(shí)現(xiàn)了管網(wǎng)3DGIS的連通性分析、上下游追蹤、共同上下游查找、最短路徑分析、查找源和匯等連通分析功能。
關(guān)鍵詞:連通分析;廣度優(yōu)先遍歷算法;SuperMap iObjects;管網(wǎng)3DGIS
0引言
隨著城市建設(shè)步伐的加快,城市管網(wǎng)系統(tǒng)建設(shè)愈加龐雜,而管網(wǎng)連通性分析的可靠性和便捷性對(duì)可燃、易爆等管網(wǎng)系統(tǒng)的管理維護(hù)要求更加嚴(yán)格。在計(jì)算管網(wǎng)可靠性上,不同時(shí)期不同學(xué)者對(duì)城市管網(wǎng)的連通性進(jìn)行了大量研究[1]。參考文獻(xiàn)[2]在MapInfo中實(shí)現(xiàn)了以圖論為基礎(chǔ)的動(dòng)態(tài)淘汰算法的管網(wǎng)連通分析,但對(duì)有向管網(wǎng)的流向來(lái)源沒(méi)有說(shuō)明;參考文獻(xiàn)[3]通過(guò)對(duì)數(shù)據(jù)結(jié)構(gòu)變更來(lái)改寫(xiě)圖的連通性算法以縮短運(yùn)算時(shí)間,提高網(wǎng)絡(luò)連通可靠性;參考文獻(xiàn)[4]通過(guò)圖論和模糊數(shù)學(xué)理論解決管網(wǎng)連通可靠性問(wèn)題。為了更好地實(shí)現(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é)合,實(shí)現(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)幾何模型來(lái)表達(dá)管網(wǎng)拓?fù)湫畔⒑凸芫W(wǎng)流向。SuperMap SDX+空間數(shù)據(jù)庫(kù)引擎采用圖庫(kù)與分布式空間數(shù)據(jù)存儲(chǔ)方式,存儲(chǔ)各種關(guān)系的空間幾何對(duì)象,支持拓?fù)潢P(guān)系和三維數(shù)據(jù)存儲(chǔ)能力,形成空間數(shù)據(jù)和幾何數(shù)據(jù)一體化的空間數(shù)據(jù)庫(kù)。管網(wǎng)邏輯模型由管網(wǎng)結(jié)點(diǎn)數(shù)據(jù)和弧段數(shù)據(jù)拓?fù)錁?gòu)網(wǎng)而成,利用屬性表信息來(lái)表達(dá)網(wǎng)絡(luò)的連通性,具體可以通過(guò)數(shù)據(jù)集一對(duì)一和一對(duì)多的ID關(guān)聯(lián)值來(lái)表達(dá)邏輯模型和幾何模型中弧段(Edge)數(shù)據(jù)集和結(jié)點(diǎn)(Node)數(shù)據(jù)集的拓?fù)潢P(guān)系[5]。然后將管網(wǎng)模型中的閥門(mén)點(diǎn)、檢修井等構(gòu)建為管網(wǎng)幾何模型中的節(jié)點(diǎn)數(shù)據(jù)集,將管網(wǎng)模型中的管線構(gòu)建為幾何模型中的弧段數(shù)據(jù)集,管網(wǎng)中介質(zhì)的流向以源、匯數(shù)據(jù)集的網(wǎng)絡(luò)位置確定,以Direction字段值表示。在構(gòu)建設(shè)施網(wǎng)絡(luò)模型時(shí),根據(jù)管網(wǎng)源(source)、匯點(diǎn)(sink)的幾何信息創(chuàng)建管網(wǎng)數(shù)據(jù)集的BuildNetwork,自動(dòng)創(chuàng)建Direction屬性字段(如圖1(b))。
1.2管網(wǎng)鄰接矩陣
廣度優(yōu)先搜索算法(BreadthFirst Search,BFS)是管網(wǎng)空間分析常用的一種方法,目的是遍歷圖中所有結(jié)點(diǎn)進(jìn)行目標(biāo)查詢,并以此為基礎(chǔ)衍生出其他算法[6]。BFS算法實(shí)質(zhì)上是以源點(diǎn)W為起點(diǎn),向外搜索與起點(diǎn)距離為d(1,2,3,…)的未被訪問(wèn)的鄰接頂點(diǎn)p1,p2,p3,…,pi,然后分別以這些頂點(diǎn)為起點(diǎn)搜索距離為d+1的其他未被搜索過(guò)的頂點(diǎn),直到所有頂點(diǎn)都被搜索到為止。
所有管網(wǎng)在遍歷時(shí)要以有向圖為基礎(chǔ),構(gòu)建非對(duì)稱矩陣。通過(guò)設(shè)施網(wǎng)絡(luò)模型可以構(gòu)建管網(wǎng)有向圖,并根據(jù)流向信息對(duì)管網(wǎng)的每條管道構(gòu)建非對(duì)稱矩陣,其中管道環(huán)路在矩陣中是對(duì)稱的。管網(wǎng)鄰接矩陣的建立過(guò)程如下:(1)定義管網(wǎng)模型的起始點(diǎn)、終止點(diǎn)和流向字段信息;(2)根據(jù)管網(wǎng)有向圖圖例,表達(dá)管網(wǎng)介質(zhì)流動(dòng)方向,即包括起點(diǎn)到終點(diǎn)、終點(diǎn)到起點(diǎn)、管網(wǎng)環(huán)路、不連通等;(3)結(jié)合設(shè)施網(wǎng)絡(luò)模型Direction字段值與流向關(guān)系,構(gòu)建鄰接矩陣S,圖內(nèi)管點(diǎn)間關(guān)系用二維數(shù)組S[m][n]存儲(chǔ),m,n表示管點(diǎn)序號(hào);(4)根據(jù)廣度優(yōu)先搜索算法,當(dāng)S[m][n]=1時(shí),則有流向Pm→Pn。以管點(diǎn)0為起點(diǎn),在鄰接矩陣中有S[0][3]=0,S[3][0]=1,判斷管點(diǎn)0的上游是管點(diǎn)3,不參與搜索,則BFS算法下的管網(wǎng)有向圖遍歷順序?yàn)?-1-2-4-5。管網(wǎng)有向圖鄰接矩陣的建立過(guò)程如圖1所示。
1.3管網(wǎng)連通分析算法
通過(guò)BFS算法搜索每個(gè)管點(diǎn)是否為目標(biāo)點(diǎn)來(lái)判斷管網(wǎng)的連通性,而對(duì)于有向管網(wǎng)來(lái)說(shuō),在判斷管段兩端的管網(wǎng)是否連通的基礎(chǔ)上,還需標(biāo)識(shí)出管點(diǎn)的連通路徑[7]。根據(jù)管網(wǎng)流向特征,如果某段管線連通,則該連通管段下游管段的所有上游管段均經(jīng)過(guò)該管段,即利用BFS算法反向搜索管點(diǎn)并記錄管段連通的路徑[8]。搜索與起點(diǎn)P0鄰接的上游管點(diǎn),當(dāng)S[m][0]=1時(shí),則Pm的上游鄰接管點(diǎn)為P0,這在管網(wǎng)環(huán)路中同樣成立, BFS算法反向搜索具體流程如圖2(cmpPoint為已搜索過(guò)的管點(diǎn),wilPoint為即將搜索的鄰接管點(diǎn),nonPoint為未搜索過(guò)的管點(diǎn))。
2管網(wǎng)連通分析功能實(shí)現(xiàn)
城市燃?xì)夤芫W(wǎng)連通分析功能的實(shí)現(xiàn)以 SuperMap iObjects組件技術(shù)為支撐,在有向管網(wǎng)鄰接矩陣的基礎(chǔ)上,通過(guò)管網(wǎng)設(shè)施網(wǎng)絡(luò)數(shù)據(jù)模型,以BFS算法為基礎(chǔ)根據(jù)管網(wǎng)流向進(jìn)行正向和反向搜索,實(shí)現(xiàn)管網(wǎng)系統(tǒng)的連通性分析、上下游追蹤、共同上下游查找、最短路徑分析、查找源和匯等。
2.1管網(wǎng)連通性分析
連通性分析主要是判斷管點(diǎn)間管網(wǎng)的連通性,通過(guò)利用BFS算法判斷燃?xì)夤芫W(wǎng)的兩個(gè)管點(diǎn)之間是否連通,并在MapControl中標(biāo)識(shí)出連通的路徑。根據(jù)流向字段信息關(guān)系(SmFNode、SmTNode、Direction),用二維數(shù)組array記錄所有管網(wǎng)鄰接矩陣的管點(diǎn),通過(guò)調(diào)用FacilityAnalystResult類(lèi)的FindPathFromNodes方法獲取SmFNode、SmTNode的ID字段值和QueryParameter類(lèi)庫(kù)定義的SQL查詢語(yǔ)句匹配管網(wǎng)閥門(mén)的OnlyID,記錄符合條件的ID數(shù)組,然后利用FindConnected EdgesFromNodes方法獲取與節(jié)點(diǎn)ID數(shù)組連通的設(shè)施網(wǎng)絡(luò)模型弧段,用GeoStyle類(lèi)記錄線狀路徑的風(fēng)格屬性;在SceneControl中通過(guò)Point3D定義相對(duì)應(yīng)的管點(diǎn),用GeoStyle3D類(lèi)設(shè)置三維場(chǎng)景中管點(diǎn)風(fēng)格符號(hào)。分析結(jié)果如圖3(兩個(gè)管點(diǎn)均在管網(wǎng)環(huán)路上)。
2.2管網(wǎng)上下游追蹤
燃?xì)夤芫W(wǎng)上下游追蹤分為上游追蹤和下游追蹤,使用BFS算法基于流向進(jìn)行正向和反向搜索計(jì)算并標(biāo)識(shí)出燃?xì)夤芫W(wǎng)目標(biāo)要素的上游和下游路徑。具體通過(guò)調(diào)用Point2D和Point3D分別在MapControl和SceneControl中選取一個(gè)管點(diǎn),并使用GeoStyle和GeoStyle3D類(lèi)設(shè)置點(diǎn)狀符號(hào)風(fēng)格;利用FacilityAnalystResult類(lèi)的TraceUp FromNode和TraceDownFromNode方法,分別根據(jù)給定的nodeID進(jìn)行上下游追蹤,利用BFS算法查找該節(jié)點(diǎn)的上下游連通節(jié)點(diǎn),利用FindConnectedEdgesFromNodes查找并返回與節(jié)點(diǎn)連通的弧段集合,用GeoStyle類(lèi)記錄并設(shè)置線狀符號(hào)風(fēng)格屬性。上游追蹤分析結(jié)果如圖4?!?/p>
2.3管網(wǎng)共同上下游查找
共同上下游查找,即查找兩個(gè)管點(diǎn)的共同上游和共同下游,并標(biāo)識(shí)出查找路徑。在mapControl和SceneControl窗口分別通過(guò)Point2D和Point3D定義兩個(gè)管點(diǎn),并設(shè)置GeoStyle和GeoStyle3D類(lèi)的點(diǎn)狀符號(hào)風(fēng)格,通過(guò)FacilityAnalyst 類(lèi)調(diào)用FacilityAnalystResult、FindCommonAncestorsFromNodes和FindCommonCatchmentsFromNodes方法,查找兩管點(diǎn)的共同上下游弧段,并返回弧段集合,用GeoStyle類(lèi)設(shè)置弧段路徑風(fēng)格符號(hào)。查找共同下游結(jié)果如圖5。
2.4最短路徑分析
最短路徑分析是指在設(shè)施網(wǎng)絡(luò)模型中,根據(jù)管網(wǎng)流向和管網(wǎng)長(zhǎng)度權(quán)值來(lái)計(jì)算最短路徑的過(guò)程。最短路徑的計(jì)算以管段的長(zhǎng)度值為參考,即通過(guò)給定的起始點(diǎn),根據(jù)流向信息和BFS算法采用正向和反向搜索遍歷到終止點(diǎn)的路徑,根據(jù)長(zhǎng)度權(quán)值選擇最短返回路線。首先根據(jù)給定的起始點(diǎn)和終止點(diǎn)ID,利用BuildFacilityNetworkDirections方法正反BFS搜索,直到搜索到終止點(diǎn)ID,通過(guò)FacilityAnalyst類(lèi)調(diào)用FacilityAnalystResult和 FindPathFromNodes方法,根據(jù)SmLength權(quán)值獲取到最短路徑。
2.5查找源和匯
查找源和匯指在設(shè)施網(wǎng)絡(luò)模型中根據(jù)指定的管點(diǎn),按照流向信息查找流向該管點(diǎn)最近的源點(diǎn)或下游匯點(diǎn)。首先判斷該管點(diǎn)ID所在的管段,根據(jù)流向Direction字段信息使用反向BFS搜索算法查找最近的源點(diǎn),使用正向BFS算法查找該管點(diǎn)的下游匯點(diǎn)。具體通過(guò)給定管點(diǎn)ID匹配管線起始點(diǎn)或終止點(diǎn)ID并判斷該管線流向,利用反向BFS算法記錄所有符合條件的管點(diǎn)ID并存儲(chǔ)在二維數(shù)組中,通過(guò)調(diào)用FacilityAnalystResult類(lèi)的FindSourceFromNode方法查找流向該管點(diǎn)的源點(diǎn),并在FindConnectedEdgesFromNodes中查找與管點(diǎn)相連通的管段集合,在GeoStyle中設(shè)置結(jié)果顯示風(fēng)格。查找源點(diǎn)結(jié)果如圖6。
3結(jié)束語(yǔ)
管網(wǎng)3DGIS的連通分析,首先要解決管網(wǎng)數(shù)據(jù)模型的拓?fù)潢P(guān)系,其次針對(duì)管網(wǎng)介質(zhì)的流動(dòng)性,分析管網(wǎng)流向?qū)B通分析的影響?;诹飨虻脑O(shè)施網(wǎng)絡(luò)模型在燃?xì)夤芫W(wǎng)連通分析中,利用BFS基礎(chǔ)算法,采用正向和反向搜索遍歷管網(wǎng)中管點(diǎn)和管段關(guān)系,解決了燃?xì)夤芫W(wǎng)在流向和環(huán)路上的連通分析問(wèn)題,包括管網(wǎng)的連通性分析、上下游追蹤、共同上下游查找、最短路徑分析、查找源和匯等連通分析功能,對(duì)管網(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): 5866.
?。?] 段琪慶,劉寒芳,薛冰.數(shù)字管網(wǎng)連通分析的淘汰算法與實(shí)現(xiàn)[J].測(cè)繪科學(xué),2008(S1):168169.
[3] 陸鳴盛,沈成康.圖的連通性快速算法[J]. 同濟(jì)大學(xué)學(xué)報(bào)(自然科學(xué)版),2001,29(4):436439.