复杂采空区激光扫描拼合散乱点云球面投影三角剖分算法

工程科学学报，第37卷，第7期：823830,2015年7月 Chinese Journal of Engineering,Vol.37,No.7:823-830,July 2015 DOI:10.13374/j.issn2095-9389.2015.07.001:http://journals.ustb.edu.cn 复杂采空区激光扫描拼合散乱点云球面投影三角剖 分算法 罗周全，罗贞焱巴，张文芬，周吉明，黄俊杰 中南大学资源与安全工程学院，长沙410083 ☒通信作者，E-mail:luozhenyan@gg.com 摘要利用三维激光扫描技术对采空区进行探测以建立三维可视化模型，从而准确获取其三维空间位置和形态，是矿山采 空区事故隐患综合治理工作中的重要环节.但由于采空区形态复杂，往往需要从多个方位对其进行多次探测才能准确获取 采空区完整的三维形态.如何对多次探测点云数据拼合后的散乱点云构建三角网格模型，是实现复杂采空区三维探测建模 的关键.本文提出了采空区激光扫描拼合散乱点云数据球面投影三角剖分生长算法，首先选定球心将原位点云投影到球面 上得到投影点云，然后对投影点云进行三角剖分，最后将投影点云三角网空间拓扑关系还原到原位点云，从而构建复杂采空 区三角网模型.为了有效实现算法，研究了球面投影参数设定、XYZ三向单元栅格点云搜索策略、三角形生成规则、优势项点 边界切分策略、边界闭合策略、不规则三角形优化策略等多种方法.实际应用表明，所研究的算法能够生成优质的采空区三 角网模型，为实现复杂采空区三维精确建模及可视化管理提供了重要技术支持. 关键词采空区：激光扫描：球面投影；三角剖分：算法 分类号TD325·.4 Spherical projection triangulation algorithm for laser-scanning splice unorganized points of complex goafs LUO Zhou-quan,LUO Zhen-yan,ZHANG Wen-fen,ZHOU Ji-ming,HUANG Jun-jie School of Resources and Safety Engineering,Central South University,Changsha 410083,China Corresponding author,E-mail:luozhenyan@qq.com ABSTRACT Detection of a goaf by laser-scan technology to build a 3D visualized model and to obtain the goafs 3D space position and shape,is an important part for comprehensive management of the goaf's accidents.Multiple probes from multiple orientations are usually needed to obtain a goaf's 3D shape because of its complexity.How to construct a triangular mesh model from splice unorganized points by multiple probes is the key technology of a goaf's 3D modeling.A spherical projection triangulation algorithm is proposed for laser-scanning splice unorganized points of a goaf in this paper.Firstly,projected points are got by a chosen sphere center and project- ing in-situ points onto the sphere.Secondly,the projected points are triangularized completely.Then topological relations are reverted from the projected points to the in-situ points.At last,a triangular mesh model of the goaf is constructed.In order to effectively imple- ment the algorithm,many methods are studied such as the spherical projection parameters setting,XYZ-orientation cell grid points searching strategy,triangle generation rules,boundary segment strategy by advantage vertexes,boundary closure strategy,and irregu- lar triangle optimization strategy.Applications show that the algorithm can generate a high quality triangular mesh model and provide technical support for accurate 3D modeling and visualized management of a goaf. KEY WORDS goafs:laser scanning:spherical projection:triangulation:algorithms 收稿日期：201404-09 基金项目：“十二五”国家科技支撑计划专题(2012BAK09B0205):中央高校基本科研业务费资助项目(2013zts061)

工程科学学报，第 37 卷，第 7 期: 823--830，2015 年 7 月 Chinese Journal of Engineering，Vol． 37，No． 7: 823--830，July 2015 DOI: 10． 13374 /j． issn2095--9389． 2015． 07． 001; http: / /journals． ustb． edu． cn 复杂采空区激光扫描拼合散乱点云球面投影三角剖 分算法 罗周全，罗贞焱，张文芬，周吉明，黄俊杰 中南大学资源与安全工程学院，长沙 410083  通信作者，E-mail: luozhenyan@ qq． com 摘 要 利用三维激光扫描技术对采空区进行探测以建立三维可视化模型，从而准确获取其三维空间位置和形态，是矿山采 空区事故隐患综合治理工作中的重要环节． 但由于采空区形态复杂，往往需要从多个方位对其进行多次探测才能准确获取 采空区完整的三维形态． 如何对多次探测点云数据拼合后的散乱点云构建三角网格模型，是实现复杂采空区三维探测建模 的关键． 本文提出了采空区激光扫描拼合散乱点云数据球面投影三角剖分生长算法，首先选定球心将原位点云投影到球面 上得到投影点云，然后对投影点云进行三角剖分，最后将投影点云三角网空间拓扑关系还原到原位点云，从而构建复杂采空 区三角网模型． 为了有效实现算法，研究了球面投影参数设定、XYZ 三向单元栅格点云搜索策略、三角形生成规则、优势顶点 边界切分策略、边界闭合策略、不规则三角形优化策略等多种方法． 实际应用表明，所研究的算法能够生成优质的采空区三 角网模型，为实现复杂采空区三维精确建模及可视化管理提供了重要技术支持． 关键词 采空区; 激光扫描; 球面投影; 三角剖分; 算法 分类号 TD325 + . 4 Spherical projection triangulation algorithm for laser-scanning splice unorganized points of complex goafs LUO Zhou-quan，LUO Zhen-yan ，ZHANG Wen-fen，ZHOU Ji-ming，HUANG Jun-jie 收稿日期: 2014--04--09 基金项目: “十二五”国家科技支撑计划专题( 2012BAK09B02--05) ; 中央高校基本科研业务费资助项目( 2013zzts061) School of Ｒesources and Safety Engineering，Central South University，Changsha 410083，China  Corresponding author，E-mail: luozhenyan@ qq． com ABSTＲACT Detection of a goaf by laser-scan technology to build a 3D visualized model and to obtain the goaf's 3D space position and shape，is an important part for comprehensive management of the goaf's accidents． Multiple probes from multiple orientations are usually needed to obtain a goaf's 3D shape because of its complexity． How to construct a triangular mesh model from splice unorganized points by multiple probes is the key technology of a goaf's 3D modeling． A spherical projection triangulation algorithm is proposed for laser-scanning splice unorganized points of a goaf in this paper． Firstly，projected points are got by a chosen sphere center and project￾ing in-situ points onto the sphere． Secondly，the projected points are triangularized completely． Then topological relations are reverted from the projected points to the in-situ points． At last，a triangular mesh model of the goaf is constructed． In order to effectively imple￾ment the algorithm，many methods are studied such as the spherical projection parameters setting，XYZ-orientation cell grid points searching strategy，triangle generation rules，boundary segment strategy by advantage vertexes，boundary closure strategy，and irregu￾lar triangle optimization strategy． Applications show that the algorithm can generate a high quality triangular mesh model and provide technical support for accurate 3D modeling and visualized management of a goaf． KEY WOＲDS goafs; laser scanning; spherical projection; triangulation; algorithms

·824· 工程科学学报，第37卷，第7期 金属和非金属地下矿山开采中形成的采空区使围 冒顶区 岩和矿柱应力集中，易造成冒顶、片帮、坍塌等灾害 由于矿山采空区潜在的危险性，行业加大采空区事故 隐患综合治理力度，将采空区探测技术与装备研发列 片帮坍塌 探测育区 为“十二五”重要研究课题. 采空区 残留未爆 目前，国内外采空区的探测技术主要有工程钻探、 探测盲区 地球物理勘探、激光扫描探测等技术·-习，在准确获取 实际边界 采空区三维形态方面，激光扫描探测技术具有一定的 设计边界 优势，其探测成果经过处理后可用于采矿设计、采场回 采指标计算、数值模拟分析、可视化安全监管等方 探头 底部结构 面.应用较广泛的采空区激光扫描探测设备有加 图2复杂采空区探测盲区示意图 拿大的空区监测系统CMS和英国的空区自动扫描 Fig.2 Detection blind spots of a complex goaf 激光系统C-ALS⑦ 针对采空区激光扫描探测数据处理和可视化建 数据进行去噪、拼合和稀释处理后，得到无序的拼合散 乱点云数据.如何对拼合散乱点云进行有效三角剖 模，现有的三维建模软件大多集中在对单次探测的数 据进行处理.单次激光扫描探测的点云是有序渐进 分，是实现复杂采空区三维精确建模的基础. 的，其空间拓扑关系明显，不难构建采空区三角网模 1 研究思路及关键问题 型.实践表明，采空区由于爆破作业、失稳破坏等因素 针对单次探测的空间拓扑关系明显的有序点云数 致使其形态复杂，通常需要从多个方位多次探测才能 据，可采用基于格网的三角剖分算法和最大张角三角 获取其完整形态.采空区激光探测原理是从采空区内 剖分算法进行三角剖分，实现采空区的三维模型构 部往采空区边界进行扫描，扫描探头的中心位置是固 建网.针对多次探测的复杂采空区的拼合散乱点云， 定的，通过抬高扫描探头角度和360°旋转探测采空区 目前可参考的主要方法有三维Delaunay三角剖分方 边界，探测原理见图1.将采空区扫描探头伸入到采 法p-@、阵面（前沿）推进法(advancing front meth- 空区内部是探测的前提，常用的测杆伸入采空区内 od)-四、八叉树(octree)法四等.但上述方法多为通 部的通道是巷道或钻孔.由于采空区设计形态、片帮 用方法，对复杂形态的采空区的适应性还需进一步研 坍塌、爆破残留、底部结构等因素的影响，使得采空 究.本文对复杂采空区的拼合散乱点云三角剖分进行 区形态复杂，加上进入采空区探测通道和测杆长度 专门研究. 限制，容易出现探测盲区，如图2所示，图中①、②和 由于需要从多方位多次探测获得复杂采空区边界 ③区为探测盲区. 的完整点云，因此考虑寻求一个能够与采空区拼合散 乱点云全部通视的虚拟中心点从而避免出现探测盲 区.基于此，将散乱拼合原位点云投影到以虚拟中心 倾角范围0-140 点为球心的球面上获得投影点云，首先在球面上对投 10 影点云进行三角剖分，然后将三角网空间拓扑关系还 140 59 原到原位点云.在球面上对投影点云三角剖分，其优 势在于有共同的参照点（球心），便于判断左右关系和 扫描头 每个倾角 顺/逆时针方向，能参考使用平面的三角网生成方法. 连续旋转360 根据上述思路提出采空区激光扫描拼合散乱点云 球面投影三角剖分算法.该算法以球面投影点云为研 究对象，算法开始前需要对点云进行球面投影换算和 优化搜索，算法结束后需要将球面投影点云的三角网 图1采空区激光扫描探测原理 格空间拓扑关系还原到原位点云，输出三角网.算法 Fig.1 Principle of laser-scanning detection for a goaf 随着搜索区域推移按照三角形生成准则不断吸收新点 生成三角形，三角网逐步拓展最终形成完整的三角网. 为了避免出现探测盲区，通常需要从多个方位对 算法研究技术路线见图3. 采空区进行多次探测.当一个探测通道存在探测盲区 时，可选择其他通道进行多次探测，从而获得采空区边 2投影球面参数 界形态完整点云数据.对多次探测的采空区边界点云 如果存在一个虚拟点，能够对多次探测的拼合散

工程科学学报，第 37 卷，第 7 期 金属和非金属地下矿山开采中形成的采空区使围 岩和矿柱应力集中，易造成冒顶、片帮、坍塌等灾害． 由于矿山采空区潜在的危险性，行业加大采空区事故 隐患综合治理力度，将采空区探测技术与装备研发列 为“十二五”重要研究课题． 目前，国内外采空区的探测技术主要有工程钻探、 地球物理勘探、激光扫描探测等技术［1 － 2］，在准确获取 采空区三维形态方面，激光扫描探测技术具有一定的 优势，其探测成果经过处理后可用于采矿设计、采场回 采指标 计 算、数 值 模 拟 分 析、可视化安全监管等方 面［3 － 5］． 应用较广泛的采空区激光扫描探测设备有加 拿大的空区监测系统 CMS［6］和英国的空区自动扫描 激光系统 C--ALS［7］． 针对采空区激光扫描探测数据处理和可视化建 模，现有的三维建模软件大多集中在对单次探测的数 据进行处理． 单次激光扫描探测的点云是有序渐进 的，其空间拓扑关系明显，不难构建采空区三角网模 型． 实践表明，采空区由于爆破作业、失稳破坏等因素 致使其形态复杂，通常需要从多个方位多次探测才能 获取其完整形态． 采空区激光探测原理是从采空区内 部往采空区边界进行扫描，扫描探头的中心位置是固 定的，通过抬高扫描探头角度和 360°旋转探测采空区 边界，探测原理见图 1． 将采空区扫描探头伸入到采 空区内部是探测的前提，常用的测杆伸入采空区内 部的通道是巷道或钻孔． 由于采空区设计形态、片帮 坍塌、爆破残留、底部结构等因素的影响，使得采空 区形态复杂，加上进入采空区探测通道和测杆长度 限制，容易出现探测盲区，如图 2 所示，图中①、②和 ③区为探测盲区． 图 1 采空区激光扫描探测原理 Fig． 1 Principle of laser-scanning detection for a goaf 为了避免出现探测盲区，通常需要从多个方位对 采空区进行多次探测． 当一个探测通道存在探测盲区 时，可选择其他通道进行多次探测，从而获得采空区边 界形态完整点云数据． 对多次探测的采空区边界点云 图 2 复杂采空区探测盲区示意图 Fig． 2 Detection blind spots of a complex goaf 数据进行去噪、拼合和稀释处理后，得到无序的拼合散 乱点云数据． 如何对拼合散乱点云进行有效三角剖 分，是实现复杂采空区三维精确建模的基础． 1 研究思路及关键问题 针对单次探测的空间拓扑关系明显的有序点云数 据，可采用基于格网的三角剖分算法和最大张角三角 剖分算法进行三角剖分，实现采空区的三维模型构 建［8］． 针对多次探测的复杂采空区的拼合散乱点云， 目前可参考的主要方法有三维 Delaunay 三角剖分方 法［9 － 10］、阵 面 ( 前 沿) 推 进 法 ( advancing front meth￾od) ［11 － 12］、八叉树( octree) 法［13］等． 但上述方法多为通 用方法，对复杂形态的采空区的适应性还需进一步研 究． 本文对复杂采空区的拼合散乱点云三角剖分进行 专门研究． 由于需要从多方位多次探测获得复杂采空区边界 的完整点云，因此考虑寻求一个能够与采空区拼合散 乱点云全部通视的虚拟中心点从而避免出现探测盲 区． 基于此，将散乱拼合原位点云投影到以虚拟中心 点为球心的球面上获得投影点云，首先在球面上对投 影点云进行三角剖分，然后将三角网空间拓扑关系还 原到原位点云． 在球面上对投影点云三角剖分，其优 势在于有共同的参照点( 球心) ，便于判断左右关系和 顺/逆时针方向，能参考使用平面的三角网生成方法． 根据上述思路提出采空区激光扫描拼合散乱点云 球面投影三角剖分算法． 该算法以球面投影点云为研 究对象，算法开始前需要对点云进行球面投影换算和 优化搜索，算法结束后需要将球面投影点云的三角网 格空间拓扑关系还原到原位点云，输出三角网． 算法 随着搜索区域推移按照三角形生成准则不断吸收新点 生成三角形，三角网逐步拓展最终形成完整的三角网． 算法研究技术路线见图 3． 2 投影球面参数 如果存在一个虚拟点，能够对多次探测的拼合散 · 428 ·

罗周全等：复杂采空区激光扫描拼合散乱点云球面投影三角剖分算法 825 投 5(a)所示.自动选定方式及通过在采空区的纵向方向 换算 探测原位点云 球面投影点云 搜索策略 求取断面，断面呈现一定的收缩或者扩大的趋势，在中 XYZ方位体 间收缩最明显的断面位置，求取断面的中心点即为球 确定中心点和球半径 素栅格搜索 心，见图5().单个球心可拓展为多个球心，对于较 环六壁搜索 预处理 为狭长的采空区（包括巷道），可沿其中心轨迹线选择 多个球心，组合实现连续的点云球面投影，见图5(c) 初始三角形 +新点三角剖分 生长边界处理 所示. 活跃点判慨 边界自检 如果投影球半径过小或过大，则导致投影点云间 最大张角准则 优势顶点切分 距太近或太远，都不利于三角形生成判断.球面半径 成小距离准则 闭合边界处理 宜与采空区跨度、高度和宽度等参数相当，可取上述参 输出三角形 输出三角形 输出三角形 数较大值作为投影球半径.确定投影球面参数后，可 投影点云三角网容器 根据球心C(x,y,z)和半径R建立点云的投影关系 空间拓扑 关系还原 算法主体 如下.图6为点云球面投影示意图. rx1=x0+(x。-x）×R/D, 原位点云三角网容器 算法结束 y=y。+(y。-y）×R/D, (1) 图3研究技术路线图 a=2o+(o-ze)×R/D. Fig.3 Research technical route 式中，xoy和0为原位点坐标，xy1和1为投影点坐 标，D为原位点到球心的距离. 乱点云全部通视，即定义为虚拟中心点，以虚拟中心点 为球心，以某一值为半径确定一个球面，将采空区边界 3点云搜索策略 原位点云数据投影到球面，得到球面投影的点云数据. 采空区单次探测点数一般为2万~3万个，采空 点云球面投影示意见图4 区拼合散乱点数一般为4万~6万个，有时甚至超过 10万个.为了提高对点云检索和三角剖分效率，需要 虚拟中心 投影球面 探寻较高效率的搜索策略.一般是从海量点云中提取 采空区 距离最近的少量点，如K邻域搜索方法.K邻域搜 索算法关键是建立一个合理高效的索引存储结构，目 描中心 打描中心2 前主要包括立方体栅格(CG)方法和索引树（如kd- tree和Octree)方法.立方体栅格方法目前常用的为子 空间环六壁搜索方式，即取子空间外层的26个体素， 图4点云球面投影示意图 查找K个最近点6-m,多采用Hash函数建立数据点 Fig.4 Spherical projection of points 与立方栅格之间的相互对应关系陶 研究发现这种环六壁的搜索方式，在最大对角的 投影球面参数主要包括球心和投影半径.投影球 方位可能搜到较远的点，从而生成错乱的三角形，同时 心可通过人工选定和自动选定两种方式确定.人工选 这种Hash函数的对应关系转换难度较大.本文基于 定可在三维界面Y视图、XZ视图和YZ视图分别选 体素栅格的思想，研究了XYZ三向单元栅格搜索方 定中心所在平面，三平面正交点即为虚拟中心点，如图 式，通过合理的单元栅格的结构体（见表1）和搜索策 三个方向选择 球心 采空区 球心3 采空区判断断面 球心2 球心 球心I 中心轨迹 (a) (b) (e) 图5球心选择方式示意图.(a)人工选定方式：(b)自动选定方式：(c)中心轨迹线选定方式 Fig.5 Ways of selecting the sphere center:(a)manual selection;(b)automatic selection;(c)center path selection

罗周全等: 复杂采空区激光扫描拼合散乱点云球面投影三角剖分算法 图 3 研究技术路线图 Fig． 3 Ｒesearch technical route 乱点云全部通视，即定义为虚拟中心点，以虚拟中心点 为球心，以某一值为半径确定一个球面，将采空区边界 原位点云数据投影到球面，得到球面投影的点云数据． 点云球面投影示意见图 4． 图 5 球心选择方式示意图． ( a) 人工选定方式; ( b) 自动选定方式; ( c) 中心轨迹线选定方式 Fig． 5 Ways of selecting the sphere center: ( a) manual selection; ( b) automatic selection; ( c) center path selection 图 4 点云球面投影示意图 Fig． 4 Spherical projection of points 投影球面参数主要包括球心和投影半径． 投影球 心可通过人工选定和自动选定两种方式确定． 人工选 定可在三维界面 XY 视图、XZ 视图和 YZ 视图分别选 定中心所在平面，三平面正交点即为虚拟中心点，如图 5( a) 所示． 自动选定方式及通过在采空区的纵向方向 求取断面，断面呈现一定的收缩或者扩大的趋势，在中 间收缩最明显的断面位置，求取断面的中心点即为球 心，见图 5( b) ． 单个球心可拓展为多个球心，对于较 为狭长的采空区( 包括巷道) ，可沿其中心轨迹线选择 多个球心，组合实现连续的点云球面投影，见图 5( c) 所示． 如果投影球半径过小或过大，则导致投影点云间 距太近或太远，都不利于三角形生成判断． 球面半径 宜与采空区跨度、高度和宽度等参数相当，可取上述参 数较大值作为投影球半径． 确定投影球面参数后，可 根据球心 C( xc，yc，zc) 和半径 Ｒ 建立点云的投影关系 如下． 图 6 为点云球面投影示意图． x1 = x0 + ( x0 － xc) × Ｒ /D， y1 = y0 + ( y0 － yc) × Ｒ /D， z1 = z0 + ( z0 － zc) × { Ｒ /D． ( 1) 式中，x0、y0和 z0为原位点坐标，x1、y1和 z1为投影点坐 标，D 为原位点到球心的距离． 3 点云搜索策略 采空区单次探测点数一般为 2 万 ～ 3 万个，采空 区拼合散乱点数一般为 4 万 ～ 6 万个，有时甚至超过 10 万个． 为了提高对点云检索和三角剖分效率，需要 探寻较高效率的搜索策略． 一般是从海量点云中提取 距离最近的少量点，如 K 邻域搜索方法［14］． K 邻域搜 索算法关键是建立一个合理高效的索引存储结构，目 前主要包括立方体栅格( CG) 方法［15］和索引树( 如 kd￾tree 和 Octree) 方法． 立方体栅格方法目前常用的为子 空间环六壁搜索方式，即取子空间外层的 26 个体素， 查找 K 个最近点［16 － 17］，多采用 Hash 函数建立数据点 与立方栅格之间的相互对应关系［18］． 研究发现这种环六壁的搜索方式，在最大对角的 方位可能搜到较远的点，从而生成错乱的三角形，同时 这种 Hash 函数的对应关系转换难度较大． 本文基于 体素栅格的思想，研究了 XYZ 三向单元栅格搜索方 式，通过合理的单元栅格的结构体( 见表 1) 和搜索策 · 528 ·

·826· 工程科学学报，第37卷，第7期 tor容器： (⑤)在X方向依次搜索每层栅格包含的点，判断 是否满足条件并进行存储，实现无缝搜索 Z方向搜索、 X方向搜索 max_Pl 点云 图6点云球面投影示意图 Fig.6 Schematic illustration of point spherical projection 略，可实现X、Y和Z三个方向的正负向搜索，同样通 min Pte-土-- 过控制三个方位递增可实现环六壁搜索，如图7所示 XYZ三向体素栅格搜索方式简单易操作，效率高且不 环六壁搜索 Y方向搜索 容易出错，以X方位为例说明其搜索步骤如下： 图7XYZ三向单元栅格点云搜索策略 Fig.7 X.Y and Z-orientation cell grid points search strategy 表1结构体的成员列表 Table 1 Structure's member-ist 搜索步距可通过长方体包盒边长和每边布设N 结构体 成员列表 说明 个栅格来计算，一般来说栅格数控制在50~200个较 为合适. struct_point 点结构体 doubleX: {点的X坐标： _point 4点云球面投影三角剖分生长算法 double Y: 点的Y坐标： double Z:} 点的Z坐标：} 4.1基本定义及算法步骤 structCell 栅格结构体 为了更好地阐述算法，作如下基本定义，参见 {point Pt: {原位点： 图8. _point PuPj 球面投影点： Cell 定义1生长边界：三角剖分中，由已剖分区域向 int nX; X向栅格数： 未剖分区域拓展的三角网的边界为生长边界 int nY; Y向栅格数： int nZ:} Z向栅格数：} 定义2活跃边：根据一定规则判断最可能生成 新三角形的生长边界中的一条边 (1)将原位点云按照投影规则生成投影点云； 定义3活跃点：根据一定规则判断最可能与活 (2)计算包含所有投影点云的长方体包盒的最外 跃边结合生成新三角形的一个点. 顶点（图7的max_Pt)和最内顶点（图7的min_P): 定义4边界切分：生长边界在拓展时，会形成拓 (3)将投影点坐标与最内顶点坐标的差值除以步 展裂缝或者空洞，此时需要将生长边界进行切分，切分 距（图7的m_step),分别得到X、Y和Z方向栅格数； 出闭合部分则通过边界闭合策略进行三角剖分，新的 (4)按照立方体栅格结构体进行存储，存到Vec- 生长边界继续拓展. 生长边界 代势顶点 裂隙 球心 新三角形 收活跃边 ,活跃点 逆时针判定P点在AB线左边 边界切分 优势顶点闭合部分 图8基本定义说明 Fig.8 Description of basic definitions

工程科学学报，第 37 卷，第 7 期 图 6 点云球面投影示意图 Fig． 6 Schematic illustration of point spherical projection 略，可实现 X、Y 和 Z 三个方向的正负向搜索，同样通 过控制三个方位递增可实现环六壁搜索，如图 7 所示． XYZ 三向体素栅格搜索方式简单易操作，效率高且不 容易出错，以 X 方位为例说明其搜索步骤如下: 图 8 基本定义说明 Fig． 8 Description of basic definitions 表 1 结构体的成员列表 Table 1 Structure's member-list 结构体 成员列表 说明 _point struct _point { double X; double Y; double Z; } 点结构体 { 点的 X 坐标; 点的 Y 坐标; 点的 Z 坐标; } _Cell struct _Cell { _point Pt; _point PtPj ; int nX; int nY; int nZ; } 栅格结构体 { 原位点; 球面投影点; X 向栅格数; Y 向栅格数; Z 向栅格数; } ( 1) 将原位点云按照投影规则生成投影点云; ( 2) 计算包含所有投影点云的长方体包盒的最外 顶点( 图 7 的 max_Pt) 和最内顶点( 图 7 的 min_Pt) ; ( 3) 将投影点坐标与最内顶点坐标的差值除以步 距( 图 7 的 m_step) ，分别得到 X、Y 和 Z 方向栅格数; ( 4) 按照立方体栅格结构体进行存储，存到 Vec￾tor 容器; ( 5) 在 X 方向依次搜索每层栅格包含的点，判断 是否满足条件并进行存储，实现无缝搜索． 图 7 XYZ 三向单元栅格点云搜索策略 Fig． 7 X，Y and Z-orientation cell grid points search strategy 搜索步距可通过长方体包盒边长和每边布设 N 个栅格来计算，一般来说栅格数控制在 50 ～ 200 个较 为合适． 4 点云球面投影三角剖分生长算法 4. 1 基本定义及算法步骤 为了 更 好 地 阐 述 算 法，作 如 下 基 本 定 义，参 见 图 8． 定义 1 生长边界: 三角剖分中，由已剖分区域向 未剖分区域拓展的三角网的边界为生长边界． 定义 2 活跃边: 根据一定规则判断最可能生成 新三角形的生长边界中的一条边． 定义 3 活跃点: 根据一定规则判断最可能与活 跃边结合生成新三角形的一个点． 定义 4 边界切分: 生长边界在拓展时，会形成拓 展裂缝或者空洞，此时需要将生长边界进行切分，切分 出闭合部分则通过边界闭合策略进行三角剖分，新的 生长边界继续拓展． · 628 ·

罗周全等：复杂采空区激光扫描拼合散乱点云球面投影三角剖分算法 827 定义5优势顶点：优势顶点为生长边界上满足位点的空间拓扑关系，输出采空区三角网模型 一定的角度阈值的凸出顶点，为切分边界判断点 4.2三角形生成规则 定义6顺/逆时针：面向球心如果三角形的三个 有效三角剖分应满足三个条件：(1)三角形应尽 顶点为逆时针排序则称为逆时针三角形，否则为顺时 可能接近规则的等边或等腰三角形：(2)三角形不能 针三角形网.同理可确定点位于直线的左边还是 出现交叉：(3)所有的点云必须全部三角剖分.在点 右边. 云三角剖分过程中，随着新点不断加入，生长边界不 采空区激光扫描拼合散乱点云球面投影三角剂分 断扩张，生长边界好比一根带磁的线，把最近的点不 生长算法基本步骤如下： 断的吸引到线上，如何寻找活跃点和活跃边以生成 (1)从搜索区域点中任取一点作为初始点，初始 三角形，需要研究形成三角形生成规则.本文研究了 点与距离其最近的点形成初始边，相对初始边张角最 最短距离判据和最大张角判据两种三角形生成 大的点为第三点，从而生成初始三角形.初始三角形 规则 即为初始生长边界. 最短距离判据是寻求某离散点到生长边界中某边 (2)根据三角形生成规则，遍历搜索点和生长边 的距离最短情况，确定活跃点和活跃边.点到线段的 界，寻找最优的活跃点和活跃边，生成三角形，更新生 距离计算方法如图9(a)所示.当6，大于90，距离d为 长边界. P,A的长度：当62大于90，距离d为P2B的长度：否则， (3)在拓展过程中生长边界会出现狭长的缝隙或 距离d为P到AB的垂线长度.利用最短距离准则求 空洞，采用优势顶点切分策略对生长边界进行切分. 活跃点时，如果日，或6，角度过大但距离最短时，则容 (4)切分的闭合部分采用边界闭合策略进行三角 易产生狭长三角形. 剖分，新的生长边界继续拓展 最大张角判据是寻求某离散点对应生长边界中某 (5)当最后的搜索点都连入三角网，采用边界闭 边的张角最大情况，确定活跃点和活跃边.张角可通 合策略对未封闭边界进行闭合处理 过空间三点求余弦计算出来.最大张角准则示意图如 (6)采用三角形优化策略对所有三角形进行一次 图9(b)所示.0、0和02为张角，如果点P的张角最大， 全面检查和优化，消除局部不规则三角形 则P为活跃点，AB为活跃边.最大张角准则能够有效 (7)将投影点云三角剖分空间拓扑关系还原到原 的避免狭长三角形，生长边界拓展效果好 (a) ) 图9三角形生成规则.()最短距离判据：(b)最大张角判据 Fig.Triangle generation rules:(a)the shortest distance criterion:(b)the maximum angle criterion 在利用最大张角判据找到活跃点后，还需增加活 跃边前后两点的张角对比判断，择优生成三角形，新点 ● 和前后点择优方法选择如图10所示.通过最大张角 i+2 判断P为活跃点后，还需对比P点、前点(i+2)和后 点(i-1)相对于活跃边(i,i+1)的三个张角(A, +1 A,A2)的大小，在三点中选择张角最大的点与活跃边 生成三角形.这种方法集新点加入和边界检查于一 体，能生成较理想的三角网. 4.3优势顶点边界切分策略 生长边界在扩张过程中，会形成一些狭长的裂缝 图10活跃点和前后点择优生成三角形 或者空洞，需要及时处理，否则会影响边界的拓展效 Fig.10 Triangle generated by choosing from the active point,former 果.本文研究了一种优势顶点切分策略来处理边界的 point and latter point 裂缝和空洞.其基本思路参见图11 (1)遍历边界上每个顶点，当顶点为外凸顶点且 夹角小于90时，则认为该顶点为优势顶点.图中顶点

罗周全等: 复杂采空区激光扫描拼合散乱点云球面投影三角剖分算法 定义 5 优势顶点: 优势顶点为生长边界上满足 一定的角度阈值的凸出顶点，为切分边界判断点． 定义 6 顺/逆时针: 面向球心如果三角形的三个 顶点为逆时针排序则称为逆时针三角形，否则为顺时 针三角 形［19］． 同理可确定点位于直线的左边还是 右边． 采空区激光扫描拼合散乱点云球面投影三角剖分 生长算法基本步骤如下: ( 1) 从搜索区域点中任取一点作为初始点，初始 点与距离其最近的点形成初始边，相对初始边张角最 大的点为第三点，从而生成初始三角形． 初始三角形 即为初始生长边界． ( 2) 根据三角形生成规则，遍历搜索点和生长边 界，寻找最优的活跃点和活跃边，生成三角形，更新生 长边界． ( 3) 在拓展过程中生长边界会出现狭长的缝隙或 空洞，采用优势顶点切分策略对生长边界进行切分． ( 4) 切分的闭合部分采用边界闭合策略进行三角 剖分，新的生长边界继续拓展． ( 5) 当最后的搜索点都连入三角网，采用边界闭 合策略对未封闭边界进行闭合处理． ( 6) 采用三角形优化策略对所有三角形进行一次 全面检查和优化，消除局部不规则三角形． ( 7) 将投影点云三角剖分空间拓扑关系还原到原 位点的空间拓扑关系，输出采空区三角网模型． 4. 2 三角形生成规则 有效三角剖分应满足三个条件: ( 1) 三角形应尽 可能接近规则的等边或等腰三角形; ( 2) 三角形不能 出现交叉; ( 3) 所有的点云必须全部三角剖分． 在点 云三角剖分过程中，随着新点不断加入，生长边界不 断扩张，生长边界好比一根带磁的线，把最近的点不 断的吸引到线上，如何寻找活跃点和活跃边以生成 三角形，需要研究形成三角形生成规则． 本文研究了 最短距 离 判 据 和 最 大 张 角 判 据 两 种 三 角 形 生 成 规则． 最短距离判据是寻求某离散点到生长边界中某边 的距离最短情况，确定活跃点和活跃边． 点到线段的 距离计算方法如图 9( a) 所示． 当 θ1大于 90，距离 d 为 P1 A 的长度; 当 θ2大于 90，距离 d 为 P2B 的长度; 否则， 距离 d 为 P 到 AB 的垂线长度． 利用最短距离准则求 活跃点时，如果 θ1或 θ2角度过大但距离最短时，则容 易产生狭长三角形． 最大张角判据是寻求某离散点对应生长边界中某 边的张角最大情况，确定活跃点和活跃边． 张角可通 过空间三点求余弦计算出来． 最大张角准则示意图如 图 9( b) 所示． θ、θ1和 θ2为张角，如果点 P 的张角最大， 则 P 为活跃点，AB 为活跃边． 最大张角准则能够有效 的避免狭长三角形，生长边界拓展效果好． 图 9 三角形生成规则． ( a) 最短距离判据; ( b) 最大张角判据 Fig． 9 Triangle generation rules: ( a) the shortest distance criterion; ( b) the maximum angle criterion 在利用最大张角判据找到活跃点后，还需增加活 跃边前后两点的张角对比判断，择优生成三角形，新点 和前后点择优方法选择如图 10 所示． 通过最大张角 判断 P 为活跃点后，还需对比 P 点、前点( i + 2) 和后 点( i － 1) 相对于活跃边( i，i + 1) 的三个张角( Amax， A1，A2 ) 的大小，在三点中选择张角最大的点与活跃边 生成三角形． 这种方法集新点加入和边界检查于一 体，能生成较理想的三角网． 4. 3 优势顶点边界切分策略 生长边界在扩张过程中，会形成一些狭长的裂缝 或者空洞，需要及时处理，否则会影响边界的拓展效 果． 本文研究了一种优势顶点切分策略来处理边界的 裂缝和空洞． 其基本思路参见图 11． ( 1) 遍历边界上每个顶点，当顶点为外凸顶点且 图 10 活跃点和前后点择优生成三角形 Fig． 10 Triangle generated by choosing from the active point，former point and latter point 夹角小于 90°时，则认为该顶点为优势顶点． 图中顶点 · 728 ·

·828· 工程科学学报，第37卷，第7期 角度∠APB小于90°，则外凸顶点P为一个优势顶点. 展开搜索下一个备选切分点 (2)采用顶点夹角扇形展开方式搜索切分点，以 (3)在所有的备选切分点中，选择距离优势顶点 优势顶点的一条临边AP为参考边，搜索判断某边界 P最近的点作为生长边界的切分点，构建切分线段划 点与参考边形成的角度，当角度∠APC大于顶点角度 分出闭合部分.闭合部分通过边界闭合策略进行三角 ∠APB时，则将C点作为一个备选切分点，类似扇形 剖分，新的生长边界继续拓展 123456 闭合部分 切分线段 生长边界 图11优势顶点边界切分策略 Fig.11 Boundary segment strategy by advantage vertexes 4.4边界闭合策略 三角形，如图14(a)所示.针对顶点聚集的三角形，首 根据优势顶点切分策略划分的闭合部分可能为裂 先根据三角形角度关系将需要优化的三角形的从三角 缝或空洞，需要研究边界闭合策略对闭合部分进行三 网中全部提取出来，另存到不规则三角形容器，然后通 角剖分以保证三角网全封闭.边界闭合策略如图12 过相邻三角形的共边关系，提取共边相连的三角形群 所示. 的顶点边界；最后将提取边界根据边界闭合策略进行 裂隙的边界闭合策略：通过比较闭合边界上某条 三角剖分，输出较规则的三角网格，如图14(b)所示 边(i,i+1)对应的前点i+2和后点i-1的张角大小 (6,和6，)，张角不能小于某阈值，取张角较大的点与 该边生成三角形，更新裂隙边界，直至三角剖分完全. 空洞的边界闭合策略：首先采用上述边界策略进 行局部三角剖分，当空洞边界所有边的前后点张角(， 局部狭长三角形 和日)都小于某阈值时，此时采用插入中心点的方式， 根据空洞边界确定中心点，以中心点为顶点依次与空 顶点聚集三角形 洞的边生成三角形，直至完全封闭空洞 图13不规则三角形 已剖分区域 生长边界 Fig.13 Irregular triangle 4.6算法效果分析 闭合部分 通过分析，算法最耗时的步骤为活跃点和活跃边 裂缝 0 切分线段 的搜索和判断，时间复杂性为0(n2).遍历的生长边 空洞 界点数为100~500个，遍历搜索的点云数在50~200 个之间，n控制在500以内，效率高.对于三角形优化 已剖分区域 步骤，时间复杂性为O(nlgn),n为三角网中全部三角 形数，一般为3万~5万个.算法在酷睿双核CUP,4G 图12边界闭合策略 内存环境中运行，生成约5万个三角形，耗时在30s以 Fig.12 Boundary closure strategy 内，算法效率较高。运用研究的算法生成的采空区三 角网模型效果如图15和图16所示.可见采空区三角 4.5不规则三角形优化策略 网模型中三角形规整，少有狭长和顶点聚集的三角形， 在三角剖分点云搜索过程中，由于存在搜索栅格 是一种有效的采空区激光扫描拼合散乱点云三角剖分 边界，邻近搜索边界的点在三角剖分时，容易出现局部 方法 狭长三角形或顶点聚集的三角形，统称为不规则三角 形，如图13所示，需要对这些三角形进行优化. 5结论 针对局部狭长三角形，搜索与其长边共边的另外 由于采空区复杂的实际形态和激光探测技术自身 个三角形，通过判断交换对角线，生成的两个较规则 的特征，为了避免探测盲区需要从多个方位多次探测

工程科学学报，第 37 卷，第 7 期 角度∠APB 小于 90°，则外凸顶点 P 为一个优势顶点． ( 2) 采用顶点夹角扇形展开方式搜索切分点，以 优势顶点的一条临边 AP 为参考边，搜索判断某边界 点与参考边形成的角度，当角度∠APC 大于顶点角度 ∠APB 时，则将 C 点作为一个备选切分点，类似扇形 展开搜索下一个备选切分点． ( 3) 在所有的备选切分点中，选择距离优势顶点 P 最近的点作为生长边界的切分点，构建切分线段划 分出闭合部分． 闭合部分通过边界闭合策略进行三角 剖分，新的生长边界继续拓展． 图 11 优势顶点边界切分策略 Fig． 11 Boundary segment strategy by advantage vertexes 4. 4 边界闭合策略 根据优势顶点切分策略划分的闭合部分可能为裂 缝或空洞，需要研究边界闭合策略对闭合部分进行三 角剖分以保证三角网全封闭． 边界闭合策略如图 12 所示． 裂隙的边界闭合策略: 通过比较闭合边界上某条 边( i，i + 1) 对应的前点 i + 2 和后点 i － 1 的张角大小 ( θ1和 θ2 ) ，张角不能小于某阈值，取张角较大的点与 该边生成三角形，更新裂隙边界，直至三角剖分完全． 空洞的边界闭合策略: 首先采用上述边界策略进 行局部三角剖分，当空洞边界所有边的前后点张角( θ3 和 θ4 ) 都小于某阈值时，此时采用插入中心点的方式， 根据空洞边界确定中心点，以中心点为顶点依次与空 洞的边生成三角形，直至完全封闭空洞． 图 12 边界闭合策略 Fig． 12 Boundary closure strategy 4. 5 不规则三角形优化策略 在三角剖分点云搜索过程中，由于存在搜索栅格 边界，邻近搜索边界的点在三角剖分时，容易出现局部 狭长三角形或顶点聚集的三角形，统称为不规则三角 形，如图 13 所示，需要对这些三角形进行优化． 针对局部狭长三角形，搜索与其长边共边的另外 一个三角形，通过判断交换对角线，生成的两个较规则 三角形，如图 14( a) 所示． 针对顶点聚集的三角形，首 先根据三角形角度关系将需要优化的三角形的从三角 网中全部提取出来，另存到不规则三角形容器，然后通 过相邻三角形的共边关系，提取共边相连的三角形群 的顶点边界; 最后将提取边界根据边界闭合策略进行 三角剖分，输出较规则的三角网格，如图 14( b) 所示． 图 13 不规则三角形 Fig． 13 Irregular triangle 4. 6 算法效果分析 通过分析，算法最耗时的步骤为活跃点和活跃边 的搜索和判断，时间复杂性为 O( n2 ) ． 遍历的生长边 界点数为 100 ～ 500 个，遍历搜索的点云数在 50 ～ 200 个之间，n 控制在 500 以内，效率高． 对于三角形优化 步骤，时间复杂性为 O( nlgn) ，n 为三角网中全部三角 形数，一般为 3 万 ～ 5 万个． 算法在酷睿双核 CUP，4G 内存环境中运行，生成约 5 万个三角形，耗时在 30 s 以 内，算法效率较高． 运用研究的算法生成的采空区三 角网模型效果如图 15 和图 16 所示． 可见采空区三角 网模型中三角形规整，少有狭长和顶点聚集的三角形， 是一种有效的采空区激光扫描拼合散乱点云三角剖分 方法． 5 结论 由于采空区复杂的实际形态和激光探测技术自身 的特征，为了避免探测盲区需要从多个方位多次探测 · 828 ·

罗周全等：复杂采空区激光扫描拼合散乱点云球面投影三角剖分算法 ·829· 提取边界 共边关系 交换对角线 提取边界 (a) b 图14三角形优化策略.(a)交换对角线：(b)提取边界 Fig.14 Irregular triangle optimization strategy:(a)switching diagonal:(b)extraction boundary 杂采空区激光扫描拼合散乱点云三角剖分的有效方 法.算法的实现对复杂采空区精确三维建模及可视化 安全管理具有重要现实意义. 参考文献 [Liu D W,Xu G Y,Huang R D,et al.A new technique for pros- pecting exhausted areas in metal mines.China Min,2000,9(4): 图15生成的某采空区三角网模型 Fig.15 A goaf's triangular mesh model generated by the algorithm (刘敦文，徐国元，黄仁东，等.金属矿采空区探测新技术 中国矿业，2000,9(4)：34) [2]Guo J,Gu D S,Luo Z Q.A new technique of 3D laser survey of finished stopes in metal mines.Min Metall Eng,2006,26(5): 16 (过江，古德生，罗周全.金属矿山采空区3D激光探测新技 术.矿治工程，2006,26(5)：16) [3]Luo ZQ,Liu X M,Zhang B,et al.Cavity 3D modeling and cor- relative techniques based on cavity monitoring.Cent South Univ Technol,2008,15(5):639 图16采空区三角网模型的局部显示 4]Luo Z Q,Yang B.Liu X M,et al.Research on CMS-aided blast Fig.16 Local image of the goaf's triangular mesh model design for ore pillar extraction.Met Mine,2007(3):15 (罗周全，杨彪，刘晓明，等.采用CMS辅助矿柱回采爆破设 才能获取采空区完整的三维形态，针对多次探测的拼 计研究.金属矿山，2007(3)：15) 合散乱点云，研究提出了将原位点云先投影到球面进 [5]Luo Z Q,Luo Z Y,Liu X M,et al.Simulation prediction of sta- 行三角剖分，然后将三角网空间拓扑关系还原到原位 bility in large-scale stope mining and verification by the moni-o- 点云的研究思路，并实现了点云球面投影三角剖分生 ring results.Min Metall Eng,2009,29 (6):5 长算法，主要技术成果如下. (罗周全，罗贞焱，刘晓明，等。大规模采场开采稳定性模拟 (1)对球面投影参数进行研究.提出了人工选 预测与实测验证.矿治工程，2009,29(6)：5) 定、自动选定和中心轨迹三种球心选定方式，研究确定 6]Cavity Monitoring System User Manual (Version 2.3).Canada: Optech System Corporation,1996 了投影球面的半径确定方法和投影变换关系 7]Ma YT,Peng W.Study on cavity-autoscanning laser system (C- (2)提出了海量拼合散乱点云的搜索策略以提升 ALS)and its application in Anging Copper Mine.Nonferrous Met 算法的效率.以合理单元栅格存储结构，基于体素栅 Mine Sect,2013,65(3):1 格思想，提出了XYZ三向体素栅格搜索方式. (马玉涛，彭威。采空区三维激光扫描系统C一ALS及其在安 (3)实现了点云球面投影三角剖分生长算法.主 庆铜矿的应用.有色金属：矿山部分，2013,65(3)：1) 要包括最短距离判据和最大张角判据两种三角形生成 [8]Luo Z Y.The Research of Goaf's 3D Visual System Based on CMS 规则、处理边界的优势顶点切分策略、封闭裂缝和空洞 Detection [Dissertation].Changsha:Central South University, 2010 的边界闭合策略、不规则三角形优化策略等关键技术. (罗贞焱.基于CMS探测的采空区三维可视化系统研究[学位 (4)实际应用效果表明，所研究形成的算法三角 论文].长沙：中南大学，2010) 剖分效率高，能够生成优质的采空区三角网模型，为复 [9]Alonso-Sanz R,Adamatzky A.On Delaunay triangulation automa-

罗周全等: 复杂采空区激光扫描拼合散乱点云球面投影三角剖分算法 图 14 三角形优化策略． ( a) 交换对角线; ( b) 提取边界 Fig． 14 Irregular triangle optimization strategy: ( a) switching diagonal; ( b) extraction boundary 图 15 生成的某采空区三角网模型 Fig． 15 A goaf's triangular mesh model generated by the algorithm 图 16 采空区三角网模型的局部显示 Fig． 16 Local image of the goaf's triangular mesh model 才能获取采空区完整的三维形态，针对多次探测的拼 合散乱点云，研究提出了将原位点云先投影到球面进 行三角剖分，然后将三角网空间拓扑关系还原到原位 点云的研究思路，并实现了点云球面投影三角剖分生 长算法，主要技术成果如下． ( 1) 对球面投影参数进行研究． 提出了人工选 定、自动选定和中心轨迹三种球心选定方式，研究确定 了投影球面的半径确定方法和投影变换关系． ( 2) 提出了海量拼合散乱点云的搜索策略以提升 算法的效率． 以合理单元栅格存储结构，基于体素栅 格思想，提出了 XYZ 三向体素栅格搜索方式． ( 3) 实现了点云球面投影三角剖分生长算法． 主 要包括最短距离判据和最大张角判据两种三角形生成 规则、处理边界的优势顶点切分策略、封闭裂缝和空洞 的边界闭合策略、不规则三角形优化策略等关键技术． ( 4) 实际应用效果表明，所研究形成的算法三角 剖分效率高，能够生成优质的采空区三角网模型，为复 杂采空区激光扫描拼合散乱点云三角剖分的有效方 法． 算法的实现对复杂采空区精确三维建模及可视化 安全管理具有重要现实意义． 参 考 文 献 ［1］ Liu D W，Xu G Y，Huang Ｒ D，et al． A new technique for pros￾pecting exhausted areas in metal mines． China Min，2000，9( 4) : 34 ( 刘敦文，徐国元，黄仁东，等． 金属矿采空区探测新技术． 中国矿业，2000，9( 4) : 34) ［2］ Guo J，Gu D S，Luo Z Q． A new technique of 3D laser survey of finished stopes in metal mines． Min Metall Eng，2006，26( 5) : 16 ( 过江，古德生，罗周全． 金属矿山采空区 3D 激光探测新技 术． 矿冶工程，2006，26( 5) : 16) ［3］ Luo Z Q，Liu X M，Zhang B，et al． Cavity 3D modeling and cor￾relative techniques based on cavity monitoring． J Cent South Univ Technol，2008，15( 5) : 639 ［4］ Luo Z Q，Yang B，Liu X M，et al． Ｒesearch on CMS-aided blast design for ore pillar extraction． Met Mine，2007( 3) : 15 ( 罗周全，杨彪，刘晓明，等． 采用 CMS 辅助矿柱回采爆破设 计研究． 金属矿山，2007( 3) : 15) ［5］ Luo Z Q，Luo Z Y，Liu X M，et al． Simulation prediction of sta￾bility in large-scale stope mining and verification by the moni-to￾ring results． Min Metall Eng，2009，29( 6) : 5 ( 罗周全，罗贞焱，刘晓明，等． 大规模采场开采稳定性模拟 预测与实测验证． 矿冶工程，2009，29( 6) : 5) ［6］ Cavity Monitoring System User Manual ( Version 2． 3) ． Canada: Optech System Corporation，1996 ［7］ Ma Y T，Peng W． Study on cavity-autoscanning laser system ( C-- ALS) and its application in Anqing Copper Mine． Nonferrous Met Mine Sect，2013，65( 3) : 1 ( 马玉涛，彭威． 采空区三维激光扫描系统 C--ALS 及其在安 庆铜矿的应用． 有色金属: 矿山部分，2013，65( 3) : 1) ［8］ Luo Z Y． The Ｒesearch of Goaf's 3D Visual System Based on CMS Detection ［Dissertation］． Changsha: Central South University， 2010 ( 罗贞焱． 基于 CMS 探测的采空区三维可视化系统研究［学位 论文］． 长沙: 中南大学，2010) ［9］ Alonso-Sanz Ｒ，Adamatzky A． On Delaunay triangulation automa- · 928 ·

·830· 工程科学学报，第37卷，第7期 ta with memory.Nano Commun Netcorks,2013,4(4):216 3D points.Comput Simul,2009.26(9):338 [0]Adamatzky A.Excitable Delaunay triangulations.Kybernetes, (陈伟，刘肖琳.一种快速三维敢乱点云的三角副分算法， 2011,40(5-6):719 计算机仿真，2009,26(9)：338) [11]Wu B H,Wang S J.Automatic triangulation over three-limen- [16]Xiong B S,He M,Yu H.Algorithm for finding K nearest neigh- sional parametric surfaces based on advancing front method.Fi- bors of scattered points in three dimensions.I Comput Aided Des nite Elem Anal Des,2005,41(90):892 Comput Graphics,2004,16(7):909 [12]Ito Y,Shih A M,Erukala A K,et al.Parallel unstructured (熊邦书，何明，俞华.三维散乱数据的K个最近邻域快速 mesh generation by an advancing front method.Math Comput 搜素算法，计算机辅助设计与图形学学报，2004,16(7)： Simd.,2007,75(56):200 909) [13]Wang J H,Xu Q X,Zhang R.Delaunay algorithm and related [17]Dickerson M T,Drysdale R L S,Sack J R.Simple algorithms for procedure to generate the tetrahedron mesh for an object with ar- enumerating interpoint distances and finding K nearest neighbors. bitrary boundary.Chin J Rock Mech Eng,2003,22(5):71 Int J Comput Geom Appl,1992.2(3):221 (王建华，徐强勋，张锐.任意形状三维物体的Delaunay网 [18]Hu R L.Research on Method of the 3D Seattered Points Triangu- 格生成算法，岩石力学与工程学报，2003,22(5)：71) lation [Dissertation].Nanjing:Nanjing University of Science 14]Dong H W.Study for cell grid methods finding K nearest neigh- and Technology,2003 bours.Comput Eng Appl,2007,43 (21)52 (胡荣林.散乱数据三角剖分方法研究[学位论文].南京： (董洪伟.求K邻域的体素栅格算法研究.计算机工程与应 南京理工大学，2003) 用，2007,43(21)：52) [19]Joseph.OR.Computational Geometry C.2nd Ed.Cambridge: [15]Chen W,Liu X L.A fast triangulation algorithm for unorganized Cambridge University Press,1997

工程科学学报，第 37 卷，第 7 期 ta with memory． Nano Commun Networks，2013，4( 4) : 216 ［10］ Adamatzky A． Excitable Delaunay triangulations． Kybernetes， 2011，40( 5-6) : 719 ［11］ Wu B H，Wang S J． Automatic triangulation over three-dimen￾sional parametric surfaces based on advancing front method． Fi￾nite Elem Anal Des，2005，41( 9-10) : 892 ［12］ Ito Y，Shih A M，Erukala A K，et al． Parallel unstructured mesh generation by an advancing front method． Math Comput Simul，2007，75( 5-6) : 200 ［13］ Wang J H，Xu Q X，Zhang Ｒ． Delaunay algorithm and related procedure to generate the tetrahedron mesh for an object with ar￾bitrary boundary． Chin J Ｒock Mech Eng，2003，22( 5) : 71 ( 王建华，徐强勋，张锐． 任意形状三维物体的 Delaunay 网 格生成算法，岩石力学与工程学报，2003，22( 5) : 71) ［14］ Dong H W． Study for cell grid methods finding K nearest neigh￾bours． Comput Eng Appl，2007，43( 21) : 52 ( 董洪伟． 求 K 邻域的体素栅格算法研究． 计算机工程与应 用，2007，43( 21) : 52) ［15］ Chen W，Liu X L． A fast triangulation algorithm for unorganized 3D points． Comput Simul，2009，26( 9) : 338 ( 陈伟，刘肖琳． 一种快速三维散乱点云的三角剖分算法， 计算机仿真，2009，26( 9) : 338) ［16］ Xiong B S，He M，Yu H． Algorithm for finding K nearest neigh￾bors of scattered points in three dimensions． J Comput Aided Des Comput Graphics，2004，16( 7) : 909 ( 熊邦书，何明，俞华． 三维散乱数据的 K 个最近邻域快速 搜索算法，计算机辅助设计与图形学学报，2004，16 ( 7) : 909) ［17］ Dickerson M T，Drysdale Ｒ L S，Sack J Ｒ． Simple algorithms for enumerating interpoint distances and finding K nearest neighbors． Int J Comput Geom Appl，1992，2( 3) : 221 ［18］ Hu Ｒ L． Ｒesearch on Method of the 3D Seattered Points Triangu￾lation ［Dissertation］． Nanjing: Nanjing University of Science and Technology，2003 ( 胡荣林． 散乱数据三角剖分方法研究［学位论文］． 南京: 南京理工大学，2003) ［19］ Joseph． O Ｒ． Computational Geometry C． 2nd Ed． Cambridge: Cambridge University Press，1997 · 038 ·