基于Quad?Edge結(jié)構(gòu)的散亂點(diǎn)集三角剖分并行算法研究及實(shí)現(xiàn)

摘 "要： 三角剖分算法在計(jì)算幾何中的地位非常重要，其中三角網(wǎng)格的剖分效率及質(zhì)量對(duì)后續(xù)研究有著重要的影響。對(duì)Delaunay三角剖分算法的基本原理進(jìn)行了分析，基于散亂點(diǎn)集研究了基于Quad?Edge結(jié)構(gòu)下的分治算法，并將目前流行的Map?Reduce并行編程模型引入到對(duì)散亂點(diǎn)集進(jìn)行基于Delaunay三角剖分中。實(shí)驗(yàn)結(jié)果表明基于Map?Reduce編程模型實(shí)現(xiàn)的三角剖分并行化在大數(shù)據(jù)量的情況下大大提高了剖分的效率，速度明顯高于基于Quad?Edge結(jié)構(gòu)實(shí)現(xiàn)的分治算法以及基于三角形索引的Bowyer?Watson三角剖分算法，并且具有很好的彈性計(jì)算能力，這對(duì)三角剖分的后續(xù)研究有重要的借鑒作用。

關(guān)鍵詞： Delaunay三角剖分算法; Quad?Edge; 并行算法; 三角網(wǎng)格

中圖分類號(hào)： TN911?34 " " " " " " " " " " " 文獻(xiàn)標(biāo)識(shí)碼： A " " " " " " " " " " " " " "文章編號(hào)： 1004?373X（2015）06?0028?03

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 "引 "言

有限元網(wǎng)格生成是工程科學(xué)與計(jì)算科學(xué)相交叉的重要研究領(lǐng)域，在計(jì)算機(jī)輔助設(shè)計(jì)、科學(xué)計(jì)算可視化、計(jì)算機(jī)圖形學(xué)、生物醫(yī)學(xué)和有限元分析等領(lǐng)域有著廣泛的應(yīng)用。網(wǎng)格剖分做為有限元計(jì)算的前置處理技術(shù)，其運(yùn)算的工作量在有限元計(jì)算分析過(guò)程中所占的比重非常大，此過(guò)程是否成功對(duì)后續(xù)的工作成果有重大的影響。本文中在保證網(wǎng)格質(zhì)量的情況下，實(shí)現(xiàn)了基于三角形索引的Bowyer?Watson[1]三角剖分算法、基于Quad?Edge[2]結(jié)構(gòu)下的三角剖分分治算法以及基于Map?Reduce[3?5]編程模型實(shí)現(xiàn)的三角剖分并行化并在大數(shù)據(jù)量的情況下進(jìn)行測(cè)試，結(jié)果表明基于Map?Reduce編程模型實(shí)現(xiàn)的三角剖分并行化效率明顯高于另外兩個(gè)并且具有很好的彈性計(jì)算能力。

1 "Delaunay三角剖分算法

在數(shù)值分析、圖形學(xué)以及有限元分析中，三角剖分都是極其重要的一項(xiàng)預(yù)處理技術(shù)。而Delaunay[6?7]三角剖分是運(yùn)用最多的三角剖分方法。其中Delaunay三角剖分必須符合兩個(gè)重要的準(zhǔn)則：第一，空外接圓特性，即在Delaunay三角網(wǎng)格中任意四個(gè)點(diǎn)不能共圓，同時(shí)任一三角形的外接圓范圍內(nèi)不能有其他的點(diǎn)存在;第二，最小內(nèi)角最大，即在散點(diǎn)集形成的三角剖分中，所形成的三角形的最小角最大。在兩個(gè)相鄰的三角形構(gòu)成凸四邊形的對(duì)角線中，在相互交換后，六個(gè)內(nèi)角的最小角不再增大。

2 "基于三角形邊索引Bowyer?Watson算法

基于逐點(diǎn)插入法[8]的Bowyer?Watson算法是基于Bowyer算法與Watson算法并在兩者的基礎(chǔ)之上進(jìn)行改進(jìn)而來(lái)的，因其簡(jiǎn)單易于實(shí)現(xiàn)而得到廣泛的應(yīng)用。此算法的思想是首先構(gòu)建包含所有散亂點(diǎn)集的超級(jí)大三角形，然后選擇其他未處理的離散點(diǎn)插入進(jìn)來(lái)，在已經(jīng)構(gòu)成的三角形中查找這些三角形的外接圓包含這個(gè)新加入的散亂點(diǎn)的三角形，并把這些三角形刪除掉，那么會(huì)形成一個(gè)包含這個(gè)新插入點(diǎn)的多邊形，然后把這個(gè)點(diǎn)與多邊形的各個(gè)頂點(diǎn)進(jìn)行連接，從而構(gòu)成多個(gè)新的三角形網(wǎng)格，重復(fù)這樣的處理直到所有的點(diǎn)都處理完為止。此算法的相當(dāng)大的時(shí)間損耗在了對(duì)空腔的查找，原始的算法要對(duì)形成的三角形進(jìn)行遍歷查找，而基于三角形邊索引的方式則大大減少了對(duì)待插入點(diǎn)進(jìn)行空腔查找的時(shí)間，此三角形邊索引的結(jié)構(gòu)如圖1所示。

lt;E：＼王芳＼現(xiàn)代電子技術(shù)201506＼現(xiàn)代電子技術(shù)15年38卷第6期＼Image＼45T1.tifgt;

圖1 三角形邊索引結(jié)構(gòu)

在對(duì)查找到的三角形進(jìn)行保存的時(shí)候同時(shí)保存三角形的三個(gè)鄰邊三角形。如圖1所示，在對(duì)Tri1的三角形進(jìn)行保存的時(shí)候同時(shí)保存其三個(gè)鄰邊三角形，保存其邊13的鄰邊三角形為T(mén)ri2，12邊的臨邊三角形為T(mén)ri4，23邊的鄰邊三角形為T(mén)ri3。這樣在進(jìn)行新點(diǎn)的插入尋找空腔時(shí)，只需要判斷插入點(diǎn)與三角形鏈表中第一個(gè)三角形的關(guān)系，判斷是在三角形內(nèi)還是在某條邊的一側(cè)，如果在某條邊的一側(cè)那么對(duì)該邊的鄰接三角形再進(jìn)行同樣判斷，如果在三角形內(nèi)，那么對(duì)該三角形的三個(gè)邊的鄰邊三角形依次判斷待插入點(diǎn)是否在這些三角形的外接圓內(nèi)，這樣就會(huì)形成一個(gè)包圍該點(diǎn)的空腔，將該插入點(diǎn)連接空腔的各個(gè)點(diǎn)形成新的三角形并做基于Delaunay優(yōu)化準(zhǔn)則的調(diào)整。

基于改進(jìn)后的Bowyer?Watson大大提高了對(duì)包圍待插入點(diǎn)的空腔的尋找速度，從而提高了三角網(wǎng)格剖分的速度。

3 "基于Map?Reduce實(shí)現(xiàn)的三角剖分并行化

3.1 "Quad?Edge結(jié)構(gòu)介紹

Quad?Edge結(jié)構(gòu)是由Guibas提出的一種處理點(diǎn)與Voronoi[9?10]圖關(guān)系的數(shù)據(jù)結(jié)構(gòu)，這種結(jié)構(gòu)保存了Delaunay邊與Voronoi邊的對(duì)偶關(guān)系，使得基于Delaunay的三角剖分操作也相對(duì)容易得多，這種結(jié)構(gòu)如圖2所示。

lt;E：＼王芳＼現(xiàn)代電子技術(shù)201506＼現(xiàn)代電子技術(shù)15年38卷第6期＼Image＼45T2.tifgt;

圖2 Quad?Edge結(jié)構(gòu)

在Quan?Edge結(jié)構(gòu)中邊next為以點(diǎn)origin為起點(diǎn)并且對(duì)與[e（0）]邊的下一個(gè)邊可以以逆時(shí)針?lè)较蛘业剑瑫r(shí)由于存儲(chǔ)了Voronoi圖的兩邊[e（1）]與[e（3）]，因此可以很容易從Delaunay三角網(wǎng)格圖轉(zhuǎn)換為Voronoi圖。在本程序中，主要是用來(lái)對(duì)Delaunay邊進(jìn)行求解，所有都是為了簡(jiǎn)化處理去除了對(duì)應(yīng)的Voronoi邊。

3.2 "Map?Reduce并行計(jì)算模型

Map?Reduce是一種目前在云計(jì)算平臺(tái)上廣泛使用的并行編程模型，主要用于對(duì)大規(guī)模數(shù)據(jù)集的并行計(jì)算，Map（映射）和Reduce（歸并）是他的主要思想。Map?Reduce主要是通過(guò)啟動(dòng)多個(gè)Task（任務(wù)），對(duì)不同的數(shù)據(jù)集進(jìn)行處理返回相應(yīng)Task的處理結(jié)果，然后對(duì)返回的結(jié)果集進(jìn)行Reduce處理，從而得到最終的結(jié)果。從上可以看出，通過(guò)啟動(dòng)不同的Task數(shù)量可以很輕松地實(shí)現(xiàn)并行計(jì)算能力的提升，具有很高的彈性計(jì)算能力。

3.3 "三角剖分算法基于Map?Reduce思想的實(shí)現(xiàn)

基于Map?Reduce并行編程思想的Delaunay三角剖分算法處理步驟如下：

第一步：輸入散亂點(diǎn)集的坐標(biāo)，記錄相應(yīng)點(diǎn)的坐標(biāo)并根據(jù)x值將散亂點(diǎn)基于快速排序算法進(jìn)行排序;

第二步：?jiǎn)?dòng)多個(gè)Task（任務(wù)）并對(duì)數(shù)據(jù)進(jìn)行分塊后分配給每個(gè)Task進(jìn)行處理，在每個(gè)子集進(jìn)行三角剖分的處理過(guò)程中使用Quad?Edge結(jié)構(gòu)存儲(chǔ)剖分的數(shù)據(jù)，對(duì)于剖分的子過(guò)程可以使用改進(jìn)后的Bowyer?Watson算法也可以使用分治算法[11]，此程序在實(shí)現(xiàn)時(shí)使用的分治算法，并返回相應(yīng)的剖分后的結(jié)果;

第三步：對(duì)返回的結(jié)果進(jìn)行Reduce操作。對(duì)數(shù)據(jù)集進(jìn)行合并時(shí)對(duì)于上下邊切線的查找使用Zig?Zag[2]算法，當(dāng)Reduce處理完成后返回結(jié)果即為三角剖分的網(wǎng)格。該程序通過(guò)基于Map?Reduce進(jìn)行處理的流程圖如圖3所示。

lt;E：＼王芳＼現(xiàn)代電子技術(shù)201506＼現(xiàn)代電子技術(shù)15年38卷第6期＼Image＼45T3.tifgt;

圖3 Map?Reduce網(wǎng)格剖分過(guò)程

該程序中使用的主要數(shù)據(jù)結(jié)構(gòu)及算法簡(jiǎn)介如下：

/*定義邊的關(guān)系，基于Quad?Edge進(jìn)行改進(jìn)，去除對(duì)應(yīng)的Voronoi邊關(guān)系*/

QuadEdge（void）

{

e[0].num = 0;

e[1].num = 1;

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

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

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

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

visited = 1;

}

//二維中點(diǎn)的x，y坐標(biāo)值

Point2d（double tx， double ty）

： x（tx）， y（ty）

{

}

//數(shù)據(jù)合并

delaunayMerge（MaxEdge retleft，MaxEdge retright）

{

//數(shù)據(jù)合并

MaxEdge rettemp; " " " " "http://臨時(shí)兩三角剖分結(jié)果相聯(lián)接

Edge *ldo， *ldi; " " " " " " " //包圍左邊剖分結(jié)果集的邊

Edge *rdo， *rdi; " " " " " //包圍右邊剖分結(jié)果集的邊

……

Return rettemp; " " " " " " " " " " "http://返回兩邊合并的結(jié)果集

}

4 "結(jié)果驗(yàn)證及分析

在本測(cè)試算法中采用C++分別對(duì)基于三角形索引的Bowyer?Watson三角剖分算法、基于Quad?Edge結(jié)構(gòu)下的三角剖分分治算法以及基于Map?Reduce編程模型實(shí)現(xiàn)的三角剖分并行化進(jìn)行實(shí)現(xiàn)。其中對(duì)Map?Reduce并行實(shí)現(xiàn)啟動(dòng)四個(gè)Task。通過(guò)隨機(jī)獲取散亂點(diǎn)集點(diǎn)數(shù)50～1 000 000個(gè)，分別通過(guò)以上三個(gè)程序進(jìn)行處理的結(jié)果如表1所示。

表1 算法針對(duì)目標(biāo)散亂點(diǎn)集的計(jì)算結(jié)果

通過(guò)表1看出，在對(duì)少量點(diǎn)集的運(yùn)算時(shí)由于改進(jìn)后的Bowyer?Watson算法處理完插點(diǎn)后要遍歷三角形鏈表，對(duì)含有初始構(gòu)建大三角形頂點(diǎn)的三角形進(jìn)行刪除操作，所以相對(duì)要慢些，同時(shí)由于Map?Reduce過(guò)程需要進(jìn)行任務(wù)拆分合并需要消耗時(shí)間，效果也不會(huì)好于基于Quad?Edge結(jié)構(gòu)的分治算法，但是當(dāng)點(diǎn)集數(shù)量非常大時(shí)，基于Map?Reduce編程模型實(shí)現(xiàn)的三角剖分并行化要明顯優(yōu)于其他兩個(gè)算法，在點(diǎn)數(shù)100萬(wàn)的時(shí)候速度是改進(jìn)后Bowyer?Watson算法效率的7倍，同時(shí)也要比Quad?Edge分治算法快得多，通過(guò)增加Task數(shù)量還可以進(jìn)一步提高剖分效率。

圖4是對(duì)含有1萬(wàn)個(gè)點(diǎn)的圓通過(guò)基于Map?Reduce編程模型實(shí)現(xiàn)的三角剖分并行化的剖分結(jié)果，從圖四可以看出剖分后的網(wǎng)格很好的符合了Delaunay三角剖分的優(yōu)化準(zhǔn)則。

lt;E：＼王芳＼現(xiàn)代電子技術(shù)201506＼現(xiàn)代電子技術(shù)15年38卷第6期＼Image＼45T4.tifgt;

圖4 基于Map?Reduce編程模型的剖分結(jié)果

5 "結(jié) "語(yǔ)

本文通過(guò)使用Quad?Edge結(jié)構(gòu)進(jìn)行剖分結(jié)果的存儲(chǔ)，并將Map?Reduce編程模型應(yīng)用到三角網(wǎng)格剖分中，通過(guò)與其他兩個(gè)方法對(duì)比證明此方法能夠很好地提高三角網(wǎng)格剖分的效率，同時(shí)由于此編程模型具有很好的彈性計(jì)算能力，可以很輕松地通過(guò)增加task數(shù)量來(lái)進(jìn)一步提高剖分的效率。如何將此并行編程模型應(yīng)用到三維散亂點(diǎn)集中進(jìn)行剖分處理，這將是要進(jìn)一步研究的問(wèn)題。

參考文獻(xiàn)

[1] REBAY S. Efficient unstructured mesh generation by means of Delaunay triangulation and Bowyer?Watson algorithm [J]. Journal of Computational Physics， 1993， 106（1）： 125?138.

[2] GUIBAS L， STOLFI J. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams [J]. ACM Transactions on Graphics， 1985， 4（2）： 75?123.

[3] YANG H， DASDAN A， HSIAO R L， et al. Map?reduce?merge： simplified relational data processing on large clusters[C]//Proceedings of the 2007 ACM SIGMOD international conference on Management of data. [S.l.]： ACM， 2007： 1029?1040.

[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.

[6] 武曉波，王世新，肖春生.Delaunay三角網(wǎng)的生成算法研究[J]. 測(cè)繪學(xué)報(bào)，1999，28（1）：28?35.

[7] 余杰，呂品，鄭昌文.Delaunay三角網(wǎng)構(gòu)建方法比較研究[J].中國(guó)圖象圖形學(xué)報(bào)，2010，15（8）：1158?1167.

[8] 劉云，夏興東，黃北生.基于分治算法與逐點(diǎn)插入法的Delaunay三角網(wǎng)建立算法的改進(jìn)[J].現(xiàn)代測(cè)繪，2010（4）：14?16.

[9] FORTUNE S. A sweepline algorithm for Voronoi diagrams [J]. Algorithmica， 1987， 2（1/4）： 153?174.

[10] HUANG Y， QIN H， WANG D， et al. Convergent adaptive finite element method based on centroidal Voronoi tessellations and super convergence [J]. Communications in Computational Physics， 2011， 10（2）： 339?370.

[11] 戴曉明，朱萍.平面散亂點(diǎn)三角剖分分治算法的實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2006，16（1）：11?12.