矿井通风系统三维联通巷道建模算法及其应用
黄俊歆1, 2，王李管1，熊书敏1，田峰3，陈建宏1
(1. 中南大学 资源与安全工程学院，湖南 长沙，410083；
2. 湖南工学院 安全与环境工程系，湖南 衡阳，421001；
3. 中铁隧道勘测设计院有限公司 第五设计分院，天津 300133)
摘要：提出一种新的矿井通风系统三维联通巷道建模算法即多层闭合轮廓线联合法(Combining Multi-layer Closed contour Algorithm，CMCA)。对已有的通风系统单线图进行求交、打断等操作，建立节点—正向弧—反向弧网络拓扑结构图；采取逆时针搜索、最外层闭合轮廓线优先提取策略，提取网络拓扑结构图中的所有闭合轮廓线；并对所有闭合轮廓线进行右偏移操作，从而生成一组闭合轮廓线。根据用户输入的生成精度，在巷道顶底板间插入若干与巷道底板平行的面，将巷道在空间上分割成对应的若干层，即可在每一层生成一组闭合轮廓线。然后将这一系列闭合轮廓线三角化，再合并所有三角网格，最终形成三维联通巷道表面模型。CMCA已用于DIMINE数字矿山系统的通风模块中，并在实际矿井通风工程中得到应用。研究结果表明：采用闭合轮廓线法生成通风系统三维联通巷道，实现简单，结果正确，能准确反映矿井巷道的内部联通状况及真实三维空间形态，为矿井通风系统三维联通巷道模型的建立提供了一种新的有效方法。
关键词：矿井通风；三维巷道模型；联通巷道；闭合轮廓线；三角化
中图分类号：TD724 文献标志码：A 文章编号：1672-7207(2012)08-3173-07
Modeling algorithm of mine ventilation 3D-interconnected airway and its application
HUANG Jun-xin1, 2, WANG Li-guan1, XIONG Shu-min1, TIAN Feng3, CHEN Jian-hong1
(1. School of Resources and Safety Engineering, Central South University, Changsha 410083, China;
2. Department of Safety and Environment Engineering, Hunan Institute of Technology, Hengyang 421001, China;
3. Fifth Design Branch, China Railway Tunnel Survey Design and Institute Co. Ltd, Tianjin 300133, China)
Abstract: Combining Multi-layer Closed contour Algorithm (CMCA) was presented. This novel algorithm is used to establish 3D-interconnected laneway model for mine ventilation simulate system. According to generative precision input by user, the laneway was segmented into several layers in space by inserting several planes into the roof and floor of laneway. The planes should be parallel to laneway floor. The procedure of CMCA could be described as follows. Intersect and cut the existing single-line laneways of ventilation system, and establish the figure of the node-positive arc-opposite arc network topologic structure; adopt the strategy of searching counter-clockwise and extracting preferentially the outermost closed contour line, and extract all the closed contour lines in the figure of network topologic structure. By excursing the closed contour lines to the right side, generate a series of closed contour lines. Finally, by triangulating these contour lines of each layer and merging all the triangular meshes, generate the 3D-interconnected laneway surface model. CMCA was used in the mine ventilation module of DIMINE digital mine system and utilized in practical mine ventilation engineering. The utilization of this algorithm shows that the 3D-interconnected laneways in mine ventilation simulate system is generated by using CMCA, with simple implementation and correct result, which can reflect accurately the internal connection status and the actual 3D spatial form of the mine laneway. CMCA provides an effective way for establishing 3D-interconnected laneway model in mine ventilation simulate system.
Key words: mine ventilation; 3D laneway model; interconnected laneway; closed contour lines; triangulation
巷道是矿井通风系统图中的主体元素，其空间位置关系复杂、纵横交错，在二维图形系统中无论是单线图还是双线图都无法直观地表现这种复杂的空间交错关系。但目前国内外的矿井通风系统三维建模技术均尚未成熟。最具代表性的产品为澳大利亚VENTSIM公司开发的三维可视化矿井通风仿真系统Ventsim Visual，但该软件中三维巷道也仅是采用非联通建模技术[1]。为了能够区分出巷道之间空间层位关系，人们习惯用双线表示矿井通风系统的巷道。郝天轩等[2]介绍了利用ObjectARX在AutoCAD上进行二次开发，并对通风系统单线图逐一进行偏移、打断等操作，最终形成通风系统双线图的方法，能够较好的表现双线巷道及其空间层位关系，但必须依赖AutoCAD软件。李钢等[3]提出矿井通风系统可视化固定宽度巷道双线处理，只能处理等宽度巷道的设计，且当结点与多于3个巷道关联时，计算复杂，难以编程实现。文献[4]提出自动架桥法及假双线法实现了通风系统双线图的绘制，无需计算双线坐标来实现通风系统双线图自动绘制，但其消隐部分的渲染工作开销非常大。本文作者在研究矿井通风仿真系统三维可视化技术时，基于矿井通风系统拓扑关系自动建立和管理，在二维双线巷道自动生成算法的基础上进行扩展，提出了一种新的矿井通风系统三维联通巷道建模算法即多层闭合轮廓线联合法(Combining multi-layer closed contour lines algorithm，CMCA)，该算法具有普适性、计算量小，执行效率高等特点，能够真实地表现巷道的几何形态及其空间的复杂交错关系。该算法已应用于DIMINE数字矿山系统的三维矿井通风仿真模块中[5-14]。
1 CMCA的基本原理
1.1 生成二维双线巷道的基本原理
1.1.1 构建拓扑关系图
矿井通风仿真系统中可以采用多种图元表示通风系统单线图，如直线、多段线、圆、圆弧，椭圆、椭圆弧、NURBS曲线等[15]。为便于阐述，以多段线表示巷道为例进行说明，对拓扑关系图中各元素进行 定义。
定义1 节点。多段线的实交点和端点对应于拓扑关系图中的节点，以Ni表示节点；
定义2 有向弧。执行打断操作后的通风系统单线图中，每条多段线对应于拓扑关系图中的2条方向相反的有向弧，其中与多段线方向相同的有向弧称为正向弧，以Ai表示；与多段线方向相反的则称为反向弧，以Ai′表示；
定义3 入弧。拓扑关系图中任一实节点Ni，所有以节点Ni为末节点的有向弧称为节点Ni的入弧；
定义4 出弧。拓扑关系图中任一实节点Ni，所有以节点Ni为始节点的有向弧称为节点Ni的出弧；
以一简单角联通风系统图为例生成拓扑关系图如图1所示。提取通风系统单线图中所有多段线，对其进行求交操作，得到若干实交点，在这些交点处将所有多段线打断。为便于阐述，将其正向弧及反向弧分开画在图1(a)及图1(b)中，拓扑关系图由图1所示的节点、正向弧、反向弧组成，称为节点—正向弧—反向弧拓扑关系图。
图1 生成正向弧及反向弧
Fig.1 Generate forward arc and reverse arc
1.1.2 最外层闭合轮廓线
生成双线巷道的关键是提取通风网络拓扑结构图中的闭合轮廓线。为正确生成通风系统双线巷道图，必须严格遵守最外层闭合轮廓线优先的搜索原则。
定义5 最外层闭合轮廓线。闭合轮廓线路径经某节点Ni的1条入弧进入节点Ni，节点Ni有n条出弧，以该入弧为起点位置，绕节点Ni的沿逆时针方向进行搜索，搜索到的第1条未选出弧即为最外层闭合轮廓线的有向弧路径。闭合轮廓线的提取过程中每个节点处都作该处理，最终提取的闭合轮廓线即为最外层闭合轮廓线。
1.1.3 闭合轮廓线的提取
提取闭合轮廓线时可从任一节点开始，若当前节点的入弧为空，则可选择该节点的任一出弧为闭合轮廓线的当前有向弧。
严格遵守最外层闭合轮廓线优先的原则，提取图1所示拓扑结构图中的所有闭合轮廓线，提取过程 如下。
步骤1 取节点N3为起始节点，此时节点N3有3条出弧A3，A4及A5′，由于此时初始时节点N3的入弧为空，则可选择节点N3的任意1条出弧为闭合轮廓线的当前有向弧，这里选择A4，将A4加入闭合轮廓线链表中，同时将A4标记为已选。
步骤2 正向弧A4的末节点为N4，节点N4有3条未选出弧A6，A2′及A4′，以入弧A4为起点沿逆时针搜索，搜索到的第一条出弧为A6，遵循最外层闭合轮廓线优先的原则，选择A6作为闭合轮廓线的当前有向弧，将A6加入闭合轮廓线链表中，同时将A6标记为已选。
步骤3 正向弧A6的末节点为N5，节点N5有3条未选出弧A5，A7及A6′，以入弧A6为起点沿逆时针搜索，搜索到的第一条出弧为A5，遵循最外层闭合轮廓线优先的原则，选择A5作为闭合轮廓线的当前有向弧，将A6加入闭合轮廓线链表中，同时将A5标记为已选。此时闭合轮廓线经A5回到节点N3，完成一个闭合轮廓线的提取，闭合轮廓线如图2(a)所示。
步骤4 任取一节点，这里仍选择节点N3为下一闭合轮廓线的起始节点，此时N3只有2条出弧A3及A5′为未选。任取一出弧，这里选择A3作为闭合轮廓线的当前有向弧。同理，提取当前闭合轮廓线为A3—A2—A4′，闭合轮廓线如图2(b)所示。
步骤5 任取一节点作为下一闭合轮廓线的起始节点，此时任一节点均只有一条出弧为未选，所以惟一闭合轮廓线路径提取为A1—A3′—A5′—A7—A7′—A6′—A2′—A1′。所有闭合轮廓线提取完毕。
图1所示的通风网络共可提取3个闭合轮廓线，如图2所示。
1.1.4 闭合轮廓线的偏移
由于搜索算法采用逆时针搜索原则，故所有偏移操作采用右偏移方式，才能保证顺、逆向闭合轮廓线分别向巷道中心线两侧偏移形成双线巷道。上述3个闭合轮廓线分别向右偏移后所形成的双线图如图3 所示。
图2 提取闭合轮廓线
Fig.2 Pick up closed contour lines
图3 闭合轮廓线右偏移得到双线巷道图
Fig.3 Double-line laneway graphic after right-offset
1.2 生成三维联通巷道
生成三维联通巷道的基本思想是：根据用户输入的生成精度，从巷道底部到顶部，插入若干与巷道底板平行的面，这些面与巷道相交形成一系列闭合轮廓线。将这些闭合轮廓线三角化，并合并所有三角网格来生成三维联通巷道。
1.2.1 生成多层闭合轮廓线
以拱形巷道为例，其巷道断面如图4(a)所示。从该断面底部到顶部插入若干平面，与巷道断面相交形成一系列交点，这些交点在相应平面上到中心线间的距离为Ln(0≤n≤19)，即为该平面上闭合轮廓线的偏移距离，顶部闭合轮廓线退化成1条线。再根据上述生成二维双线巷道的方法，逐层生成闭合轮廓线，所有闭合轮廓线的结果如图4(b)所示。
1.2.2 巷道三维建模
采用上述生成二维双线巷道的算法，对每一层生成一组闭合轮廓线。得到多层闭合轮廓线后，巷道三维建模问题就转化成多边形的三角剖分问题。
多边形的三角剖分就是在不产生新顶点的条件下将平面多边形划分成一系列不相重叠的三角形[16]。多边形三角剖分的算法很多，如Gareym等[17]提出的Sweep Line algorithm算法；Seidel[18]提出的Incremental Randomized算法等。这些算法较难扩展到带洞多边形的情况。Incremental randomized算法性能较好，但未见实现方面的报道；Chazelle[19]证明了多边形的三角剖分可以在O(n)级时间内完成，但这种算法的实现非常困难[20]；李学军等[21]提出的快速算法只是在单调多边形三角化时的时间复杂度为O(n)，而在多边形单调化时复杂度比O(n)要高，同时对含有岛的多边形是否支持还有待于进一步验证；刘海涛等[22]提出的算法是将凹边形分解成凸多边形，再通过添加辅助点的方式对子多边形进行三角剖分，时间复杂度为O(jn+nlogn+jklogn)；毕林等[23]提出的快速多边形区域三角化算法，适合于带有洞、岛的任意简单多边形，速度近似为O(n)，且实现简单。本文选用毕林等[23]所提出的算法实现了各层轮廓线的三角化并将所有的三角化网格合并，最终生成封闭的三维巷道实体表面模型。
图4 生成拱形巷道多层闭合轮廓线
Fig.4 Closed contour lines of arch shape laneway
显然，在其他领域对于实体的联通建模问题通常采用多边形的三角剖分算法来实现，该算法目前已较为成熟。因此矿井通风系统三维联通巷道的建模难点就在于多层闭合轮廓线的提取与生成。
2 CMCA实现算法
2.1 建立节点—正向弧—反向弧拓扑关系图
为记录通风系统图的节点—有向弧—反向弧拓扑关系图。构建数据结构如下，以类C语言描述为：
Struct CNode
{
C3DPoint m_Pt; //交点的位置
CArcList m_Arcs; //以m_Pt为起点的有向弧链表
};
struct CArc
{
CCurve* m_pCurve; //对应的多段线
CArc* m_pRArc; //对应的反向弧
CNode* m_pSNode; //始节点
CNode* m_pENode; //末节点
Bool m_bClosed; //是否自闭合
double m_offset; //偏移距离(巷道宽度的1/2)
}；
该过程的主要为多段线相交或自相交求交点的操作，算法中以参数曲线[15]表示多段线。各交点对应于相应多段线上的一个参数坐标[15]，将各条多段线上的交点参数坐标从大到小排列，并按顺序打断成多条多段线。打断后的每条多段线对应于2条有向弧，以数据结构CArc记录；各有向弧的端点称为节点，以数据结构CNode记录。
2.2 提取闭合轮廓线
提取闭合轮廓线为本算法的关键步骤，严格遵守最外层闭合轮廓线优先的原则提取节点—有向弧—反向弧网络拓扑结构，设计算法如下：
第1步：在节点数组中任取一节点，以指针pNode指向该节点；
第2步：若pNode为空，闭合轮廓线提取完毕，程序结束；
第3步：若pNode的未选出弧数为0，指针pNode移至下一节点；
第4步：若当前闭合轮廓线链表为空，令闭合轮廓线链表头指针pHeader=pNode；
第5步：将节点pNode加入到当前闭合轮廓线链表尾部；
第6步：若pHeader==pNode，任取pNode的一条出弧，令有向弧指针pArc指向该弧，并标记为已选；
第7步：以节点pNode为中心点，pArc为起始位置，沿逆时针方向搜索pNode的出弧，搜索到其第一条出弧为当前弧，令pArc指向该弧，并标记pArc为已选；
第8步：令pNode=pArc->m_pENode；
第9步：若pHeader==pNode，当前闭合轮廓线提取完毕，存储当前闭合轮廓线，并清空当前闭合轮廓线链表跳转至第1步提取下一闭合轮廓线。否则跳转至第5步。
图5所示为提取一层闭合轮廓线的算法流程图，其他各层闭合轮廓线的生成只需对其高程及宽度进行适当的调整即可。
图5 提取闭合轮廓线的算法流程图
Fig.5 Algorithm flow chart of pick up closed contour lines
2.3 闭合轮廓线右偏移
由于提取闭合轮廓线时采取最外层闭合轮廓线优先，且搜索策略为逆时针搜索。因此，所有闭合轮廓线采用右偏移，从而形成矿井通风双线图。目前偏移算法已非常成熟[15]。
2.4 生成三维巷道模型
得到各层闭合轮廓线后，利用文献[23]中的快速多边形区域三角化算法，将各层轮廓线三角化并将所有的三角网格合并，最终生成封闭的三维巷道实体表面模型。具体的实现方法参见文献[23]。
3 实例应用
以图1所示的简单角联通风网络为例。将A1的断面设为圆形，A2，A3，A5，A6的断面设为圆弧拱，A4的断面设为梯形，A7的断面设为矩形。采用本文提出的算法对其建立联通巷道模型，如图6(a)所示，为观察其内部联通状况，从巷道中部进行剖切，剖面图如图6(a)所示。
图6 简单角联通风网络三维联通巷道模型
Fig.6 3D-interconnected laneway model of simple diagonal ventilation network
4 结论
(1) 矿井通风系统三维联通巷道的建模难点在于多层闭合轮廓线的提取与生成。
(2) 充分利用矿井通风系统单线图的节点—正向弧—反向弧网络拓扑结构图，采用最外层闭合轮廓线优先的逆时针搜索方法，通过在巷道顶底板间插入若干与巷道底板平行的面，从而得到多层闭合轮廓线。
(3) 提出了多层闭合轮廓线联合法(CMCA)，在提取上述多层闭合轮廓线的基础上生成三维联通巷道表面模型。
(4) 如何提高通风系统单线图中各多段线求交的运算及后期三角剖分运算的效率，进一步减少数据前期处理的运算量，是今后算法优化的主要方向。
参考文献：
[1] Ventsim L T D. Ventsim Visual? User Guide[EB/OL]. [2009-12-01]. http://www.ventsim.com/Manual.htm.
[2] 郝天轩, 李辉, 魏建平, 等. 矿井通风系统平面图自动绘制系统的研制[J]. 中国煤炭, 2005, 31(3): 28-30.
HAO Tian-xuan, LI Hui, WEI Jian-ping, et al. Research on mine ventilation plan automatic drawing system [J]. China Coal, 2005, 31(3): 28-30.
[3] 李钢, 陈开岩, 聂百胜. 矿井通风系统CAD技术研究[J]. 辽宁工程技术大学学报, 2005, 24(6): 636-638.
LI Gang, CHEN Kai-yan, NIE Bai-sheng. Research on CAD technology in mine ventilation system[J]. Journal of Liaoning Technical University, 2005, 24(6): 636-638.
[4] 李钢, 陈开岩, 何学秋, 等. 矿井通风系统巷道自动绘制方法研究[J]. 煤炭科学技术, 2006, 34(6): 797-800.
LI Gang, CHEN Kai-yan, HE Xue-qiu, et al. Research on laneway auto mapping method for mine ventilation system[J]. Coal Science and Technology, 2006, 34(6): 797-800.
[5] 倪景峰. 矿井通风仿真系统可视化研究[D]. 阜新: 辽宁工程技术大学安全科学与工程学院, 2004: 5-25.
NI Jing-feng. The study on visualization of mine ventilation simulation[D]. Fuxin: Liaoning Technical University. School of Safety Science and Engineering, 2004: 5-25.
[6] 牛永胜, 曹荣, 陈学习, 等. 矿井通风三维可视化仿真系统的设计与实现[J]. 金属矿山, 2007, 373(7): 73-76.
NIU Yong-sheng, CAO Rong, CHEN Xue-xi, et al. Design and implementation of 3D visualized simulation system of mine ventilation[J]. Metal Mine, 2007, 373(7): 73-76.
[7] 黄光球, 陆秋琴, 郑彦全. 存在固定风量分支的通风网络解算新方法[J]. 金属矿山, 2004(10): 52-54.
HUANG Guang-qiu, LU Qiu-qin, ZHENG Yan-quan. A new optimization algorithm for ventilation network with fixed volume branches[J]. Metal Mine, 2004(10): 52-54.
[8] 魏连江, 王德明, 王琪, 等. 构建矿井通风可视化仿真系统的关键问题研究[J]. 煤矿安全, 2007, 392(7): 6-9.
WEI Lian-jiang, WANG De-ming, WANG Qi, et al. Study on some key issues of constructing visual mine ventilation simulation system[J]. Safety in Coal Mines, 2007, 392(7): 6-9.
[9] 魏连江, 朱华新, 张雷林. 矿井通风仿真系统双线图的快速自动绘制研究[J]. 中国安全科学学报, 2008, 18(11) : 55-59.
WEI Lian-jiang, ZHU Hua-xin, ZHANG Lei-lin. Study on the rapid automatic drawing of double-line diagram of mine ventilation simulation system[J]. China Safety Science Journal, 2008, 18(11): 55-59.
[10] 王德明, 李永生. 矿井火灾救灾决策支持系统的研究[M]. 北京: 煤炭工业出版社, 1996: 14-44.
WANG De-ming, LI Yong-sheng. Study of mine fire rescue decision support system[M]. Beijing: Coal Industry Press, 1996: 14-44.
[11] 苏清政, 刘剑. 矿井通风仿真系统理论与实践[M]. 北京: 煤炭工业出版社, 2006: 24-40.
SU Qing-zheng, LIU Jian. The theory and practice of mine ventilation simulation system[M]. Beijing: Coal Industry Press, 2006: 24-40.
[12] 倪景峰, 刘剑. 矿井通风系统可视化固定宽度巷道双线处理[J]. 辽宁工程技术大学学报, 2005, 24(5) : 28-30.
NI Jing-feng, LIU Jian. Fixed distance double line automatic treatment of tunnel coordinates in mine ventilation visualization[J]. Journal of Liaoning Technical University, 2005, 24(5): 28-30.
[13] 魏连江, 王德明. 基于构件的矿井通风安全管理系统的开发研究[J]. 中国矿业, 2006, 15(12) : 25-27.
WEI Lian-jiang, WANG De-ming. Study on the mine ventilation and safety management system developments base on component[J]. China Mining Magazine, 2006, 15(12): 25-27.
[14] 魏连江, 郝宪杰, 张宏捷, 等. 矿井通风仿真系统区分井巷层位关系的新方法研究[J]. 金属矿山, 2008, 384(6): 105-107.
WEI Lian-jiang, HAO Xian-jie, ZHANG Hong-jie, et al. Study on new methods for identifying tunnel layer relationship in mine ventilation simulation system[J]. Metal Mine, 2008, 384(6): 105-107.
[15] Philip J S, David H E. 计算机图形学几何算法工具详解[M]. 北京: 电子工业出版社, 2005: 6-20.
Philip J S, David H E. Geometric tools for computer graphics[M]. Beijing: Publishing House of Electronics Industry, 2005: 6-20.
[16] 马小虎, 潘志庚, 石教英. 基于凹凸顶点判定的简单多边形Delaunay三角剖分[J]. 计算机辅助设计与图形学学报, 1999, 11(1): 1-3.
MA Xiao-hu, PAN Zhi-geng, SHI Jiao-ying. Delaunay triangulation of simple polygon based on determination of convex concave vertices[J]. Journal of Computer Aided Design & Computer Graphics, 1999, 11(1): 1-3.
[17] Gareym R, Johnson D S, Preparata F P, et al. Triangulating a simple polygon[J]. Information Proceeding Letters, 1978, 7(4): 175-179.
[18] Seidel R. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons[J]. Comput Geom Theory Appl, 1991, 1(1): 51-64.
[19] Chazelle B. Triangulating a simple polygon in linear time[J]. Discrete Comp Geom, 1991, 6(5): 485-524.
[20] WU Liang. Fast and robust simple polygon triangulation with/without holes by sweep line algorithm[EB/OL]. [2007-03-18].http://www.mema.ucl.ac.be/~wu/Poly2Tri/poly2tri.Html
[21] 李学军, 黄文清. 平面区域三角化的快速算法[J]. 计算机辅助设计与图形学学报, 2003, 15(2): 233-238.
LI Xue-jun, Huang Wen-qing. Fast triangulation algorithm for planar regions[J]. Journal of Computer Aided Design & Computer Graphics, 2003, 15(2): 233-238.
[22] 刘海涛, 张三元, 叶修梓. 一种快速相容三角剖分算法[J]. 计算机应用研究, 2007, 24(1): 235-237.
LIU Hai-tao,ZHANG San-yuan,YE Xiu-zi. Fast compatible triangulations algorithm[J]. Application Research of Computers, 2007, 24(1): 235-237.
[23] 毕林, 王李管, 陈建宏, 等. 快速多边形区域三角化算法与实现[J]. 计算机应用研究, 2008, 25(10): 3030-3033.
BI Lin, WANG Li-guan, CHEN Jian-hong, et al. Fast triangulation algorithm for polygon regions and implementation[J]. Application Research of Computers, 2008, 25(10): 3030-3033.
(编辑 赵俊)
收稿日期：2011-09-11；修回日期：2011-11-20
基金项目：国家自然科学基金资助项目(50774092); 湖南省科技厅重点项目(2008SK3077); 湖南省教育厅科研项目(10C0573)
通信作者：黄俊歆(1982-)，男，湖南衡阳人，博士研究生，从事安全预警、采矿仿真及矿井通风可视化技术研究；电话：0734-6666858；E-mail：amwwcwujqw@126.com
