李学相　彭崇高

摘要： 为有效解决激光盘煤中三维建模的算法效率问题，提出一种基于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]的等都是非常有效的。在此基础上，本文提出了一种改进的算法，并介绍改算法激光盘煤系统中得以应用。传统的激光盘煤系统：以激光扫描仪配以角度测量实现煤堆表面有限点的二维空间位置坐标的测量。……