最短路徑算法在礦山巷道三維模型網絡分析中的應用

車德福 陳軍偉 趙西亭

(東北大學資源與土木工程學院,遼寧 沈陽 110819)

最短路徑算法在礦山巷道三維模型網絡分析中的應用

車德福 陳軍偉 趙西亭

(東北大學資源與土木工程學院,遼寧 沈陽 110819)

礦山巷道三維模型能真實地模擬井下的工作場景，基于該模型的網絡分析對煤礦井下安全救援十分重要。根據巷道的網絡特點，將實際的測量數據中點狀和線狀元素抽象為節點-弧段圖，該圖的生成對應著一維中心線和二維雙線巷道的構建，在此基礎上根據斷面的拱高、墻高及拓撲關系進行井巷模型基本單元自動的裝配以及三角化生成巷道的三維模型。網絡分析采用能適應拓撲變化的Dijkstra算法，從減少搜索節點和采用鄰接表的存儲結構兩方面對傳統的Dijkstra算法進行優化，并分析了算法的效率。最后編寫程序實現了改進后算法在巷道三維模型中存在障礙的情況下的最短路徑分析，并能在三維巷道中漫游顯示，結果表明該算法快捷有效。

最短路徑算法 Dijkstra 三維模型 巷道網絡 漫游

巷道是礦山中最重要的空間要素，具有三維網絡特征。通過計算機技術對礦山巷道的基礎數據進行管理實現礦山巷道的三維模型的構建，能真實地模擬井下的工作場景，提高礦山的管理水平及工作效率。國內外大量學者對礦山巷道的交互建模問題開展了研究，國外已有多家公司推出了商業化三維數字礦山建模軟件(如Lynx，Surpac，GOCAD，Micromine，CTech，EarthVision等)，上述軟件的3D功能大多集中在3D建模的可視化方面，空間分析功能則顯得不足[1]。網絡分析是空間分析的一個重要方面，最短路徑分析在網絡分析中占據著主導地位，因此深入地研究最短路徑算法在礦山三維巷道網絡分析中的應用就顯得十分必要。

本研究從巷道具有網絡的特點出發，首先對巷道數據進行了組織，給出了構建巷道三維模型的方法，基于優化的Dijkstra算法在構建的模型中進行最短路徑分析，最后在三維巷道模型中漫游顯示，對礦山安全問題中的避災救險有一定的幫助。

1 礦山三維巷道網絡數據的組織

礦山巷道一般是根據開采水平(簡稱水平，指地下采煤時，將井田沿傾斜方向按一定高度劃分的開采范圍)、采區(在階段范圍內，沿走向把階段劃分為具有獨立生產系統的塊)、工作面(直接進行采掘或排碴的場所)、工作地點(巷道名稱)區分的。巷道網絡空間數據具有以下特點[2]：①整個巷道網絡可以按照開采水平來劃分，例如-450 m水平、-600 m水平等，不同開采水平通過井筒聯系；②某一開采水平的巷道網絡除了井底車場附近處較為稠密外，其他地方一般都比較稀疏，如運輸大巷、采區上下山等；③巷道網絡中存在有很多硐室，硐室就是為某種專門用途在井下開鑿和建造的斷面較大或長度較短的空間構筑物。

要對巷道網絡進行路徑分析，就需要構建巷道網絡數據間的拓撲關系，本研究從圖的角度出發，將現實世界中的巷道地理網格抽象成節點-弧段圖，然后基于圖來解決巷道網絡分析問題。

根據以下原則把巷道測量數據轉換成節點-弧段圖的節點：①所有巷道交叉處應設置成節點；②考慮到轉彎限制對權值的影響，巷道轉彎處也應設置成節點；③所有的設施處應設置成節點，如水倉、泵房、風機房、變電所、主副井、儲藏室、硐室等；④考慮到巷道三維模型的構建都使用測量成果，所有測量點也作為節點。

弧段對應著巷道網絡中的線狀元素，可以把運輸大巷、切眼等巷道的中心線抽象為弧段。在最短路徑救援時用巷道的長度表示弧段的權值。根據以上原則轉化的結果如圖1所示。

圖1 巷道中心線節點-弧段圖

2 礦山巷道三維模型的構建及漫游顯示

巷道三維模型的構建主要包括一維中心線建模，二維雙線巷道建模，三維井巷工程建模等步驟[3]。

一維中心線建模：井巷工程中心數據由導線生成，通過交叉點數據的檢測與計算、彎道數據的離散擬合與中心線拓撲關系建立等，生成具有拓撲關系的井巷工程中心線網絡(網絡上的每一條線段即是一段巷道)，這個網絡是巷道空間分析、巷道漫游等功能實現的基礎。

二維雙線巷道建模：就是建立通常圖紙資料上的二維井巷工程雙線輪廓，基于已經建立的一維中心線網絡模型，根據每一段巷道的寬度、方位角以及其他參數，計算雙線巷道邊線交點的坐標，從而構建二維雙線巷道。

三維井巷工程建模：根據生成的雙線巷道、每一斷面的拱高、墻高及其拓撲關系，按一定的規則進行井巷模型基本單元自動的裝配，進行必要的三角化，進而生成井巷工程的三維模型。

虛擬漫游技術是基于地理信息技術、虛擬現實技術、計算機技術等高新技術的一種應用[4]。經過一定的算法與智能化設計，建立與現實相一致的虛擬場景，用戶能在場景自由地瀏覽和查詢，有身臨其境的感覺。OpenGL 所具有的平移、縮放、旋轉等功能為實現三維場景的實時動態漫游提供了保證，借助OpenGL，建立三維模型場景庫，建立虛擬三維場景空間，實現的過程主要包括漫游路徑的設計、漫游控制、碰撞檢測以及模型簡化等關鍵技術[3]。

3 最短路徑算法

最短路徑算法中Dijkstra 算法由于能適應網絡拓撲的變化 ，性能穩定 ，因而在計算機網絡拓撲路徑選擇以及GIS中得到廣泛的應用。傳統的Dijkstra算法[5]用于尋求從一個固定起點到其余各點的最短路徑，是典型的單源最短路徑算法，主要特點是以起始點為中心向外層擴展，直到擴展到終點為止。

Dijkstra算法的基本思路[5-6]是：按路徑長度遞增的順序，逐個產生各節點j最短路徑。設G=(V,E)是一個賦權圖，把圖中頂點集合V分成2組，第1組為已求出最短路徑的頂點集合(用S表示，初始時S中只有1個源點，以后每求得1條最短路徑，就將加入到集合S中，直到全部頂點都加入到S中，算法就結束了)；第2組為其余未確定最短路徑的頂點集合(用U表示)，按最短路徑長度的遞增次序依次把第2組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應1個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。傳統Dijkstra算法比較簡單，容易實現，理論上，用該算法解決最短路徑問題已經很成熟。

3.1 Dijkstra 算法的優化

礦山事故發生時，為保證最快速度搜索到最優避災路徑，采取基于Dijkstra算法的改進算法來進行路徑搜索。針對礦山巷道的網絡空間分布特點，考慮到傳統算法以鄰接矩陣方式存儲數據，造成大量空間的浪費，而且難以全面地描述真實的巷道網絡信息，如節點的屬性信息及弧的屬性信息等。對Dijkstra算法從時間和存儲空間2個方面進行改進。

(1)時間上：根據縮小搜索區域的思想[7-8]，根據巷道的點—弧段圖的實際場景，通過減少搜索的節點數目實現。

(2)存儲空間上：巷道網絡為大型稀疏網絡，考慮采用鄰接鏈表的方式來描述巷道網絡的連通關系及屬性信息。

3.1.1 Dijkstra 算法時間方面的優化

巷道數據抽象成的節點-弧段圖有很多不必要的節點，因此可以通過對巷道網絡圖簡化來減少算法的搜索時間。

巷道網絡中存在很多硐室，如圖1中E1-E2為例，在路徑分析中，節點E2的弧段連接數為1，如果節點E2既不是起始節點，又不是終止節點外，路徑分析中肯定不會經過節點E2，所以可以將節點E2和節點E1的鄰接邊E1-E2去除。然后，對路徑初始化，將與起始節點S有鄰接關系的所有弧段，加入到路徑鏈表中，并且對其做標記，表示已經對該弧段搜索。接著進行路徑搜索，分別對與路徑鏈表中節點(與前一個節點對應)有鄰接關系的弧段搜索，并對其做標記，如果該弧段的另一節點已經在路徑中存在，比較該節點路徑權值大小，將較小節點加入路徑。直至搜索到終止點。最后，選擇起始節點與終止節點間的最短路徑。從終止節點開始搜索其前一個節點，搜到起止節點為止。

3.1.2 Dijkstra算法存儲空間方面的優化

礦山巷道網絡的拓撲結構復雜，數據量大,設圖有n個節點，用傳統鄰接矩陣存儲結構，其空間復雜度為 。礦山巷道網絡抽象的節點-弧段圖屬于稀疏圖(每個巷道交叉口所連接的巷道一般為2～5個，巷道的數目遠遠小于 )。適宜采用鄰接表存儲結構，它既能節省存儲空間也容易實現，且可根據需要擴充數據域，有利于全面反映礦山巷道的網絡特征。

路徑存儲采用單向鏈表的數據結構如表1所示。

表1 路徑的數據結構

節點與弧段的鄰接表存儲結構用C++語言描述為

class CNonGraVex

{

頂點坐標以及標識等屬性；

繪制特殊顯示等基本方法；

};

class CNonGraArc

{

弧尾標識以及弧的權重；

BOOL mark;∥最短路徑路線標識；

BOOL Arcmark;∥弧的標記,是否有障礙；

相關的的操作；

};

3.2 Dijkstra算法改進后效率分析

在實際的礦山巷道中，如果某一平巷內出現瓦斯涌出量過高、坍塌、涌水、冒頂或火災等危險障礙，導致該平巷不能通行，就需要考慮如何避開這些事故路段到達目的地。把該因素考慮進去后改進的Dijkstra最短路徑分析搜索方法總結如下。

Step1：確定要搜索的起止節點，并對節點-弧段圖進行簡化；

Step2：初始化起始節點的路徑，將路徑中的每一個弧段都定義成∞，不可通過；

Step3：對路徑節點逐步搜索、更新路徑，直至搜到終止節點，并將路徑中的各個節點都記錄下來，并記錄路徑的長度；

Step4：選擇出起止節點間的最短路徑，并將最短路徑用可區分的顏色顯示出來。

Step5：對于出現事故的路段進行“添加障礙”的標志，將事故路段定為不通，然后重復上述的4步重新搜索新路徑，將路徑更新。

算法效率分析[9-11]：假設初始節點-弧段圖有n個節點。第1步中對所有節點循環，其時間復雜度為O(n)。第2步中對所有節點循環，時間復雜度為O(n)。第3步中，第1次循環為與起始點相鄰的弧段的數目m，第2次循環次數為m-1加上與第1次找到的頂點直接相鄰的弧段的數目。以此類推，直到所有節點搜索完畢為止。最壞情況下，也就是這n個節點之間都有直接相鄰關系，那么每次循環次數為(n-1),(n-2),…,1，那么其時間復雜度是它們的和為O(n2)。第4步中，對所有保存路徑循環，最壞情況下為所有弧段個數T，其時間復雜度為O(n2)。因此改進的Dijkstra最短路徑分析方法的時間復雜度為max{O(n),O(n2),O(n)}，即為O(n2)。這與Dijkstra最短路徑分析方法的時間復雜度一致，但是注意到實際礦山網絡數據中，巷道弧段個數T?n2，所以此改進算法可以有效地消除大量的冗余存儲和計算，很大程度上提高算法效率。

4 仿真實現

設計程序首先構建三維模型，單擊屏幕選擇搜索的起點和終點，使用Dijkstra算法確定出最短路徑，并用綠色標識出來。對于出現障礙的路徑，通過設置變量的值，重新建立拓撲關系，找出當前的最短路徑，具體實現如下：

讀取巷道數據庫中的導線數據，根據節點之間的拓撲關系建立起節點-弧段圖，構建巷道，巷道三維模型主要是由雙線巷道以及巷道三角面構成，如圖2所示。

圖2 礦山巷道三維模型

在巷道模型中，根據實際巷道中避災的需要選擇起點和終點，選擇菜單中的“巷道最短路徑搜索”，得出最短路徑并標示出來，如圖3所示。

圖3 巷道最短路徑搜索

如果巷道中存在安全隱患或出現事故時，某條巷道可能會不通。當前的路徑肯定要發生變化，將發生事故段用紅線標出，表示此路不通，對應地在程序中就是添加1個障礙，并將表示該弧段的標記變量Arcmark更改為“TRUE”，清除當前路徑，重新建立拓撲關系，得到有障礙的最短路徑，如圖4所示。

圖4 有障礙時的最短路徑

對于建立的最短路徑，可以在其中進行漫游，清晰地查看最短路徑中各個巷道的連接以及避災時的行走路徑，如圖5所示。

圖5 最短路徑巷道內部漫游

5 結 語

從巷道具有網絡的特點出發，對傳統的Dijkstra算法進行了改進，能有效地減少節點搜索范圍和計算復雜度，將其應用到礦山巷道網絡最短路徑的分析中，在礦山巷道三維模型中漫游顯示，能真實地再現巷道的場景，對礦山的安全救援有一定的幫助。最短路徑分析等網絡分析一般是在瓦斯監測系統實時監測、預警危險，視頻監控系統提供的當前巷道的視頻信息，人員定位系統提供的人員實時位置信息的基礎上實施的，與這3大系統的集成能使礦山管理人員更方便地做出決策，提高管理水平，這也是今后工作的研究方向。

[1] 車德福，吳立新．數字礦山基礎平臺——GeoMo3D的功能結構與應用[C]∥第七屆全國礦山測量學術會議論文集．北京:中國煤炭學會,2007：142-148． Che Defu，Wu Lixin.Functional structure and application of the basic Information platform of digital mine：GeoMo3D[C]∥The Proceedings of the Seventh National Academic Meeting on Mine Surveying.Beijing：China Coal Society,2007：142-148.

[2] 丁宜晨．井下工程交互設計系統研發及應用[D]．沈陽：東北大學，2012． Ding Yichen.Research of Three-Dimensional Interactive Design Subsystem for Sinking and Drifting Engineering and Its Applications[D].Shenyang：Northeastern University，2012.

[3] 高光亮．基于煤礦井三維模型的漫游查詢模塊研究與實現[D]．沈陽：東北大學，2013． Gao Guangliang.Research and Implementation of Roam-query Module Based on Three-dimensional Coal Mine Models[D].Shenyang：Northeastern University，2013.

[4] 劉林濤.建筑場景虛擬漫游關鍵技術的研究和實現[D] ．蘇州：蘇州大學，2008. Liu Lintao.Research and Implement of Key Technology for Virtual Architecture Environment[D].Suzhou：Soochow University，2008.

[5] 張渭軍，王 華．城市道路最短路徑的Dijkstra算法優化[J]．長安大學學報：自然科學版，2005，25(6)：62-65． Zhang Weijun，Wang Hua.Optimization dijkstra arithmetic for shortest path of urban traffic net[J].Journal of Chang'an University:Natural Science ，2005,25(6):62-65.

[6] 王戰紅，孫明明，姚 瑤．Dijkstra算法的分析與改進[J]．湖北第二師范學院學報，2008，25(8)：12-14． Wang Zhanhong，Sun Mingming，Yao Yao.Analysis and improvement of dijkstra algorithm[J].Journal of Hubei University of Education，2008，25(8):12-14.

[7] 鄭四發，曹劍東，連小珉．復雜路網下多客戶間最短路徑的扇面Dijkstra算法[J]．清華大學學報：自然科學版，2009，49(11):1834-1837. Zheng Sifa，Cao Jiandong，Lian Xiaomin.Sector dijkstra algorithm for shortest routes between customers in complex road networks[J].Journal of Tsinghua University：Science and Technology，2009，49(11):1834-1837.

[8] 董 俊，黃傳河．改進Dijkstra算法在GIS導航應用中最短路徑搜索研究[J]．計算機科學，2012，39(10):245-247. Dong Jun，Huang Chuanhe.Research on shortest path search of improved dijkstra algorithm in GIS navigation application[J].Computer Science，2012，39(10):245-247.

[9] 蔚 潔，楊懷雷，成汝震．基于Dijkstra算法的最優路徑搜索方法[J]．河北師范大學學報：自然科學版，2008，32(5)：590-598． Yu Jie，Yang Huailei，Cheng Ruzhen.The research and application of formal requirement analysis method based on evolved component[J].Hebei Normal University：Natural Science Edition，2008，32(5):590-598.

[10] 王兆南．基于Dijkstra算法改進的海量數據最優路徑計算方法研究與實現[J]．測繪通報，2012(9)：32-37． Wang Zhaonan.Mass data optimal path searching using an improved dijkstra algorithm[J].Bulletin of Surveying and Mapping，2012(9)：32-37.

[11] 姜鳳輝，李樹軍，姜鳳嬌，等．基于GIS的Dijkstra改進算法及其在交通導航系統中的應用[J]．測繪與空間地理信息，2011，34(4)：129-131． Jiang Fenghui，Li Shujun，Jiang Fengjiao，et al.The dijkstra algorithm improved a navigation system and its application in the traffic based on GIS[J].Geomatics & Spatial Information Technology.2011，34(4)：129-131.

(責任編輯 石海林)

Application of Shortest Route Algorithm in Network Analysis of 3D Tunnel Modeling

Che Defu Chen Junwei Zhao Xiting

(CollegeofResourcesandCivilEngineering，NortheasternUniversity，Shenyang100819，China)

Three dimensional model of mine tunnel can simulate the work scene at the ground mine，the network analysis based on it is very important for coal mine rescue.According to the network's characteristic of mine tunnel，the point and linear elements in the actual measurement data is abstracted to node-arc ADT，which corresponds to the construction of one-dimensional center line and two-dimensional double line tunnel.In the end，three-dimensional model of the mine tunnel is generated by using arch height of the section，wall height and topological relations to assemble the basic unit of laneway model and triangulation.Network analysis adopts Dijkstra algorithm which can adapt to topology changes，to optimize the traditional Dijkstra algorithm in reducing the search nodes and using the adjacency list storage structure，and then analyze the efficiency of the algorithm.Finally，a program is written to test the shortest path algorithm's analysis in the three dimensional model of mine tunnel with obstacles and make it roam in the model.The results show that the algorithm is fast and effective.

Shortest route algorithm，Dijkstra，3D model，Tunnel network，Roam

2015-02-03

車德福(1970—)，男，教授，博士。

TD178

A

1001-1250(2015)-04-273-05