Delaunay三角剖分算法

1、Delaunay三角剖分算法點(diǎn)集的三角剖分（Triangulation），對數(shù)值分析（比如有限元分析）以及圖形學(xué)來說，都是極為重要的一項(xiàng)預(yù)處理技術(shù)。尤其是Delaunay三角剖分，由于其獨(dú)特性，關(guān)于點(diǎn)集的很多種幾何圖都和Delaunay三角剖分相關(guān)，如Voronoi圖，EMST樹，Gabriel圖等。Delaunay三角剖分有最大化最小角，“最接近于規(guī)則化的“的三角網(wǎng)和唯一性（任意四點(diǎn)不能共圓）兩個特點(diǎn)。定義編輯【定義】三角剖分1：假設(shè)V是二維實(shí)數(shù)域上的有限點(diǎn)集，邊e是由點(diǎn)集中的點(diǎn)作為端點(diǎn)構(gòu)成的封閉線段, E為e的集合。那么該點(diǎn)集V的一個三角剖分T=(V,E)是一個平面圖G，該平面圖滿足條件：

2、1.除了端點(diǎn)，平面圖中的邊不包含點(diǎn)集中的任何點(diǎn)。2.沒有相交邊。3.平面圖中所有的面都是三角面，且所有三角面的合集是散點(diǎn)集V的凸包。在實(shí)際中運(yùn)用的最多的三角剖分是Delaunay三角剖分，它是一種特殊的三角剖分。先從Delaunay邊說起：【定義】Delaunay邊：假設(shè)E中的一條邊e（兩個端點(diǎn)為a,b），e若滿足下列條件，則稱之為Delaunay邊：存在一個圓經(jīng)過a,b兩點(diǎn)，圓內(nèi)(注意是圓內(nèi)，圓上最多三點(diǎn)共圓)不含點(diǎn)集V中任何其他的點(diǎn)，這一特性又稱空圓特性。【定義】Delaunay三角剖分：如果點(diǎn)集V的一個三角剖分T只包含Delaunay邊，那么該三角剖分稱為Delaunay三角剖分。優(yōu)化處

3、理:理論上為了構(gòu)造Delaunay三角網(wǎng)2，Lawson提出的局部優(yōu)化過程LOP(Local Optimization Procedure)，一般三角網(wǎng)經(jīng)過LOP處理，即可確保成為Delaunay三角網(wǎng)，其基本做法如下所示：1.將兩個具有共同邊的三角形合成一個多邊形。2.以最大空圓準(zhǔn)則作檢查，看其第四個頂點(diǎn)是否在三角形的外接圓之內(nèi)。3.如果在，修正對角線即將對角線對調(diào)，即完成局部優(yōu)化過程的處理。LOP處理過程如下圖所示：Delaunay剖分的算法Delaunay剖分是一種三角剖分的標(biāo)準(zhǔn)，實(shí)現(xiàn)它有多種算法。準(zhǔn)則特性編輯準(zhǔn)則:要滿足Delaunay三角剖分的定義，必須符合兩個重要的準(zhǔn)則：1、空圓特

4、性：Delaunay三角網(wǎng)是唯一的（任意四點(diǎn)不能共圓），在Delaunay三角形網(wǎng)中任一三角形的外接圓范圍內(nèi)不會有其它點(diǎn)存在。如下圖所示：2、最大化最小角特性：在散點(diǎn)集可能形成的三角剖分中，Delaunay三角剖分所形成的三角形的最小角最大。從這個意義上講，Delaunay三角網(wǎng)是“最接近于規(guī)則化的“的三角網(wǎng)。具體的說是指在兩個相鄰的三角形構(gòu)成凸四邊形的對角線，在相互交換后，六個內(nèi)角的最小角不再增大。如下圖所示：特性:以下是Delaunay剖分所具備的優(yōu)異特性：1.最接近：以最近的三點(diǎn)形成三角形，且各線段(三角形的邊)皆不相交。2.唯一性：不論從區(qū)域何處開始構(gòu)建，最終都將得到一致的結(jié)果。3.最

5、優(yōu)性：任意兩個相鄰三角形形成的凸四邊形的對角線如果可以互換的話，那么兩個三角形六個內(nèi)角中最小的角度不會變大。4.最規(guī)則：如果將三角網(wǎng)中的每個三角形的最小角進(jìn)行升序排列，則Delaunay三角網(wǎng)的排列得到的數(shù)值最大。5.區(qū)域性：新增、刪除、移動某一個頂點(diǎn)時只會影響臨近的三角形。6.具有凸多邊形的外殼：三角網(wǎng)最外層的邊界形成一個凸多邊形的外殼。計算方法編輯a)Lawson算法逐點(diǎn)插入的Lawson算法3是Lawson在1977年提出的，該算法思路簡單，易于編程實(shí)現(xiàn)。基本原理為：首先建立一個大的三角形或多邊形，把所有數(shù)據(jù)點(diǎn)包圍起來，向其中插入一點(diǎn)，該點(diǎn)與包含它的三角形三個頂點(diǎn)相連，形成三個新的三角形

6、，然后逐個對它們進(jìn)行空外接圓檢測，同時用Lawson設(shè)計的局部優(yōu)化過程LOP進(jìn)行優(yōu)化，即通過交換對角線的方法來保證所形成的三角網(wǎng)為Delaunay三角網(wǎng)。上述基于散點(diǎn)的構(gòu)網(wǎng)算法理論嚴(yán)密、唯一性好，網(wǎng)格滿足空圓特性，較為理想。由其逐點(diǎn)插入的構(gòu)網(wǎng)過程可知，遇到非Delaunay邊時，通過刪除調(diào)整，可以構(gòu)造形成新的Delaunay邊。在完成構(gòu)網(wǎng)后，增加新點(diǎn)時，無需對所有的點(diǎn)進(jìn)行重新構(gòu)網(wǎng)，只需對新點(diǎn)的影響三角形范圍進(jìn)行局部聯(lián)網(wǎng)，且局部聯(lián)網(wǎng)的方法簡單易行。同樣，點(diǎn)的刪除、移動也可快速動態(tài)地進(jìn)行。但在實(shí)際應(yīng)用當(dāng)中，這種構(gòu)網(wǎng)算法當(dāng)點(diǎn)集較大時構(gòu)網(wǎng)速度也較慢，如果點(diǎn)集范圍是非凸區(qū)域或者存在內(nèi)環(huán)，則會產(chǎn)生非法三角形。如左圖所示：當(dāng)離散點(diǎn)集構(gòu)成圓環(huán)時，Lawson算法產(chǎn)生的非法三角形離散點(diǎn)集合Lawson算法產(chǎn)生的三角剖分正確的三角剖分b)Bowyer-Watson算法(推薦)Watson算法的基本步驟是：1、構(gòu)造一個超級三角形，包含所有散點(diǎn)，放入三角形鏈表。2、將點(diǎn)集中的散點(diǎn)依次插入，在三角形鏈表中找出外接圓包含插入點(diǎn)的三角形（稱為該點(diǎn)的影響三角形），刪除影響三角形的公共邊，將插入點(diǎn)同影響三角形的全部頂點(diǎn)連接起來，完成一個點(diǎn)在