基于三维建模算法在激光盘煤的研究

李学相　彭崇高

摘要： 为有效解决激光盘煤中三维建模的算法效率问题，提出一种基于Delaunay三角剖分的改良算法。该算法在处理离散点生成凸壳和形成三角网时的方法，凸壳生成采用最高点相连的办法，三角网的形成采用延伸法，使得生成凸壳所需遍历点的个数和三角网生成所需时间减少，并找到该算法的不足之处。最后介绍了改进的算法在激光盘煤系统中的应用，通过改进的算法建立的模型计算煤堆的体积。通过实验结果分析表明，改进的算法执行的效率有了很大的提升。

关键词：激光盘媒；三维模型；三角剖分；延伸法；凸壳

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2015）28-0174-03

Research on 3D Modeling Algorithm Based On Laser Coal Stocktaking

LI Xue-xiang， PENG Chong-gao

（College of Software Technology， Zhengzhou University， Zhengzhou Henan 450000， China）

Abstract： To solve the problem of the efficiency of three-modeling in laser disc coal effectively， put forward an improved algorithm based on Delaunay triangle subdivision. The algorithm in dealing with discrete points generated convex hull and formation of triangulation method， convex hull generated the highest point is linked together， the formation of the triangulation using extension method， decreases the number of traverse points needed for generating convex hull and time needed for triangular mesh generation， and find the shortcoming of the algorithm. Finally introduces the improved algorithm in the application of laser disc coal system， by improving the algorithm model of calculating the volume of the coal. By analyzing the experimental results show that the improved algorithm execution efficiency has a great improvement.

Key words： Laser coal stocktaking； three-dimensional model； triangulation； extension method； convex hull

1 前言

把Delaunay三角网的特性应用到实际环境中是当今社会各行各业的热潮。但是由于该算法易于实现，且时间复杂度高，所以还是有很多改良版的三角网出现。在此算法的基础上，产生很多种新算法：基于文献[1]Sloan算法的效率是比较高的，但是该算法仅对于处理平面散乱的点集，且处理的程序比较复杂。再后来Huang和Sihih对Sloan算法进行了改进文献[2]；Guibas也对进行改进，即DAG（directed acyclic graph）此算法可以实现对点在几何图形中的定位搜索，时间复杂度达到[Ologn]，但由于数据占用了大量的存储空间，算法也不够简洁。还有一些相关算法，如金字塔算法文献[3]、基于Voronoi图的新型几何插值文献[4]的等都是非常有效的。在此基础上，本文提出了一种改进的算法，并介绍改算法激光盘煤系统中得以应用。传统的激光盘煤系统：以激光扫描仪配以角度测量实现煤堆表面有限点的二维空间位置坐标的测量。此后改进的设备中，我们还必须用编码器和PLC数据采集机同激光扫描仪一起使用，才可以得到点的三维空间坐标信息。最后以空间点信息建模，并计算出煤堆的体积，并可以对煤堆进行一些分割、合并的操作。以此方便对煤的使用进行调配。

算法的基本思想是，先通过处理得到的点云数据，通过点数据建立三维模型，再对模型进行一些相对以实际工作中的一些操作。而算法实现的核心都是在于寻找形成三角形的第三点做工作。

2 点集的处理

初始化的点云数据A数组PAY、点云A的链表存放PLT、生成的三角形链表存放TLT、Delaunay三角剖分后点A的链表PLT、三角形数TCT=0。

2.1凸壳的生成

生成简单的凸壳如图1所示。改进的凸壳生成算法最高点相连的方法步骤如下：

步骤1. 先在点云数据A中，求出横坐标最大和最小值与纵坐标最大和最小值，分别为[xmax]、 [xmin] 、[ymax]、 [ymin]。如图1.所示可有[p0（xmin，y0）]，[p4（xmax，y4）]，由线段[p0p4]作为划分线，上下部分又分为[K]个小区间，并从左到右编号从1到[K]，[K]的取值为取整（是一个由经验决定大小的数）。

步骤2. 判断点是否在线段[p0p4]上。在图1中可以得到[S?=p5，p6，p7，p8，p9，p13，p14]。从左和右双向判断每个小区间的点[y]坐标的最大值[pymax]，（这里只描述从左方向开始）并连接点[p0pymax]。由两点之间的线段公式

可判断点是否在线段[p0pymax]之上，如不在则此小区间判断完毕。

步骤 3. 如步骤2中存在点在线段之上，则把线段[p0pymax]之上的点从新找出纵坐标[y]最大点并连接点，此时用连接线段的点作为起点。，重新开始步骤2和步骤3，直到没点在[p0pymax]线段之上。重复操作直到判断到点集的最高点完毕如图2。

步骤 4. 在线段[p0p4]下方的点，[S?=p1，p2，p3，p10，p11，p12，p15]从左和右双向同时判断每个小区间[y]坐标的最小值[pymin]。（这里只描述从左方向开始）并连接[p0pymin]。判断点是否在[p0pymin]之下，如不在则此小区间判断完毕。

步骤 5. 如步骤4中存在点在线段之下，则把线段[p0pymin]之下的点从新找出纵坐标[y]最小的点并连接，此时用线段的端点作为起点。重新开始步骤4和步骤5，直到没有点在线段[p0pymin]之下。每个小区间重复操作到点集的最低点完毕。

步骤 6. 以上步骤连成的点就是凸壳的边界点，边成线就是凸壳。按以上步骤顺时针将边存到数组PLT中。

该算法存在如果在点数比较少的时候，形成凸壳的时间也不会有很大的减少，甚至有可能会增加。但当点数达到一定量时候，形成的时间肯定会减少。

2.2 Delaunay三角网生成

形成三角网的延伸法，以凸壳上的边为种子边，寻找第三点以边形成三角形，将所有的边同时判断产生三角形，生成三角形所构成的边，再同时进行下一个三角形的判断，以此循环，直到最后一个点。步骤如下：

步骤 1. 以生成凸壳的边为种子扩展边，将所有的边并行判断。以一条边为例，如图3中的[p0p7]，在链表PAY中寻找点[p13]，使角[p0p13p7]最大，此时生成三角形[p0p13p7]。以此类推，逆时针遍历完整个凸壳的边。得到的三角形存放在TLT.

步骤 2. 边的使用。在完成步骤1时，将链表PLT清空，把构成三角形所形成的新边加入链表。

步骤3扩展三角形。重新以边链表为起始开始以步骤1方法判断。如图3所示：以[p1p13]为一边，在链表PAY中寻找点[p16]，以此类推，直至最后一点。在第二步骤形成的边链表中，寻找第三点的过程，需要把形成边的边界点加入到第三点的寻找过程中，如边[p7p8]与边界点[p13]。最后得到的三角形存放在TLT。

新三角形生成需加入到三角形链表TLT中，并且TCT次数加1。当点成为封闭点和半封闭点时候。删除封闭点和半封闭点，可加快第三点的搜索。

由文献[5]和[6]可以判断封闭点和半封闭边界点。判断构成三角形的点，如果没有凸壳上的点，则该点是封闭点。如图3中的[p11]。当该点构成三角形，如该点在凸壳上时候，则该点是半封闭点，如图3中的[p1]、[p2]。

步骤 4. 三角形链表TLT即为所求的三角剖分。

由文献[7的知Delaunay三角网的判断方法：

1）在形成的三角网格中，任意一个三角形的外接圆都不包含任何其他的点。如图4。

2）在构成的三角网格的所有点，Delaunay三角剖分所形成的三角形有最小角最大的特性。就是指一种相邻的两个三角形形成凸四边形的时候，在对角线交换时六个内角的最小角不再增大。如图5.

判断三角形链表TLT中的三角形的特性，是符合上述的条件。

2.3三维重建

煤堆体积分析的是一种空间三维分析，一般情况下，对三维模型的分析，都是在数字高程模型（Digital Elevation Model 简称DEM）上进行的。如果生成的DEM在精度和密度上都符合生产时的要求，这样对具体事务的三维分析便可很容易的实现。而最常用的一种DEM是TIN DEM。

所谓的TIN结构的三角形在平面结构的投影是不规则，然而它在不规则的基础上它也有一定的规则可循：它是一个非重叠覆盖的区域，且每一个三角形的形成必定有其特在的特点和符合构建时候的要求。

由煤场的扫描的点数据，通过上述的算法进行计算，我们可以得到在三维空间的一个煤堆的模型，在通过对煤堆的一些处理，就可以得到准确的煤堆模型。并且这个算法处理的模型中的构建也是符合Delaunay剖分的所以特性的。

而在煤场的建模中，计算体积时，因为基数都是以吨位单位的，故不需要涉及太精密的计算，有这种精度的模型，完全可以符合对煤的调度。

2.4 体积计算

改进的算法形成的三角网格的体积，可以由单个三菱柱体积计算累加所得。三菱柱的投影面积（是指三菱柱在水平面投影成三角形的面积）[Si]，可计算此面积的海伦计算公式为：

其中[p]为投影三角形的周长，[ΔX]、[ΔY]是两顶点之间[X]、[Y]方向的坐标差。

现由单个三菱柱体积可得，进行体积求和，则可以求出整个图形的体积。

计算公式为：

[Zi1]、[Zi2]、[Zi3]表示第i个TIN的规则格网的点的高程。[Si]为第i个三角形或规则格网的投影面积。

3 在激光盘煤系统中的应用

随着科技的进步，大型电力集团公司对能耗低，污染控制管理水平提高有了更高的认识，但还远远没达到对资源利用最大化的标准。且时至今日， 大多数火力发电集团公司对料场存料的管理，仍然沿袭百年的传统--人工盘存。故而急需一种现代化的激光盘煤工具，来实现对煤的更好调配使用。

激光盘煤的种类众多。由于具体配置和激光盘煤的原理不同，可分为几大类，十多种具体的模式。比如：全自动、斗轮机（固定式）、多功能等。

我们在通过设备得到煤堆的点数据后，通过上述的改良算法，创建一个煤堆的三维模型和计算模型的体积，进而配以煤堆的密度求出煤的质量；从上面描述，我们可以看到，在影响最后结果的准确性有以下几个因素：点测量的精度，创建模型的精度。我们评价一款现代化的激光盘煤系统好坏的标准就是以此为依据。当然，设备可靠稳定，使用的方便，效率也必须提前考虑。还有最后得到煤堆体积的误差大小也应该考虑其中，一般我们有一个可接受的误差范围5%左右，这个也是一个重要评判的标准。

通过数据采集，将数据转换成三维坐标形式的数据。处理生成好的三维坐标数据，首先把三维点投影到二维上，即此时先不管Z轴坐标，然后通过上面描述的Delaunay算法，得到一系列三角形。此时便可以得到在平面的三角网。

由这些三角网关系，再构建体积计算模型。网格中的三角形，每个顶点与其相应的空间三维点，即此时要处理Z轴坐标，构成三菱柱体。故由平面的三角网，可得到以其对应的三菱柱体群，便可构成三维图形。所有的三菱柱体的体积便可以看成煤场体积的一个近似结果。

这就是激光盘煤系统中对一煤堆的三维建模并且求得体积的应用。

4 实例

通过在煤场中取得的一些点数据，用于建立模型，通过生成时所需要的时间如表格1可以得出，改进的算法可以相对的节约时间，大大提高了运行的效率。

5结语

本文提出了一种改良的三维建模算法。通过该算法在激光盘煤系统中的应用，可建立煤堆的三维模型，和需要的煤堆体积和质量并可对煤堆进行分割、合并等操作。这样具体应用中好方便对煤的调配。

同时该算法也存在不足，对煤堆扫描得到的点数据，要求比较严格。并且存在着一些影响计算结果准确性的因数。同时体积的计算跟扫描点有关，点越多体积得到的越精确。这样也增加了计算量，影响计算速度，并且增加的扫描仪的工作。

在实际应用中，还存在一些有光线产生的一些问题，如反射性不均匀、物面倾斜、机械扫描误差、现场大功率环境等等因数的影响。

因此，随着科技的进步，激光盘煤系统还需进一步的研究和改进。

参考文献：

[1] 杨钦.限定Delaunay三角网剖分技术[M].北京：电子工业出版社，2005.

[2]Sloan S W.A fast algorithm constructing Delaunay triangulations in the plane[J]. Adv Eng Softw Workstat， 1987，9（1）；34-35

[3] 张忠武，吴信才.平面海量散乱点集凸壳算法[J].计算机工程，2009，35（9）：43-45.

[4] 周小平，周瑞忠.基于Voronoi图的新型几何插值及其与传统代数插值方法的比较[J].岩石力学与工程学报，2005（1）.

[5] 孙继忠，胡艳，马永强 ，基于Delaunay三角解剖分生成Voronoi图算法[J].计算机应用，2010，30（1）.

[6] 凌海滨， 吴兵. 改进的自连接Delaunay三角网生成算法[J].计算机应用，1999，19（12）：10-12.

[7] 袁洋.激光盘煤系统的研究[D]. 北京： 华北电力大学， 2009.