基于Quad?Edge结构的散乱点集三角剖分并行算法研究及实现

摘 要： 三角剖分算法在计算几何中的地位非常重要，其中三角网格的剖分效率及质量对后续研究有着重要的影响。对Delaunay三角剖分算法的基本原理进行了分析，基于散乱点集研究了基于Quad?Edge结构下的分治算法，并将目前流行的Map?Reduce并行编程模型引入到对散乱点集进行基于Delaunay三角剖分中。实验结果表明基于Map?Reduce编程模型实现的三角剖分并行化在大数据量的情况下大大提高了剖分的效率，速度明♒显高于基于Quad?Edge结构实现的分治算法以及基于三角形索引的Bowyer?Watson三角剖分算法，并且具有很好的弹性计算能力，这对三角剖分的后续研究有重要的借鉴作用。

关键词： Delaunay三角剖分算法; Quad?Edge; 并行算法; 三角网格

Parallel algorithm of Delaunay triangulation dividing for scattered point set

based on Quad?Edge structure

FU Jian?sheng， MA Cun?liang

（Institute of Electromagnetic Field and Microwave Technology， Southwest Jiaotong University， Chengdu 610031， China）

Abstract： The triangulation dividing ตalgorithm plays an important role in computational geometry， in which the efficiency and quality of triangular mesh are inseparably linked with the follow?up study. In this paper， the basic principle of Delaunay triangulation dividing algorithm is analyzed and the divide?and?conquer algorithm for scattered☏ point set is investigated based on the Quad?Edge structure. The popular Map?Reduce parallel programming model is introduced to the Delaunay triangulation dividing algorithm when dealing with scattered point set. The experiment result shows the parallel triangulation dividing parallelization can improve the efficiency of this algorithm in the case of mass data by means of Map?Reduce Programming Model. Furthermore， this method has good elastic capacity and the efficiency is obviously higher than another two methods， namely the divide?and?conquer algorithm based on the Quad?Edge structure and the Bowyer?Watson triangulation dividing algorithm with triangular index.

Keywords： Delaunay triangulation algorithm; Quad?Edge; parallel algorithm; triangular mesh

0 引 言

1 Delaunay三角剖分算法

在数值分析、图形学以及有限元分析中，三角剖分都是极其重要的一项预处理技术。而Delaunay[6?7]三角剖分是运用最多的三角剖分方法。其中Delauna❤y三角剖分必须符合两个重要的准则：第一，空外接圆特性，即在Delaunay三角网格中任意四个点不能共圆，同时任一三角形的外接圆范围内不能有其他的点存在;第二，最小内角最大，即在散点集形成的三角剖分中，所形成的三角形的最小角最大。在两个相邻的三角形构成凸四边形的对角线中，在相互交换后，六个内角的最小角不再增大。 2 基于三角形边索引Bowyer?Watson算法

基于逐点插入法[8]的Bowyer?Watson算法是基于Bowyer算法与Watson算法并在两者的基础之上进行改进而来的，因其简单易于实现而得到广泛的应用。此算法的思想是首先构建包含所有散乱点集的超级大三角形，然后选择其他未处理的离散点插入进来，在已经构成的三角形中查找这些三角形的外接圆包含这个新加入的散乱点的三角形，并把这些三角形删除掉，那么会形成一个包含这个新插入点的多边形，然后把这个点与多边形的各个顶点进行连接，从而构成多个新的三角形网格，重复这样的处理直到所有的点都处理完为止。此算法的相当大的时间损耗在了对空腔的查找，原始的算法要对形成的三角形进行遍历查找，而基于三角形边索引的方式则大大减少了对待插入点进行空腔查找的时间，此三角形边索引的结构如图1所示。

E：＼王芳＼现代电子技术201506＼现代电子技术15年38卷第6期＼Image＼45T1.tif

图1 三角形边索引结构

基于改进后的Bowyer?Watson大大提高了对包围待插入点的空腔的寻找速度，从而提高了三角网格剖分的速度。

3 基于Map?Reduce实现的三角剖分并行化

3.1 Quad?Edge结构介绍

图2 Quad?Edge结构

在Quan?Edge结构中边next为以点origin为起点并且对与[e（0）]边的下一个边可以以逆时针方向找到，同时由于存储了Voronoi图的两边[e（1）]与[e（3）]，因此可以很容易从Delaunay三角网格图转换为Voronoi图。在本程序中，主要是用来对Delaunay边进行求解，所有都是为了简化处理去除了对应的Voronoi边。

3.2 Map?Reduce并行计算模型

Map?Reduce是一种目前在云计算平台上广泛使用的并行编程模型，主要用于对大规模数据集的并行计算，Map（映射）和Reduce（归并）是他的主要思想。Map?Reduce主要是通过启动多个Task（任务），对不同的数据集进行处理返回相应Task的处理结果，然后对返回的结果集进行Reduce处理，从而得到最终的结果。从上可以看出，通过启动不同的Task数量可以很轻松地实现并行计算能力的提升，具有很高的弹性计算能力。 ϡ

3.3 三角剖分算法基于Map?Reduce思想的实现

基于Map?Reduce并行编程思想的Delaunay三角剖分算法处理步骤如下：

第一步：输入散乱点集的坐标，记录相应点的坐标并根据x值将散乱点基于快速排序算法进行排序;

第二步：启动多个Task（任务）并对数据进行分块后分配给每个Task进行处理，在每个子集进行三角剖分的处理过程中使用Quad?Edge结构存储剖分的数据，对于剖分的子过程可以使用改进后的Bowyer?Watson算法也可以使用分治算法[11]，此程序在实现时使用的分治算法，并返回相应的剖分后的结果;

第三步：对返回的结果进行Reduce操作。对数据集进行合并时对于上下边切线的查找使用Zig?Zag[2]算法，当Reduce处理完成后返回结果即为三角剖分的网格。该程序通过基于Map?Reduce进行处理的流程图如图3所示。

E：＼王芳＼现代电子技术201506＼现代电子技术15年38卷第6期＼Image＼45T3.tif

图3 Map?Reduce网格剖分过程

该程序中使用的主要数据结构及算法简介如下：

/*定义边的关系，基于Quad?Edge进行改进，去除对应的Voronoi边关系*/

QuadEdge（void）

{

e[0].num = 0;

e[1].num = 1;

e[0].ePrev = （e[1]）;

e[0].eNext = （e[1]）;

e[1].ePrev = （e[0]）;

e[1].eNext = （e[0]）;

visited = false;

}

//二维中点的x，y坐标值

Point2d（double tx， double ty）

： x（tx）， y（ty） {

}

//数据合并

delaunayMerge（MaxEdge retleft，MaxEdge retright）

{

//数据合并

MaxEdge rettemp; //临时两三角剖分结果相联接

Edge *ldo， *ldi; //包围左边剖分结果集的边

Edge *rdo， *rdi; //包围右边剖分结果集的边

……

Return rettemp; //返回两边合并的结果集

}

4 结果验证及分析

在本测试算法中采用C++分别对基于三角形索引的Bowyer?Watson三角剖分算法、基于Quad?Edge结构下的三角剖分分治算法以及基于Map?Reduce编程模型实现的三角剖分并行化进行实现。其中对Map?Reduce并行实现启动四个Task。通过随机获取散乱点集点数50～1 000 000个，分别通过以上三个程序进行处理的结果如表1所示。

表1 算法针对目标散乱点集的计算结果

通过表1看出，在对少量点集的运算时由于改进后的Bowyer?Watson算法处理完插点后要遍历三角形链表，对含有初始构建大三角形顶点的三角形进行删除操作，所以相对要慢些，同时由于Map?Reduce过程需要进行任务拆分合并需要消耗时间，效果也不会好于基于Quad?Edge结构的分治算法，但是当点集数量非常大时，基于Map?Reduce编程模型实现的三角剖分并行化要明显优于其他两个算法，在点数100万的时候速度是改进后Bowyer?Watson算法效率的7倍，同时也要比Quad?Edge分治算法快得多，通过增加Task数量还可以进一步提高剖分效率。

图4是对含有1万个点的圆通过基于Map?Reduce编程模型实现的三角剖分并行化的剖分结果，从图四可以看出剖分后的网格很好的符合了Delaunay三角剖分的优化准则。

E：＼王芳＼现代电子技术201506＼现代电子技术15年38卷第6期＼Image＼45T4.tif

图4 基于Map?Reduce编程模型的剖分结果

5 结 语

本文通过使用Quad?Edge结构进行剖分结果的存储，并将Map?Reduce编程模型应用到三角网格剖分中，通过与其他两个方法对比证明此方法能够很好地提高三角网格剖分的效率，同时由于此编程模型具有很好的弹性计算能力，可以很轻松地通过增加task数量来进一步提高剖分的效率。如何将此并行编程模型应用到三维散乱点集中进行剖分处理，这将是要进一步研究的问题。

参考文献

[4] DEAN J， GHEMAWAT S. MapReduce： simplified data processing on large clusters [J]. Communications of the ACM， 2008， 51（1）： 107?113.

[5] CHEN S， SCHLOSSER S W. Map?reduce meets wider varieties of applications， IRP?TR?08?05 [R]. Pittsburgh： IRP， 2008.

[7] 余杰，吕品，郑昌文.Delaunay三角网构建方法比较研究[J].中国图象图形学报，2010，15（8）：1158?1167.

[8] 刘云，夏兴东，黄北生.基于分治算法与逐点插入法的Delaunay三角网建立算法的改进[J].现代测绘，2010（4）：14?16.