矿山复杂巷道网络组件式三维建模方法

2020-12-18贾庆仁车德福钟壬清

东北大学学报（自然科学版） 2020年12期

贾庆仁，车德福，钟壬清

(东北大学资源与土木工程学院，辽宁沈阳 110819)

巷道是开展煤矿生产活动的重要场所.由于煤层开采活动会在多个地层上同时开展，使用传统二维图纸表达多层巷道空间关系会存在空间位置不直观的问题，甚至产生空间冲突.并且人工绘制二维巷道网络图工作较为繁重.三维巷道模型能够更直观地展示井巷工程之间、井巷工程与地质体之间的空间关系.在三维巷道模型上开展空间分析，更可对救灾避险、员工作业、井下通风等工作提供辅助，对矿山安全生产、降低财物与人员的伤亡损失意义重大[1].将巷道三维模型建立为实体模型，有助于进一步分析围岩力学性质[2].因此研究巷道三维自动建模方法具有重要意义.

当前，已有学者针对三维巷道建模提出了多种方法，并开发了多种原型系统.文献[3-4]提出由巷道测量导线点计算巷道中心线，并结合断面进行巷道三维建模的断面中线法；汪云甲等[1]通过对巷道中心线网络的分析，提出由二维巷道数据自动建模三维巷道的方法；张志华等[5]从巷道的中心线对称性出发提出了对称建模法；文献[6]通过激光雷达获取到的点云数据，可以建立高精度的巷道三维模型[7].

对巷道交叉口的无缝建模是巷道三维建模的难点[5].为顾及井下轨道行车安全，巷道交汇处、转向处往往需要将巷道设计为曲线线路，并通过抬高外轨道提供向心力，保障行车安全.因此，曲线巷道在煤矿应用广泛，其存在也为巷道交汇点的三维建模增加了困难.目前，复杂巷道三维建模方法主要有断面离散法[3]、中心线交汇法[8]和对称建模法[5].断面离散法和中心线交汇法能够为简单巷道交汇建模，但是不具备对曲线巷道、曲线巷道交汇建模处理能力；对称建模法能够处理各类巷道交汇问题，但使用该方法的前提是已存在巷道双边线数据，无法从导线测量数据自动建模三维巷道网络模型；基于点云数据的建模结果精度高，但数据采集成本较高、建模效率低于测量导线数据.

在煤矿实际工作中，巷道导线测量数据是巷道主要的空间数据，基于测量导线数据建立的巷道三维模型可以满足现有应用场景中(人员定位、巷道掘进体积计算等)的精度需求.为实现煤矿巷道建模工作的自动化，如何通过巷道导线测量数据自动生成含曲线巷道、交汇巷道的复杂巷道网络三维模型成为值得研究的关键问题.

1 巷道基本组件定义与三维建模

首先定义了巷道基本组件的概念，然后提出了基本组件的三维建模方法.在此基础上简要介绍了组件法构建复杂巷道三维模型的思路，即将复杂巷道网络三维建模问题转化为二维巷道基本组件划分问题.

1.1 巷道基本组件定义

通过分析图1a，1d中巷道模型的几何和拓扑特征，抽象出了矿井模型的基本组件(basic component of roadway, BCR)，BCR定义如下：①BCR为组成巷道模型的最小几何结构单元；②每一段巷道都被通过巷道中心线的垂面分割为两个BCR.

BCR有两种表现形式：二维形式(2D-BCR)和三维形式(3D-BCR).其中，2D-BCR包含巷道中心线和单侧边线(图1b).3D-BCR包含巷道半侧顶、底面和单侧面(图1e).在封闭巷道处还应包括两端半断面，且两断面类型不一定一致，高、宽不一定相等，也不一定平行.通过拓展两端半断面并进行三角剖分后，可以将2D-BCR建模为3D-BCR.BCR具有退化能力，2D-BCR中的巷道边线可以退化为一个点(图1c)，在3D-BCR中则表现为巷道侧面退化为线(图1f).BCR的退化能力是构建曲线交叉巷道三维模型的基础.

图1 巷道基本组件示意

1.2 巷道基本组件三维建模

巷道基本组件每个面的三角剖分需在局部坐标系下进行，再将结果转换到全局坐标系完成建模.全局坐标系和局部坐标系均采用右手三维直角坐标系.全局坐标系是用于多个空间对象在场景中定位的统一参照系；局部坐标系是为方便构造单个对象而定义的坐标系，它独立于世界坐标系，其原点位置和坐标轴方向可根据用户需要自由定义.通过指定局部坐标系在全局坐标系中的位置和姿态，可以将空间对象纳入全局坐标系内(图2a).

图2 计算巷道断面离散点

(a)—全局坐标系中的BCR； (b)—局部坐标系.

巷道断面类型取决于支架类型.岩石稳定性及使用年限的不同影响井下支架类型的选取[3].梯形断面多采用木材支架，可短期使用或用于支护较稳固的岩壁；拱形断面一般采用混凝土支架，可长期使用或用于支护岩石不稳固的岩壁.本文对任意断面形状顶端都采用等分段的离散划分方式，以便于实现三角剖分.以直壁圆拱形半断面为例(图2b)，以巷道中心线上的点O作为局部坐标系原点，根据巷道断面的宽度W和高度H，对巷道拱形部分进行微分处理可以精确地模拟巷道断面.

由于3D-BCR是一个顶面、底面、侧面相对规则的三维几何体，可通过对顶面、底面、侧面三个面分别进行三角剖分获得完整的3D-BCR.其中，顶面和底面可以投影为梯形，可连接两侧断面顶部离散点完成剖分.侧面则为平行四边形，可直接连接对角点将其划分为两个三角形完成剖分.图3展示了不同断面的巷道BCR顶面的三角剖分结果.

图3 变断面巷道基本组件顶面建模

2 巷道网络组件式三维建模方法

基于BCR及其三维建模方法的定义，可将三维复杂巷道网络建模问题转化为二维BCR划分问题.即通过组合巷道中心线和边线构建2D-BCR，然后对每个2D-BCR分别建模完成.基于此思路，本文解决了2D-BCR划分问题，并提出了复杂巷道网络组件式三维建模法.

2.1 方法流程

巷道组件式三维建模法构建巷道网络三维模型主要包括巷道网络中心线建模、二维巷道基本组件划分、三维巷道基本组件建模3个步骤(图4).

图4 复杂巷道网络组件式三维建模法流程图

步骤描述：

1) 巷道中心线建模.巷道中心线数据可以从测绘资料中由导线生成，也可以从二维测绘、设计图纸资料提取.此过程需要交叉点数据的检测与计算、弯道数据的离散拟合与中心线拓扑关系建立等辅助工作.最后生成的是具有拓扑关系的巷道中心线网络，网络上的每一条线段即代表一段巷道，该网络可用于实现人员定位、最短路径搜索等[9-10].

2) 巷道基本组件划分.为解决该问题，本文基于对建立的中心线网络的分析和深度优先遍历，提出了一种复杂巷道网络边线生成算法.通过该算法建立二维巷道双边线模型，然后将生成的边线数据分配到其对应的中心线，可将整个巷道划分为2D-BCR的集合.

3) 巷道基本组件建模.对每个生成的巷道2D-BCR，根据其巷道中心线、双边线，以及两端半断面数据(包括每一断面的形状、拱高、墙高等)，按1.2节给出的建模方法建立3D-BCR.组合后的建模结果即为巷道网络三维模型.

上述3个建模步骤中，步骤1) 中的巷道中心线建模可以通过导线数据直接计算.步骤3) 中BCR的三维建模方法已经给出.因此，重点讨论并给出步骤2) 中的边线生成算法及2D-BCR划分方法.

2.2 基本组件划分

在组件法中，2D-BCR表达为一组相互对应的中心线段和边线段.因此，计算获得巷道双边线是划分2D-BCR、建模三维巷道网络的基础[5].

现有的研究中，巷道双边线数据大多由人工绘制.为自动生成巷道双边线模型，文献[11]提出可由中心线提取获得所有闭环后，偏移生成双侧边线的“闭环法”等.但是由于井下巷道之间并不是理想化的线段相接，真实巷道中存在曲线巷道交汇等复杂情况，通过上述方法提取中心线闭环后，在交汇巷道，尤其是曲线巷道交汇处会出现计算错误，导致巷道三维建模结果出现表面冲突或非闭合现象.

为解决上述问题，引入计算机图论中的双向图来构建巷道中心线网络，提出了一种基于深度优先遍历的巷道双边线生成方法.该方法通过对巷道中心线节点网络进行深度优先遍历，并在此过程中计算边线的连接和拓扑，从而计算获得二维巷道双边线图.该方法能实现曲线巷道、交汇巷道等各种复杂情况下的巷道双边线的建立，并通过组合中心线与边线解决BCR划分问题.

1) 建立巷道中心线双向图.双向图(bidirectional graph)是一种有向图，将无向图中边{x,y}替换为一对边{ (x,y),(y,x)}后，即可从该无向图获得双向图.首先基于计算机图论对井下复杂巷道中心线及节点进行建模，将其转换成一个双向的网络连接图(巷道中心线双向图)，为巷道双边线建模奠定基础.

在建立巷道中心线双向图时，巷道中心线可抽象成网络图的边，巷道中心线的端点和节点则可作为图中的结点.则巷道中心线双向图可表述为

G=(V(G),E(G)),
V(G)={vi,1≤i≤n},
E(G)={eij(vi,vj),eji(vj,vi)|vi,vj∈V}.

式中:G表示巷道中心线双向图;V(G)是双向图中非空结点v的集合;n为结点数目，即巷道中心线节(端)点个数;E(G)为双向图中边的集合;eij表示连通结点vi与结点vj的巷道中心线.

通过结合顺序存储结构与链式存储结构，可用邻接表来表达双向图的拓扑邻接信息.使用顺序结构存储双向图中的结点信息，再对每一个结点建立一个单链表，存储与该结点邻接的结点.

2) 巷道双边线的深度优先遍历.获得巷道中心线网络双向图后，提出基于双向图的深度优先遍历的双边线生成方法.由于深度优先遍历算法可优先获得一条连续、完整的子路径，因此可以用来获得原始边线段的拓扑顺序，然后将边线段拼接成巷道单侧连续边线多段线.多次执行深度优先遍历，获得巷道两侧连续边线多段线后，可将多段线的每一子段与原始中心线段一一组合，获得的BCR集合可用于组建巷道网络三维模型.

对于给定的包含n条巷道中心线的双向图，从任意叶结点出发，按照深度优先原则遍历整个图.双向图G(V,E)的深度优先遍历过程可以描述为从图G的某个顶点v0出发，依次访问与该点相邻且未从该点访问的顶点vk.直至所有顶点和有向边都被访问.图5a所示巷道中心线双向图中，深度优先遍历所有结点和有向边的具体流程如下：

①选择起始结点.起始结点应优先选择网络末端结点(v1)，在完全闭环的情况下可选则与未被访问有向边连接的任意结点作为起始点.

②访问下一结点.在每个结点处，始终访问未被访问的有向边(如v1处访问e12)及指向的下一结点.在多边交汇处，始终按照右手原则选择下一结点.访问回到v1时终止(图5b).

③闭环处理.检查是否已访问所有有向边.如存在边未被访问，则存在闭环.反复执行步骤①～③，直至所有的有向边都被访问.图5c中，由于存在闭环，通过两条路径才完成访问全部有向边.

图5 双向图深度优先遍历

3) 巷道双边线计算及巷道基本组件划分.

为了定义巷道双边线计算方法，首先定义部分遍历过程中涉及到的名词.

度：表示结点处巷道的联通关系.度大小代表连接的巷道段数目.如图5a中结点v1的度为1，结点v2的度为3.

叶结点：度为1的结点称为叶结点，标志巷道在此处终止.如图5a中v1,v4为叶结点.

过渡结点：度为2的结点称为过渡结点.如图5a中v5,v6为过渡结点.

根据上述定义和描述，提出基于中心线双向图的深度优先遍历的巷道双边线计算方法(图6).

图6 基于深度优先遍历的巷道双边线自动生成方法流程图

对于给定的包含n条巷道中心线的拓扑图，该方法从任意叶结点出发，按照深度优先原则遍历整图.在此过程中，将2n条从巷道中心线偏移生成的、独立的边线段按照规则分组，并拼接形成巷道双边线多段线集合PL={pli,i=1,2,…,m}，得到拓扑正确的巷道双边线模型.该方法具体步骤如下.

①获得巷道中心线双向图后，根据巷道宽度，将所有的中心线段沿垂线方向向两侧复制并平移获得巷道两侧边线段(以下简称初始边线).

②执行深度优先遍历依次访问所有结点和有向边.在遍历结点及有向边时依次采用4个判别条件并分别执行计算(表1).

表1 算法判别条件

③将PL内的所有边线多段线打散，并分配给初始对应的巷道中心线.完成巷道双边线及基本组件建模.

如图7所示，由巷道中心线偏移获得初始边线(图7a).以v1为起点，访问v2(图7b)，由于该结点是非过渡结点，因此将pla存储为pl1.然后经过v4、v5，由于v5是非过渡结点，因此连接两条边线获取新的pla(图7c)，且由于v5是叶结点，拼接pl1和pla获得新的pl1后，存储入集合PL(图7d).最终，通过该算法获得的边线多段线集合PL中包含3条边线多段线(图7e)，将其从结点处拆分后获得的每一段中心线对应的双侧边线(图7f).

图7 基于本文方法建模巷道双边线示意图

巷道边线连接算法中存在三种情况：直接修剪(Case 1)、延伸求交(Case 2)和舍弃边线(Case 3).Case 1和Case 2出现频率较高，且比较容易判断.Case 3判断算法为：首先对按遍历顺序排列的两段边线段延伸求交.然后判断线段延伸至交点方向与有向边的关系，若延伸方向与有向边方向相反，则舍弃巷道线，否则保留并修剪线段.

3 方法分析与应用

通过VC++编程实现该算法后，设计了两个实验验证本文算法的有效性和时间效率.实验运行在便携式笔记本上，硬件环境为Intel(R)Core(TM) i5-8250U CPU @ 1.60 GHz，内存8.0GB，软件环境为Windows 10 (x64)家庭版.

3.1 建模方法时间效率分析

钱家营煤矿位于唐山市，井田范围88 km2(图8a).以该矿5，7，8，9，12-1煤巷及岩巷井下导线测量数据作为数据源，测试本文算法的时间效率和建模效果.各巷道网络建立的中心线双向图的拓扑信息统计如图8b所示.

图8 钱家营煤矿位置与巷道数据

通过本文巷道双边线建模方法，使用5，7，8，9，12-1等煤巷及岩巷导线，为每个煤巷(岩巷)建立双边线模型所需时间见图9.其中建模时间取五次测试平均值.图中横坐标为主要中心线结点个数，纵坐标为算法运行时长.结果显示该方法总体建模效率较高，且随着中心线结点的增加，建模时间总体呈线性增长，表明算法随参与建模数据增长稳定性较好.

图9 巷道双边线建模时间

由于巷道中心线双向图采用邻接表存储图中点的邻域，即用一维数组存储图的n个顶点，且其中每个元素都指向该顶点的邻接点形成的单链表，单链表中的节点个数为与该顶点有关联的边，所以深度优先搜索遍历图的时间复杂度为O(n+e)，与实验结果相互印证.

3.2 巷道网络三维建模实例

为验证本文提出的复杂巷道组件式三维建模方法的有效性，使用BCAM方法对钱家营矿区岩巷和煤巷网络分别进行三维建模.图10为巷道网络典型复杂场景.首先以岩巷井下导线测量数据作为数据源，构建中心线网络(图10a)，然后使用提出的深度优先遍历巷道中心线网络双向图算法生成双边线(图10b)并将整个巷道划分为BCR并完成三维建模(图10c，10d).整个巷道网络的三维建模结果如图11所示.