二维离散点集Delaunay三角网生长算法的改进

黄浩洋　邓飞　隆振海　常煜

摘要：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]，该算法中的子网合并过程比较复杂，算法实现难度相对较大。实际应用中逐点插入法因其实现简单、算法高效且占用内存较小而被广泛应用于二维三角网剖分中，但是因为算法本身特点，这两种方法都不易直接扩展到三维进行三维曲面网格剖分。生长法是一种利用三角网的判别法则，在逐边扩展中通过一定的生长法则构建Delaunay三角网的方法，该方法的优点在于易于扩展到三维空间，直接构建三维三角网。近年来许多学者都对生长算法进行了研究[7-10]，但对算法效率改进都不大，这大大限制了生长法在实际工程邻域中的应用。而采用一种基于Delaunay空外接圆性质的优化算法，在定向扩展中以此为条件，可以大幅度提升算法效率。

1 经典生长算法基本步骤

1.1 经典生长算法

经典的Delaunay三角网的生长算法是Brassel和Reif在1979年提出的。算法的基本思路是，先找出离散点集中相距最短的两个数据点并连接成为一条Delaunay边，此边作为初始边并加入扩展队列，寻找一个备选点使其与初始边满足Delaunay三角网的判别法则，检测备选点与扩展边两个端点连接的新扩展边的使用次数，若没有一条由扩展点形成的扩展边的使用次数达到2次以上则加入扩展边队列，否则舍弃该备选点。按照上述方法依次处理所有扩展边，直至最终完成。算法1是经典Delaunay三角网生长算法，算法1如下：

1.2 通过夹角余弦扩展

算法1中对于每一条扩展边，按照满足Delaunay三角网的判别法则寻找扩展点的过程就是算法2。算法2根据当前已经存在的一条Delaunay扩展边，遍历所有数据点找到距离扩展边中点最近的点作为备选点，检测备选点引出的两条新扩展边的使用次数，若有任意一条新扩展边使用次数达到2次以上则舍弃该备选点，然后比较备选点与扩展边端点构成的两向量的之间夹角的余弦值。找出余弦值最小的点作为扩展点算法2如下：

2 生长算法效率的改进

2.1 直接通过空外接圆性质扩展

通过表1可以看出经典生长算法效率很低，能够处理的离散点集的规模较小，不具有实际应用效果。算法1基本的三角网生长算法的核心部分是算法2夹角余弦扩展算法。造成算法2效率低的原因是边扩展过程中，需要逐点验证是否满足最小角最大的性质等，这样算法2的时间复杂度为 。

空外接圆性质是一种验证是否为Delaunay三角形的方法。但是可以直接将该性质用于定向扩展中，把经过扩展点和被扩展边的两点的圆是否满足空外接圆特性作为判断条件，逐点检测，直到寻找到一个满足判断条件的扩展点，并将新扩展边加入扩展边队列中。

2.2 空外接圆性质扩展的图解以及证明

根据公式确定外界圆后，对算法2进行改进，当算法2在已知扩展边以及扩展方向以后，首先扩展方向上取出任意一点作为扩展点（为了提高算法效率，可以取生长方向上距离扩展边最近的一个点）经过两次判定，第一次判定从扩展点到扩展边两个端点的两条边，有任意一条边使用次数达到2次以上时，舍弃该扩展点，第二次判定则为判断扩展点和扩展边的两端点的圆内部还有多少数据点，将这些数据点作为下一次备选点集，重复上述步骤直到备选点集大小为1时，并将该备选点作为扩展点。此为算法3，是对算法2的改进。

算法详解：

1） 2-3行是确定创建两个滚动数组便于存放下一次与当前需要扩展的点集。

2） 5-6行是确定是否找到扩展点满足空外接圆特性，没有则继续查找。

3） 7-12行是根据当前扩展点与扩展边确定外接圆C，然后将外接圆内部的扩展都加入点集合A，并将A作为下一次检测的点集。

经过一些数据测试，得到直接利用空外接圆性质生长效率表，如表2：

3 进一步加速生长算法

3.1 齐对称网格

在大量点集的搜索算法中，为了提高搜索效率，对于不规则的点集可以采用BSP算法，而对于均匀的点集可以采用齐对称网格算法。

齐对称网格算法可以对整体算法进行改进，首先将整个平面分成若干网格并将点与所在网格编号进行映射，对于算法3，先计算每一个网格的外接圆与当前圆的位置关系，如果两圆相交再利用算法3进一步筛选扩展点，否则淘汰当前网格。

3.2 使用齐对称网格优化算法

图3是利用改进生长算法对正六边形规则散点数据剖分的效果。由于规则的六边形数据会出现共圆现象，生长算法在边扩展时会同时找到多个备选点，而本文提出的改进算法可以有效处理共圆点数据，不会出现三角形交叉的错误现象，对规则均匀分布的数据具有完全一致的剖分效果。

4.2 生长法效率的对比

本文提出的改进的生长算法利用Delaunay空外接圆性质推论大幅度提高了三角网生长速度，与现有生长算法相比效率提升明显，实验表明对于大规模数据该改进算法效率提升达到10倍以上，且数据量越大效率提升越明显。表4列出了本文提出的改进算法与其他文献提出的生长法效率的对比。为了确保对比的客观和真实性，各种算法统一使用VS2008开发环境实现，在同一台测试机器上测试，测试机硬件条件：CPU为Intel-3610QM 2.3GHZ，内存4GB。

此处所对比的文献是参考文献中[4]，[9]，[10]文献。

5 结论

Delaunay三角剖分在计算机辅助设计、三维表面重建、三维可视化、有限元分析等方面都有着十分广泛的应用，是极为重要的一项预处理技术。改进的Delaunay生长算法依据三角剖分中的空圆特性，在确定扩展点的过程中，加入齐对称网格，判断每个网格与当前扩展边的位置关系，确定相交关系后再进行遍历，可以大大缩小搜索点的范围，提高算法的效率。将改进的Delaunay生长算法与插入算法进行对比，输入规模相同的离散点集，得到了相同的三角网，验证了本算法的正确性。本算法思路简单，易于扩展，可靠性高，生长速度快，可以对10万级甚至百万级别点集合进行三角网构建，具有明显的实际应用效果，设计思路对于三维空间的三角剖分也有借鉴意义。

参考文献：

[1] Ruprecht D，Muller H. Spatial free-form Deformation with Scatte red Data Interpolation Methods[J]. Computers and Graphics， 1995，19（1）：63-71.

[2] Ledoux H， Gold C. An Efficient Natural Neighbour Interpolation Algorithm for Geoscientific Modelling[J].Developments in Spatial Data Handling，2005：97-108.

[3] Perter Su，Robert L Scot Drysdale. A Comparisonof Ssequential，DelaunayTriangulation，Algorithms[J]. Computational Geometry，1997（7）：361-385.

[4] B Yang，S Shang .Research on Algorithm of the Point Set in the Plane Based on Delaunay Triangulation American Journal of Computational Mathematics[J]. American Journal of Computational Mathematics，2012，2（4）：336-340.

[5] XU Xu，LI Yuan，XG Chen. One algorithm of the Delaunay Triangulation on the Basis of Inserting Algorithm[J]. Computer & Information Technology， 2010

[6] 祝志恒.构建Delaunay三角网的一种新型生长法——壳外插入法[J].铁道科学与工程学报，2007，4（6）：67-72

[7] 赵文芳等.离散点集Delaunay三角网生成算法改进与软件开发[J].测绘工程，2003，12（4）：22-25.

[8] 刘云，夏兴东，黄北生.Delaunay三角网通用合并算子其分治算法的简化[J].现代测绘，2010，33（4）：14-16.

[9] 孙继忠，胡艳.基于Delaunay三角剖分生成voronoi图算法[J].计算机应用，2010，30（1）：75-77.

[10] 陈学工，陈树强，王丽青.基于凸壳技术的Delaunay三角网生成算法[J].计算机工程与应用，2006，42（06）：27-29.

[11] 周婷，彭正洪，密新武.Delaunay三角网生长算法改进与实现[J].图学学报，2013，34（5）：12-15.

[12] 姬安召，蓝燕.三角网增长算法构建Delaunay三角网DEM的原理与实现[J].测绘，2009，32（2）：65-69.