最短路径算法在矿山巷道三维模型网络分析中的应用

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

矿山巷道三维模型能真实地模拟井下的工作场景,基于该模型的网络分析对煤矿井下安全救援十分重要。根据巷道的网络特点,将实际的测量数据中点状和线状元素抽象为节点-弧段图,该图的生成对应着一维中心线和二维双线巷道的构建,在此基础上根据断面的拱高、墙高及拓扑关系进行井巷模型基本单元自动的装配以及三角化生成巷道的三维模型。网络分析采用能适应拓扑变化的Dijkstra算法,从减少搜索节点和采用邻接表的存储结构两方面对传统的Dijkstra算法进行优化,并分析了算法的效率。最后编写程序实现了改进后算法在巷道三维模型中存在障碍的情况下的最短路径分析,并能在三维巷道中漫游显示,结果表明该算法快捷有效。

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.