黄浩洋　邓飞　隆振海　常煜

摘要：Delaunay三角剖分在计算几何、计算机图形学、计算机辅助设计、有限元分析、地理信息系统等邻域有广泛的应用，是一项极为基础且重要的离散数据网格化技术。生长算法是一种重要的Delaunay剖分算法，具有较高的理论价值和实际意义，该算法思路简单且容易扩展，可以拓展到三维点云曲面的构造中。但是现有的生长法效率不高，无法处理海量数据，本文经研究提出了一种基于Delaunay空圆性质的改进算法，在逐边定向扩展过程中直接利用Delaunay空圆性质，迅速缩小备选扩展点集的范围，大幅提高了三角网生长速度。大量的随机和规则数据测试表明该改进算法效率提升显著，与已有生长算法相比有10倍以上的提高，且数据量越大效率提升越明显。

关键词： Delaunay三角网；三角网生长算法；空外接圆特性；计算机图形学；数据

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2016）23-0188-04

Abstract： Delaunay triangulation in computational geometry， computer graphics， computer-aided design， finite element analysis， geographic information systems and other neighbors have a wide range of applications， is an extremely basic and important discrete data gridding techniques. Growth algorithm is an important Delaunay triangulation algorithm， with high theoretical value and practical significance， the algorithm is simple and easy extension ideas， can be extended to construct a three-dimensional point cloud in surface. But the existing growth method is not efficient， can not handle huge amounts of data， this paper presents a study by an empty circle nature of inferences based on Delaunay improved algorithm by-side expansion process through verification extension points and extensions edge meets the Delaunay empty circle the nature of inference， you can quickly narrow the range of options for expansion point set， a substantial increase in the growth rate of triangulation. A lot of random and regular data tests show that the improved algorithm efficiency significantly， compared with the existing algorithms have grown more than 10-fold increase， the greater the efficiency and the amount of data more obvious.

Key words： delaunay triangulation； growth triangulation algorithm； empty circumcircle properties； computer graphics； data

Delaunay三角剖分是计算几何中的一种重要算法，在计算机辅助设计、三维表面重建、三维可视化、有限元分析等方面都有着十分广泛的应用。Delaunay三角网由于具有最小角最大的性质，被公认为最优三角网。根据三角网构建过程的不同，Delaunay三角剖分算法可以分为逐点插入、分治和生长法三种。逐点插入法于1977年由Lawson提出的，随后许多学者进行了研究并改进，如文献[5]，该算法思路简单易于编程并且内存消耗少，但是该算法需要花费大量时间在查询以及定位三角形，增加了它的时间复杂度。分治算法是另一种著名的构网算法，许多学者也对分治算法进行了研究并改进如文献[8]，该算法中的子网合并过程比较复杂，算法实现难度相对较大。……