基于Quad?Edge結構的散亂點集三角剖分并行算法研究及實現

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

關鍵詞： Delaunay三角剖分算法; Quad?Edge; 并行算法; 三角網格

中圖分類號： TN911?34 " " " " " " " " " " " 文獻標識碼： 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 "引 "言

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

1 "Delaunay三角剖分算法

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

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

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

lt;E：＼王芳＼現代電子技術201506＼現代電子技術15年38卷第6期＼Image＼45T1.tifgt;

圖1 三角形邊索引結構

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

基于改進后的Bowyer?Watson大大提高了對包圍待插入點的空腔的尋找速度，從而提高了三角網格剖分的速度。

3 "基于Map?Reduce實現的三角剖分并行化

3.1 "Quad?Edge結構介紹

Quad?Edge結構是由Guibas提出的一種處理點與Voronoi[9?10]圖關系的數據結構，這種結構保存了Delaunay邊與Voronoi邊的對偶關系，使得基于Delaunay的三角剖分操作也相對容易得多，這種結構如圖2所示。

lt;E：＼王芳＼現代電子技術201506＼現代電子技術15年38卷第6期＼Image＼45T2.tifgt;

圖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所示。

lt;E：＼王芳＼現代電子技術201506＼現代電子技術15年38卷第6期＼Image＼45T3.tifgt;

圖3 Map?Reduce網格剖分過程

該程序中使用的主要數據結構及算法簡介如下：

/*定義邊的關系，基于Quad?Edge進行改進，去除對應的Voronoi邊關系*/

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;

}

//二維中點的x，y坐標值

Point2d（double tx， double ty）

： x（tx）， y（ty）

{

}

//數據合并

delaunayMerge（MaxEdge retleft，MaxEdge retright）

{

//數據合并

MaxEdge rettemp; " " " " "http://臨時兩三角剖分結果相聯接

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

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

……

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

}

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三角剖分的優化準則。

lt;E：＼王芳＼現代電子技術201506＼現代電子技術15年38卷第6期＼Image＼45T4.tifgt;

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

5 "結 "語

本文通過使用Quad?Edge結構進行剖分結果的存儲，并將Map?Reduce編程模型應用到三角網格剖分中，通過與其他兩個方法對比證明此方法能夠很好地提高三角網格剖分的效率，同時由于此編程模型具有很好的彈性計算能力，可以很輕松地通過增加task數量來進一步提高剖分的效率。如何將此并行編程模型應用到三維散亂點集中進行剖分處理，這將是要進一步研究的問題。

參考文獻

[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三角網的生成算法研究[J]. 測繪學報，1999，28（1）：28?35.

[7] 余杰，呂品，鄭昌文.Delaunay三角網構建方法比較研究[J].中國圖象圖形學報，2010，15（8）：1158?1167.

[8] 劉云，夏興東，黃北生.基于分治算法與逐點插入法的Delaunay三角網建立算法的改進[J].現代測繪，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] 戴曉明，朱萍.平面散亂點三角剖分分治算法的實現[J].計算機技術與發展，2006，16（1）：11?12.