, 张文芬中南大学 资源与安全工程学院，湖南 长沙 410083
收稿日期: 2015-11-03
基金项目: “十二五”国家科技支撑计划项目(2012BAK09B02-05)；国家自然科学基金资助项目(51274250)。
作者简介: 黄俊杰(1984-)，男，江西九江人，中南大学博士研究生;
罗周全(1966-)，男，湖南邵阳人，中南大学教授，博士生导师。
摘要: 以采空区三维激光扫描系统探测获取的原始数据为依据，针对复杂采空区散乱点云数据，研究提出运用一组等间距的垂直于包围盒走向方向的平行切割面，对散乱点云进行区域划分进而构建空区实体模型的方法.首先确定等间距平行切割面的方向和间距，对散乱点云数据进行划分；其次运用最小距离法确定散乱点云的位置即所归属的切割面；最后运用凸包最小距离法对每个切割面上的散乱点进行排序，成为有序点后对其进行建模.应用表明，研究所形成的建模方法可实现对复杂采空区散乱点云的精确建模.
关键词：复杂采空区散乱点剖面线三角剖分凸包算法
Research and Application of Three-Dimensional Scattered Points Modeling Technology in Complex Cavity
HUANG Jun-jie, LUO Zhou-quan, QIN Ya-guang
, ZHANG Wen-fenSchool of Resources and Safety Engineering, Central South University, Changsha 410083, China
Corresponding author: QIN Ya-guang, E-mail: csuqyg@163.com
Abstract: Aiming at scattered data, a set of equally spaced cutting face in vertical direction of maximum bounding box was used to segment scattered point cloud, and the method of cavity three-dimensional model was proposed by taking cavity three-dimensional laser scanning system to obtain original data as the basis. The direction and pitch of parallel cutting surface was determined firstly to divide and cut scattered point cloud. Then the location of scattered point cloud which is in cutting surface was determined by the minimum distance method. Finally, scattered points were sorted through convex hull the minimum distance method, and it was modeled after becoming ordered points. Applications show scattered points modeling algorithm of complex cavity is accurate, which can be realized in complicated scattered point cloud modeling.
Key Words: complex cavityscattered pointshatchtriangulationconvex hull algorithm
地下矿山开采形成的采空区是威胁矿山安全生产的重要灾源之一.其空间形态的准确获取为矿山采空区充填及灾害预测提供了基础性依据，同时也是矿山实施空区周边资源及残矿安全回采的重要依据[1].
对于形态规整的采空区，利用三维激光扫描仪单次探测获得的有序点云数据就能够实现其三维形态的构建.但对于形态复杂的空区，通过单次探测往往会出现局部遮挡而不能准确获取其三维空间形态.此时，需要通过两次探测才能完整获取其三维形态的点云数据.对于两次探测获取的空区点云数据，复合之后就会形成一群杂乱无章的三维空间点云，称之为空区散乱点云.目前，国内外主流矿山三维建模软件都不能较好解决此类空间散乱点的实体建模问题.本文提出一种利用平行切割面对散乱点云进行分区吸附，然后根据凸包最小距离法实现平行切割面上无序点云的有序化，最后通过最小周长法对相邻平行切割面上的有序化点云进行剖分建模的方法，实现了复杂采空区三维空间形态的准确构建.
1 算法原理及关键问题复杂采空区散乱点云建模的原理如下：
1)通过判断两次空区探测点云数据的包围盒，沿较大包围盒走向方向用一组等间距平行面对散乱点云进行分割，对散乱点云进行区域化划分；
2)将划分到该区域上的点云存入到相应的点集中；
3)将位于两个平行切割面之间的散乱点云通过距离判断存入到相应切割面的点集中；
4)将每个切割面上的点云数据进行排序，使无序点有序化；
5)利用最小周长法，对有序点进行建模.
散乱点云建模的基本流程如图 1所示，需要解决的关键问题如下：
1)确定平行切割面的方向和平行切割面之间的最佳间距；
2)将两个相邻的平行切割面之间的散乱点存入到正确的切割面中；
3)将每个切割面上的无序点排序成为有序点.
图 1(Fig. 1)
 | 图 1 算法基本流程图Fig.1 The basic flow chart of algorithm |
2 散乱点云建模方法2.1 平行切割面点云获取对散乱点云进行建模时，首先判断两次探测点云数据的包围盒大小，确定垂直于包围盒较大的点云数据走向方向为剖切面方向，然后对点云进行平行切割，取得的截线称之为边界截取线.如果边界截取线足够密集，即各边界截取线之间的间距越小，提供的点云模型空间实际形态的信息就越精确、全面.经过平行切割后，三维散乱点云建模的问题就转化为处理数据共面的问题，大大降低了散乱点云建模的复杂程度，也为接下来的建模工作创造了更为方便的条件.
为此，本文对平行切割面做了如下定义：
span=(Ymax-Ymin)/(num-1)，其中span为平行切割面之间的间距，num为平行切割面的数量，Ymax，Ymin分别为采空区点云数据走向方向上最大、最小值.具体实现时，num的取值可根据用户实际需要的三维模型精度来确定，即通过调整平行切割面之间的间距，构建不同精度的采空区三维模型，间距越小，精度越高，但同时数据运算量也随之增大.
以沿X轴对散乱点云进行平行剖切为例说明.确定各平行剖切面上点的步骤如下：
1)找出所有散乱点中X坐标的最大值Xmax和最小值Xmin，并根据实际需要的三维模型的精度要求确定平行剖切面的间距span的取值；
2)对每一个平行剖切面进行编号，分别为num={X1, X2, …, Xi, …, Xn}；
3)将所有的散乱点云数据和Xi相比较确定每个点云数据的位置，有以下几种情况：
①点正好位于平行剖切面上时，直接将点保存到相应的剖切面的点集中；
②点位于两平行剖切面之间时，通过判断点到平面的距离来确定平行切割面之间每个点的归属，如果点到平面的距离小于span/2，则该点属于该平面，否则属于相邻的平面.将该点存入到相应剖切面的点集中.图 2所示为某一平行剖切面与该剖切面间散乱点云数据的对应关系.
图 2(Fig. 2)
 | 图 2 边界截面线与点云的关系Fig.2 Relation of border section line and the point cloud |
由图 2可知，在切割面Xi-1, Xi, Xi+1三个切割面之间存在若干个点云数据，以Xi-1, Xi平面之间的10个点为例，点A1, A2正好位于切割面Xi-1上，点A8, A9, A10正好位于切割面Xi上.而对于Xi-1与Xi之间的其他点，按照距离最近原则，距离哪个切割面较近就存储到哪个切割面中.由图可知，点A3, A4, A5, A6应该添加到切割面Xi-1中，而点A7应该添加到切割面Xi中.依此类推，将所有的点保存到相应的切割面数据容器中.
2.2 切割面上无序点排序对于平行切割面上散乱点的排序方法有紧邻排序法[2]、扇形区域法[3].这两种排序方法对于表面变化比较平缓的模型较适用，但是应用于边界复杂的采空区时，得到的剖面轮廓线会失真.基于传统排序方法的缺陷，根据凸包算法[4-7]的思想提出了凸包最小距离法：首先运用传统的凸包算法生成包含所有点的最外层包络线，然后运用最小距离原理找出包络线内其他交点所在的位置，生成完整的剖面线.具体步骤如下：
1)找出点集Xi={a1, a2, ···, ai, ···, an}中n个数据中横坐标最小的点记为b1，把该点记为轮廓线的起始点；
2)对于其余的n-1个点，计算与b1连线与水平方向夹角的余弦值，取出余弦值最小的点，作为生成初始边缘轮廓线的第二个点，记为b2；
3)对于点集A中其余的n-2个点，可构成三角形b1b2ai，找出∠b1b2ai最大的点ai作为生成初始边缘轮廓线的第三个点b3；
4) b2代替b1，b3代替b2，在其余n-3个点中，重复3)，寻找下一个生成初始边缘轮廓线的点；
5)当b3与b1重合时，停止，即生成边缘轮廓线.图 3中红线为将所有的交点包络在内的初始边缘轮廓线.
图 3(Fig. 3)
 | 图 3 剖面的初始边缘轮廓线Fig.3 Contour line of the outer boundary |
在生成的最外层包络线的基础上，还需要对包络线内的点进行合理连接，才能生成完整的剖面轮廓线.但是在将包络线内的点进行连接的过程中存在两个不确定性：一是包络线内点的分布具有不确定性；二是包络线内点相对于包络线的位置也具有不确定性.因此，针对以上两个不确定性，运用最小距离的原则，将包络线内的点进行排序.其原理如下，见图 4.
图 4(Fig. 4)
 | 图 4 最大张角准则的原理Fig.4 Principle of the maximum angle |
1)找出与包络线bi, bi+1距离最近的点，并且保证该点与bi, bi+1形成的夹角大于90°，在图 5中为ai+1点；
2)将bi, ai+1两点的连线作为外层包络线，找出距离bi, ai+1线段距离最近的点，并且也要保证夹角大于90°；
3)循环1)，2)直至形成包含所有的点在内的最小包络线中.
依次判断，直至所有满足要求的点都添加至轮廓线中，将连线作为最终剖面图输出.图 5为将所有符合要求的点添加到图 4初始边缘轮廓线后生成的完整剖面轮廓线.
图 5(Fig. 5)
 | 图 5 完整剖面线Fig.5 The complete profile |
2.3 有序点的建模--最小周长法俄国数学家Delaunay在1934年提出了Delaunay三角剖分算法[8-10].但是该算法运用于复杂采空区的点云建模时，由于采空区的形态复杂，建模时容易出现狭长的三角形，使得三维模型失真.本文提出了最小周长法的有序点建模方法，该方法的基本步骤如下：
1)选取相邻的两个平行的剖切面，第n圈和第n+1圈；
2)假设第n圈的i点和第n+1圈的j点连接，寻找对比第n圈i+1点和第n+l圈j+1点，对比形成的两三角形周长的大小；
3)按照周长最小的原则，通过比较两个三角形的周长找出周长较小的三角形进行连接，最小周长法的有序点三角剖分示意图见图 6；
4)将生成的三角形进行保存，重复1)~3)步骤直至将所有的点判断完毕；
5)运用OpenGL和C++相结合将三角网格模型显示出来.
图 6(Fig. 6)
 | 图 6 最小周长法的有序点三角剖分Fig.6 Ordered triangulation of the minimum perimeter method (a)-最小周长法三角剖分算法说明；(b)-圈间三角剖分连接. |
3 散乱点建模方法应用采用自主研发的集成了上述散乱点建模方法的采空区激光探测三维建模可视化集成系统(CVIS)，针对国内某地下大型金属矿山多年来开采形成的复杂采空区，以Shn6#采场为例，空区三维激光探测系统(cavity monitoring system，CMS)扫描仪原始探测数据通过后处理软件CMSPosProcess处理后的XYZ格式复杂点云数据如图 7所示，按照无序点建模原理生成的剖面轮廓线及三维实体模型如图 8所示.
图 7(Fig. 7)
 | 图 7 两次探测复合的散乱点云数据Fig.7 Scattered point cloud data combined by twice laser scanning (a)-第一次探测点云；(b)-第二次探测点云；(c)-两次探测复合点云. |
图 8(Fig. 8)
 | 图 8 散乱点建模方法生成的剖面及三维实体模型Fig.8 Section and three-dimensional model generated by scattered point modeling (a)-剖面；(b)-模型. |
已知该采场空区的体积值为101 557 m3，将其作为参考值.剖面间距取不同值时求得的体积与参考值的偏差，如图 9所示.
图 9(Fig. 9)
 | 图 9 算法取不同剖面间距计算的体积偏差Fig.9 D-value of different spacing between section planes and the reference value |
由图 9可知，取不同剖面间距计算的体积偏差仅为0.2%~0.5%之间，当剖切面的间距为40 cm时，求得的该空区体积误差最小.为了进一步验证算法的有效性，运用CMS激光探测仪探测的采空区的点云数据利用无序点建模方法计算求得的体积与参考值相对误差的对比见图 10.通过无序点云建模求取的采空区体积与参考值之间的相对误差仅为0.2%~0.6%，能够满足工程精度要求.
图 10(Fig. 10)
 | 图 10 无序点建模方法求得采空区体积与参考值的偏差Fig.10 D-value between the volume obtained by disorderly point modeling and the reference value |
4 结论1)提出了复杂采空区散乱点云建模方法：以散乱点云为基础，根据包围盒大小确定平行切割面方向，将散乱点云划分为若干个区域，然后按照凸包最小距离法，形成包含所有点在内的最小包络线，实现无序点云的有序化.
2)以有序化点云为基础，提出了最小周长法的有序点建模方法，按照最小周长法精确建立了采空区三角网格模型.实际应用表明：该算法误差较小，具有良好的稳定性和精度.
3)复杂采空区散乱点云精确建模的实现，为采空区边界获取、充填、灾变监控、空区周边资源以及残矿安全回采提供了重要依据.
参考文献
| [1] | 李夕兵, 李地元, 赵国彦, 等. 金属矿地下采空区探测、处理与安全评判[J].采矿与安全工程学报, 2006, 23(1) : 24–29. ( Li Xi-bing, Li Di-yuan, Zhao Guo-yan, et al. Detecting, disposal and safety evaluation of the underground goaf in metal mines[J].Journal of Mining and Safety Engineering, 2006, 23(1) : 24–29.) |
| [2] | 张献颖, 周明全, 耿国华, 等. 空间三角网格曲面的边界提取方法[J].中国图象图形学报A辑, 2003, 8(10) : 1223–1226. ( Zhang Xian-ying, Zhou Ming-quan, Geng Guo-hua, et al. A method of detecting the edge of triangular mesh surface[J].Journal of Image and Graphies, 2003, 8(10) : 1223–1226.) |
| [3] | 乔鹏程, 吴正国, 李辉, 等. 基于改进雷达图法的电能质量综合评估方法[J].电力自动化设备, 2011, 31(6) : 88–92. ( Qiao Peng-cheng, Wu Zheng-guo, Li Hui, et al. Power quality synthetic evaluation based on improved radar chart[J].Electric Power Automation Equipment, 2011, 31(6) : 88–92.) |
| [4] | Rezaei H. On the convex hull generated by orbit of operators[J].Linear Algebra and Its Applications, 2013, 438(11) : 4190–4203.DOI:10.1016/j.laa.2013.02.002 |
| [5] | Xiao Y J, Werghi N, Siebert P.A topological approach for segmenting human body shape[C]// 12th International Conference on Image Analysis and Processing.Mantova, 2003:82. |
| [6] | Liu G H, Chen C B. A new algorithm for computing the convex hull of a planar point set[J].Journal of Zhejiang University Science A, 2007, 8(8) : 1210–1217.DOI:10.1631/jzus.2007.A1210 |
| [7] | Zhang X Q, Tang Z J, Yu J H, et al. Convex hull properties and algorithms[J].Applied Mathematics and Computation, 2010, 216(11) : 3209–3218.DOI:10.1016/j.amc.2010.04.044 |
| [8] | Chen J J, Zheng Y. Redesign of a conformal boundary recovery algorithm for 3D Delaunay triangulation[J].Journal of Zhejiang University Science A, 2006, 7(12) : 2031–2042.DOI:10.1631/jzus.2006.A2031 |
| [9] | Chazelle B, Devillers O, Hurtado F, et al. Splitting a Delaunay triangulation in linear time[J].Algorithmica, 2002, 34(1) : 39–46.DOI:10.1007/s00453-002-0939-8 |
| [10] | Miller G L, Sheehy D R. A new approach to output-sensitive construction of Voronoi diagrams and Delaunay triangulations[J].Discrete & Computational Geometry, 2014, 52(3) : 476–491. |
