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

摘 "要： 三角剖分算法在計(jì)算幾何中的地位非常重要，其中三角網(wǎng)格的剖分效率及質(zhì)量對后續(xù)研究有著重要的影響。對Delaunay三角剖分算法的基本原理進(jìn)行了分析，基于散亂點(diǎn)集研究了基于Quad?Edge結(jié)構(gòu)下的分治算法，并將目前流行的Map?Reduce并行編程模型引入到對散亂點(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ì)算能力，這對三角剖分的后續(xù)研究有重要的借鑒作用。

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

中圖分類號： TN911?34 " " " " " " " " " " " 文獻(xiàn)標(biāo)識碼： A " " " " " " " " " " " " " "文章編號： 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ì)算分析過程中所占的比重非常大，此過程是否成功對后續(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)行測試，結(jié)果表明基于Map?Reduce編程模型實(shí)現(xiàn)的三角剖分并行化效率明顯高于另外兩個并且具有很好的彈性計(jì)算能力。

1 "Delaunay三角剖分算法

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

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

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

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

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

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

基于改進(jìn)后的Bowyer?Watson大大提高了對包圍待插入點(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邊的對偶關(guān)系，使得基于Delaunay的三角剖分操作也相對容易得多，這種結(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)并且對與[e（0）]邊的下一個邊可以以逆時針方向找到，同時由于存儲了Voronoi圖的兩邊[e（1）]與[e（3）]，因此可以很容易從Delaunay三角網(wǎng)格圖轉(zhuǎn)換為Voronoi圖。在本程序中，主要是用來對Delaunay邊進(jìn)行求解，所有都是為了簡化處理去除了對應(yīng)的Voronoi邊。

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

Map?Reduce是一種目前在云計(jì)算平臺上廣泛使用的并行編程模型，主要用于對大規(guī)模數(shù)據(jù)集的并行計(jì)算，Map（映射）和Reduce（歸并）是他的主要思想。Map?Reduce主要是通過啟動多個Task（任務(wù)），對不同的數(shù)據(jù)集進(jìn)行處理返回相應(yīng)Task的處理結(jié)果，然后對返回的結(jié)果集進(jìn)行Reduce處理，從而得到最終的結(jié)果。從上可以看出，通過啟動不同的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)行排序;

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

第三步：對返回的結(jié)果進(jìn)行Reduce操作。對數(shù)據(jù)集進(jìn)行合并時對于上下邊切線的查找使用Zig?Zag[2]算法，當(dāng)Reduce處理完成后返回結(jié)果即為三角剖分的網(wǎng)格。該程序通過基于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)格剖分過程

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

/*定義邊的關(guān)系，基于Quad?Edge進(jìn)行改進(jìn)，去除對應(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://臨時兩三角剖分結(jié)果相聯(lián)接

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

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

……

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

}

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

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

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

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

圖4是對含有1萬個點(diǎn)的圓通過基于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é) "語

本文通過使用Quad?Edge結(jié)構(gòu)進(jìn)行剖分結(jié)果的存儲，并將Map?Reduce編程模型應(yīng)用到三角網(wǎng)格剖分中，通過與其他兩個方法對比證明此方法能夠很好地提高三角網(wǎng)格剖分的效率，同時由于此編程模型具有很好的彈性計(jì)算能力，可以很輕松地通過增加task數(shù)量來進(jìn)一步提高剖分的效率。如何將此并行編程模型應(yīng)用到三維散亂點(diǎn)集中進(jìn)行剖分處理，這將是要進(jì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]. 測繪學(xué)報(bào)，1999，28（1）：28?35.

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

[8] 劉云，夏興東，黃北生.基于分治算法與逐點(diǎn)插入法的Delaunay三角網(wǎng)建立算法的改進(jìn)[J].現(xiàn)代測繪，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.