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

摘要

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