地下矿山开采形成的采空区是威胁矿山安全生产的重要灾源之一.其空间形态的准确获取为矿山采空区充填及灾害预测提供了基础性依据，同时也是矿山实施空区周边资源及残矿安全回采的重要依据^[1].

对于形态规整的采空区，利用三维激光扫描仪单次探测获得的有序点云数据就能够实现其三维形态的构建.但对于形态复杂的空区，通过单次探测往往会出现局部遮挡而不能准确获取其三维空间形态.此时，需要通过两次探测才能完整获取其三维形态的点云数据.对于两次探测获取的空区点云数据，复合之后就会形成一群杂乱无章的三维空间点云，称之为空区散乱点云.目前，国内外主流矿山三维建模软件都不能较好解决此类空间散乱点的实体建模问题.本文提出一种利用平行切割面对散乱点云进行分区吸附，然后根据凸包最小距离法实现平行切割面上无序点云的有序化，最后通过最小周长法对相邻平行切割面上的有序化点云进行剖分建模的方法，实现了复杂采空区三维空间形态的准确构建.

1 算法原理及关键问题

复杂采空区散乱点云建模的原理如下：

1)通过判断两次空区探测点云数据的包围盒，沿较大包围盒走向方向用一组等间距平行面对散乱点云进行分割，对散乱点云进行区域化划分；

2)将划分到该区域上的点云存入到相应的点集中；

3)将位于两个平行切割面之间的散乱点云通过距离判断存入到相应切割面的点集中；

4)将每个切割面上的点云数据进行排序，使无序点有序化；

5)利用最小周长法，对有序点进行建模.

散乱点云建模的基本流程如图 1所示，需要解决的关键问题如下：

1)确定平行切割面的方向和平行切割面之间的最佳间距；

2)将两个相邻的平行切割面之间的散乱点存入到正确的切割面中；

3)将每个切割面上的无序点排序成为有序点.

2 散乱点云建模方法 2.1 平行切割面点云获取

对散乱点云进行建模时，首先判断两次探测点云数据的包围盒大小，确定垂直于包围盒较大的点云数据走向方向为剖切面方向，然后对点云进行平行切割，取得的截线称之为边界截取线.如果边界截取线足够密集，即各边界截取线之间的间距越小，提供的点云模型空间实际形态的信息就越精确、全面.经过平行切割后，三维散乱点云建模的问题就转化为处理数据共面的问题，大大降低了散乱点云建模的复杂程度，也为接下来的建模工作创造了更为方便的条件.

为此，本文对平行切割面做了如下定义：

span=(Y_max-Y_min)/(num-1)，其中span为平行切割面之间的间距，num为平行切割面的数量，Y_max，Y_min分别为采空区点云数据走向方向上最大、最小值.具体实现时，num的取值可根据用户实际需要的三维模型精度来确定，即通过调整平行切割面之间的间距，构建不同精度的采空区三维模型，间距越小，精度越高，但同时数据运算量也随之增大.

以沿X轴对散乱点云进行平行剖切为例说明.确定各平行剖切面上点的步骤如下：

1)找出所有散乱点中X坐标的最大值X_max和最小值X_min，并根据实际需要的三维模型的精度要求确定平行剖切面的间距span的取值；

2)对每一个平行剖切面进行编号，分别为num={X₁, X₂, …, X_i, …, X_n}；

3)将所有的散乱点云数据和X_i相比较确定每个点云数据的位置，有以下几种情况：

①点正好位于平行剖切面上时，直接将点保存到相应的剖切面的点集中；

②点位于两平行剖切面之间时，通过判断点到平面的距离来确定平行切割面之间每个点的归属，如果点到平面的距离小于span/2，则该点属于该平面，否则属于相邻的平面.将该点存入到相应剖切面的点集中.图 2所示为某一平行剖切面与该剖切面间散乱点云数据的对应关系.

由图 2可知，在切割面X_i-1, X_i, X_i+1三个切割面之间存在若干个点云数据，以X_i-1, X_i平面之间的10个点为例，点A₁, A₂正好位于切割面X_i-1上，点A₈, A₉, A₁₀正好位于切割面X_i上.而对于X_i-1与X_i之间的其他点，按照距离最近原则，距离哪个切割面较近就存储到哪个切割面中.由图可知，点A₃, A₄, A₅, A₆应该添加到切割面X_i-1中，而点A₇应该添加到切割面X_i中.依此类推，将所有的点保存到相应的切割面数据容器中.

2.2 切割面上无序点排序

对于平行切割面上散乱点的排序方法有紧邻排序法^[2]、扇形区域法^[3].这两种排序方法对于表面变化比较平缓的模型较适用，但是应用于边界复杂的采空区时，得到的剖面轮廓线会失真.基于传统排序方法的缺陷，根据凸包算法^[4-7]的思想提出了凸包最小距离法：首先运用传统的凸包算法生成包含所有点的最外层包络线，然后运用最小距离原理找出包络线内其他交点所在的位置，生成完整的剖面线.具体步骤如下：

1)找出点集X_i={a₁, a₂, ···, a_i, ···, a_n}中n个数据中横坐标最小的点记为b₁，把该点记为轮廓线的起始点；

2)对于其余的n-1个点，计算与b₁连线与水平方向夹角的余弦值，取出余弦值最小的点，作为生成初始边缘轮廓线的第二个点，记为b₂；

3)对于点集A中其余的n-2个点，可构成三角形b₁b₂a_i，找出∠b₁b₂a_i最大的点a_i作为生成初始边缘轮廓线的第三个点b₃；

4) b₂代替b₁，b₃代替b₂，在其余n-3个点中，重复3)，寻找下一个生成初始边缘轮廓线的点；

5)当b₃与b₁重合时，停止，即生成边缘轮廓线.图 3中红线为将所有的交点包络在内的初始边缘轮廓线.

在生成的最外层包络线的基础上，还需要对包络线内的点进行合理连接，才能生成完整的剖面轮廓线.但是在将包络线内的点进行连接的过程中存在两个不确定性：一是包络线内点的分布具有不确定性；二是包络线内点相对于包络线的位置也具有不确定性.因此，针对以上两个不确定性，运用最小距离的原则，将包络线内的点进行排序.其原理如下，见图 4.

1)找出与包络线b_i, b_i+1距离最近的点，并且保证该点与b_i, b_i+1形成的夹角大于90°，在图 5中为a_i+1点；

2)将b_i, a_i+1两点的连线作为外层包络线，找出距离b_i, a_i+1线段距离最近的点，并且也要保证夹角大于90°；

3)循环1)，2)直至形成包含所有的点在内的最小包络线中.

依次判断，直至所有满足要求的点都添加至轮廓线中，将连线作为最终剖面图输出.图 5为将所有符合要求的点添加到图 4初始边缘轮廓线后生成的完整剖面轮廓线.

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++相结合将三角网格模型显示出来.

3 散乱点建模方法应用

采用自主研发的集成了上述散乱点建模方法的采空区激光探测三维建模可视化集成系统(CVIS)，针对国内某地下大型金属矿山多年来开采形成的复杂采空区，以Shn6#采场为例，空区三维激光探测系统(cavity monitoring system，CMS)扫描仪原始探测数据通过后处理软件CMSPosProcess处理后的XYZ格式复杂点云数据如图 7所示，按照无序点建模原理生成的剖面轮廓线及三维实体模型如图 8所示.

已知该采场空区的体积值为101 557 m³，将其作为参考值.剖面间距取不同值时求得的体积与参考值的偏差，如图 9所示.

由图 9可知，取不同剖面间距计算的体积偏差仅为0.2%~0.5%之间，当剖切面的间距为40 cm时，求得的该空区体积误差最小.为了进一步验证算法的有效性，运用CMS激光探测仪探测的采空区的点云数据利用无序点建模方法计算求得的体积与参考值相对误差的对比见图 10.通过无序点云建模求取的采空区体积与参考值之间的相对误差仅为0.2%~0.6%，能够满足工程精度要求.

4 结论

1)提出了复杂采空区散乱点云建模方法：以散乱点云为基础，根据包围盒大小确定平行切割面方向，将散乱点云划分为若干个区域，然后按照凸包最小距离法，形成包含所有点在内的最小包络线，实现无序点云的有序化.

2)以有序化点云为基础，提出了最小周长法的有序点建模方法，按照最小周长法精确建立了采空区三角网格模型.实际应用表明：该算法误差较小，具有良好的稳定性和精度.

3)复杂采空区散乱点云精确建模的实现，为采空区边界获取、充填、灾变监控、空区周边资源以及残矿安全回采提供了重要依据.