delaunay演算法

❶ 點集的Delaunay三角剖分方法

3.2.1.1 基本理論

B.Delaunay於1934年提出了Delaunay三角網格的概念，它是Voronoi圖(簡稱V圖)的幾何對偶圖，具有嚴格的數學定義和完備的理論基礎。

圖3.1 Voronoi圖(虛線)及對應的Delaunay三角剖分(實線)

3.2.1.1.1 Voronoi圖

假設V={v₁，v₂，…，v_N}，N≥3是歐幾里得平面上的一個點集，並且這些點不共線，四點不共圓。用d(v_i，v_j)表示點v_i與v_j間的歐幾里得距離。

設x為平面上的點，則:

區域V_(i)={x∈E²d(x，v_i)≤d(x，v_j)，j=1，2，…，N，j≠i}稱為Voronoi多邊形，也稱為該點的鄰域。點集中所有點的Voronoi多邊形組成Voronoi圖，如圖3.1所示。

平面上的Voronoi圖可以看做是點集V中的每個點作為生長核，以相同的速率向外擴張，直到彼此相遇為止而在平面上形成的圖形。除最外層的點形成開放的區域外，其餘每個點都形成一個凸多邊形。

3.2.1.1.2 Delaunay三角剖分

Delaunay三角形網格為V圖的幾何對偶圖。在二維平面中，點集中若無四點共圓，則該點集V圖中每個頂點恰好是3個邊的公共頂點，並且是3個Voronoi多邊形的公共頂點;上述3個Voronoi多邊形所對應的點集中的點連成的三角形稱為與該Voronoi頂點對應的Delaunay三角形，如圖3.1所示。如果一個二維點集中有四點共圓的情況，此時，這些點對應的Voronoi多邊形共用一個Voronoi頂點，這個公共的Voronoi頂點對應多於3個Voronoi多邊形，也就是對應於點集中多於3個的點;這些點可以連成多於一個的三角形。此時，可以任意將上述幾個點形成的凸包劃分為若干三角形，這些三角形也稱為和這個Voronoi頂點對應的Delaunay三角形。

所有與Voronoi頂點對應的Delaunay三角形就構成了Delaunay三角剖分。當無退化情況(四點共圓)出現時，點集的Delaunay三角剖分是唯一的。

3.2.1.1.3 Delaunay三角剖分的特性

Delaunay三角剖分具有兩個重要特性:

(1)最小角最大化特性:即要求三角形的最小內角盡量最大，具體地說是指在兩個相鄰的三角形構成凸四邊形的對角線，在相互交換後，6個內角的最小角不再增大，並且使三角形盡量接近等邊。

(2)空外接圓特性:即三角形的外接圓中不包含其他三角形的頂點(任意四點不能共圓)，該特性保證了最鄰近的點構成三角形，使三角形的邊長之和盡量最小。

3.2.1.2 常用演算法

Delaunay三角剖分方法是目前最流行的通用的全自動網格生成方法之一。比較有效的Delaunay三角剖分演算法有分治演算法、逐點插入法和三角網生長法等(Tsai，1993)，其中逐點插入法由於其演算法的簡潔性且易於實現，因而獲得廣泛的應用。其主要思路是先構建一個包含點集或區域的初始網格，再依次向初始網格中插入點，最後形成Delaunay三角剖分。

採用逐點插入法建立Delaunay三角網的演算法思想最初是由Lawson於1977年提出的(Lawson，1977)，Bowyer和Watson等先後對該演算法進行了發展和完善(Bowyer，1981;Watson，1981)。目前涌現出的大量逐點插入法中，主要為以Lawson演算法代表的對角線交換演算法和以Bowyer-Watson演算法代表的空外接圓法。

3.2.1.2.1 Lawson演算法

Lawson演算法的主要思想是將要插入的數據點逐一插入到一個已存在的Delaunay三角網內，然後再用局部優化演算法(Local Optimization Procere，LOP)優化使其滿足Delau-nay三角網的要求，其主要步驟如下:

圖3.7 Bowyer-Watson演算法剖分實例

❷ Delaunay細分

地質特徵具有結構性(局部連續性)，而實際地質采樣具有不規則性和稀疏性，使得由鑽孔孔口坐標點所剖分的初始三角網格可能存在畸形和尺寸過大的情況，可視化效果差，也不能真實地反映地層的分布特徵。因此，需要對初始三角網格進行細分，以消除這些影響。

網格細分要求進行質量控制和尺度控制(楊欽，2005)。質量控制方法是在畸形網格單元頂點附近加點的方法來實現。加點細化後網格保持了Delaunay三角化的一些優良特性，且向一個符合Delaunay優化准則的網格中加入一個點是一個局部運算，演算法效率更高。主要採用兩種加點方法：①畸形網格單元的最長邊中點加點；②畸形網格單元的外接圓圓心加點。通常，第二種方法優於第一種方法。

為了使網格具有一定的密度，對於尺寸超過標準的網格單元應該進行加點細分。加點方案同質量控制一樣。

因此，無論是對三角網進行質量控制還是尺寸控制，均選擇三角單元外接圓圓心作為點插入的位置。同時，需要建立評價點插入的收斂准則：

(1)用三角形單元的外接圓半徑與內切圓半徑的比值來度量網格單元的質量，稱為三角形單元的縱橫比(aspect ratio)；

(2)用三角單元的外接圓半徑與最短邊長度的比值來度量網格單元的質量，建成為Radius-Edge比。用ρ來表示三角單元T的Radius-Edge比，R表示T的外接圓半徑，L_min表示T的最短邊長度，有：

數字地下空間與工程三維地質建模及應用研究

由於三角形的內切圓半徑的計算比較煩瑣，通常採用第二種方法作為三角形的質量評價標准。採用三角形的Radius-Edge比作為質量評價的另一個好處是根據三角形T的Radius-Edge比ρ(T)可以直接計算三角形最小角的角度，如圖3.9所示。

圖3.9 三角形的Radius-Edge比和最小角度的關系

由圖3.9中的幾何關系可以得到：

數字地下空間與工程三維地質建模及應用研究

不難看出，ρ(T)具有明顯幾何意義：

ρ(T)越大，T的最小角度也越小，T就越畸形。

ρ(T)越小，T的最小角度也越大，T就越接近正三角形。

當T是正三角形時，ρ(T)達到最小，其值為

，網格質量最好。

通過設置不同的網格質量和尺寸的控制性參數，可以得到不同的網格質量和密度的網格剖分結果，從而可以實現模型的精度控制。圖3.10是以中國主要陸地區域作為約束邊界，一些控制點作為約束點，在一定質量和尺寸控制下的三角剖分，剖分結果為非常均勻的三角網格。該方法用於鑽孔加密，可以實現鑽孔(包括虛擬鑽孔)的相對均勻分布，進而可以了解各個位置處的地層分布。

❸ 　Delaunay剖分及其性質

在二維情況下的三角網格和在三維情況下的四面體網格，具有很強的表示模型的能力。Delaunay剖分是二維Delaunay三角形化和三維Delaunay四面體化的總稱。在二維情況下，指的是將一些隨機散亂的點，連成三角形網，並給出每個三角形的相鄰信息。首先，需要定義一個數據結構，使得三角形的組成及其相鄰關系均可以用這個數據結構表示出來。

在二維情況下，這個數據結構通常用一個n×6維的矩陣表示出來。如圖2.1（b）是一個三角形網，圖2.1（c）是其三角形構成和相鄰關系。這個矩陣的頭三列為三角形結點的編號，後三列為相鄰三角形的編號。

圖2.1二維Delaunay剖分數據結構

（a）Dirichlet多邊形；（b）Delaunay三角形化；（c）數據結構

如圖，1號三角形是由15、5、4號點組成，其中15號點對邊的相鄰三角形編號4,5號點對邊的三角形編號為2,4號點對邊的三角形編號為0（指外邊）。可見，當三角形的三個頂點的順序在數據結構中確定下來以後，其相鄰三角形編號的順序和在數據結構中的位置也就確定下來了。在下面的所有Delaunay剖分演算法，均是針對這一數據結構進行的。

給定一系列離散點坐標，所形成的三角形網並不是惟一的。目前應用最廣泛的是Delaunay三角形化方法。

Delaunay三角形的定義應從Dirichlet多邊形說起。在每個網格點附近劃出一個鄰域；鄰域內的任一點到該網格點的距離小於到其他網格點的距離。這個鄰域多邊形稱為Dirichlet多邊形（圖2.1（a）。將每個多邊形內的格點與相鄰的多邊形的網格點連接起來，構成一個三角形，稱為Delaunay三角形（圖2.1（b））。Delaunay三角形具有一種性質，它可以盡可能的避免形成過瘦的三角形，因而在有限元計算中非常有用，因為有限元法的穩定性是由所有三角形的最小內角確定的。過瘦的三角形不利於射線追蹤，因為它使得射線追蹤經過的交點過多，從而會增加積累誤差，增大計算量。Delaunay三角形的三角形數目大約為點的兩倍。在三維情況下，Delaunay四面體的數目大約為點的7倍。文獻（閔衛東、唐澤聖，1993）曾給出大量Delaunay三角形和四面體的點線、面的數量關系。

❹ Delaunay三角剖分演算法的准則特性

准則:
要滿足Delaunay三角剖分的定義，必須符合兩個重要的准則：
1、空圓特性：Delaunay三角網是唯一的（任意四點不能共圓），在Delaunay三角形網中任一三角形的外接圓范圍內不會有其它點存在。如下圖所示：
2、最大化最小角特性：在散點集可能形成的三角剖分中，Delaunay三角剖分所形成的三角形的最小角最大。從這個意義上講，Delaunay三角網是「最接近於規則化的「的三角網。具體的說是指在兩個相鄰的三角形構成凸四邊形的對角線，在相互交換後，六個內角的最小角不再增大。如下圖所示：

特性:
以下是Delaunay剖分所具備的優異特性：
1.最接近：以最近的三點形成三角形，且各線段(三角形的邊)皆不相交。
2.唯一性：不論從區域何處開始構建，最終都將得到一致的結果。
3.最優性：任意兩個相鄰三角形形成的凸四邊形的對角線如果可以互換的話，那麼兩個三角形六個內角中最小的角度不會變大。
4.最規則：如果將三角網中的每個三角形的最小角進行升序排列，則Delaunay三角網的排列得到的數值最大。
5.區域性：新增、刪除、移動某一個頂點時只會影響臨近的三角形。
6.具有凸多邊形的外殼：三角網最外層的邊界形成一個凸多邊形的外殼。

❺ 　三維Delaunay演算法

將Delaunay剖分演算法推廣到三維具有重要意義。三維Delaunay剖分構成的Delaunay四面體是進一步構成任意塊體的中間工具。三維空間的四面體對於三維射線追蹤非常方便。三維Delaunay演算法基本原理與二維Delaunay演算法十分相似，但編制起來更為復雜。它也要用一個n×8維數組記錄四面體構成點和相鄰四面體信息，它大致也分為以下幾步：

（1）判斷哪些四面體的外接球包含新加入的點；

（2）將這些四面體匯總到一塊，形成一個凸多面體；

（3）找到這多面體外表面，用一個二維三角形相鄰關系數組記錄下來；

（4）由多面體表面的三角形與新加入的點構制新四面體，用一個三維四面體數據結構數組，存貯新形成的四面體信息；

（5）用新四面體信息去更新原來總的四面體數據結構信息。

其中第（3）步是比二維Delaunay剖分復雜。待修改的四面體的外表面不再能夠用環表示，而要用一個二維Delaunay三角形數據結構來表示。這種三角形的相鄰關系要從原四面體的數據結構關系中去尋找。A、C面是多面體的外表面。B是其內表面須尋找A的一個棱的相鄰三角形B，從B找到下一個四面體，再從四面體上找到與B三角形棱相鄰的面C。

在三維Delaunay演算法中，在通過外接球找到所有待修改的四面體後，將其排成一個待修改四面體數據結構數組，將待修改四面體的所有面全部排列起來，其中包含各個四面體的相互公共面和這些四面體組成的多面體的外表面，構成一個關於面的數據結構數組。從這個數據結構中刪去相互相鄰的三角形面，這樣就構成了外表面的數據結構數組。

三維Delaunay剖分時，我們總利用三角形網格中的數量關系，來檢查所形成的四面體的正確性。如果待刪四面體數目為T，外表面三角形的數目為F，則

地質模型計算機輔助設計原理與應用

❻ Delaunay三角剖分演算法的定義

【定義】三角剖分 ：假設V是二維實數域上的有限點集，邊e是由點集中的點作為端點構成的封閉線段, E為e的集合。那麼該點集V的一個三角剖分T=(V,E)是一個平面圖G，該平面圖滿足條件：
1.除了端點，平面圖中的邊不包含點集中的任何點。
2.沒有相交邊。
3.平面圖中所有的面都是三角面，且所有三角面的合集是散點集V的凸包。
在實際中運用的最多的三角剖分是Delaunay三角剖分，它是一種特殊的三角剖分。先從Delaunay邊說起：
【定義】Delaunay邊：假設E中的一條邊e（兩個端點為a,b），e若滿足下列條件，則稱之為Delaunay邊：存在一個圓經過a,b兩點，圓內(注意是圓內，圓上最多三點共圓)不含點集V中任何其他的點，這一特性又稱空圓特性。
【定義】Delaunay三角剖分：如果點集V的一個三角剖分T只包含Delaunay邊，那麼該三角剖分稱為Delaunay三角剖分。
優化處理:
理論上為了構造Delaunay三角網 ，Lawson提出的局部優化過程LOP(Local Optimization Procere)，一般三角網經過LOP處理，即可確保成為Delaunay三角網，其基本做法如下所示：
1.將兩個具有共同邊的三角形合成一個多邊形。
2.以最大空圓准則作檢查，看其第四個頂點是否在三角形的外接圓之內。
3.如果在，修正對角線即將對角線對調，即完成局部優化過程的處理。
LOP處理過程如下圖所示：
Delaunay剖分的演算法
Delaunay剖分是一種三角剖分的標准，實現它有多種演算法。

❼ 帶許可權定Delaunay三角化的演算法步驟及實現

1.二維的演算法步驟及實現

帶權的限定Delaunay三角剖分（Weighted CDT）的演算法的輸入是一個包含限定線段和限定點的平面直線圖（planar straight line graph，簡稱PSLG），演算法的輸出是與限定條件（限定點和限定線段）一致的一個三角形集合。

演算法4.7二維的帶許可權定Delaunay三角剖分

（PSLG）

{

規范化演算法

調用演算法WeightAssignment2d對PSLG中的點賦權值

建立初始大三角形

調用二維帶權Delaunay空洞演算法（演算法4.2）生成受限點集的帶權Delaunay三角剖分；

調用二維恢復受限邊的演算法（演算法4.5）生成邊界一致的帶權Delaunay三角網格

刪除邊界外的多餘的三角形，得到邊界一致的帶許可權定Delaunay三角剖分

}

2.三維的演算法步驟及實現

加權的限定Delaunay剖分的演算法步驟：

輸入：一個分段線性復合形（a piecewise linear complex）

輸出：滿足受限條件的具有帶權Delaunay性質的四面體集合

演算法三維的帶許可權定Delaunay四面體剖分演算法：

（PLC）

{

調用演算法4.4 WeightAssignment3d對規范化後的點和邊賦權值；

建立初始大四面體

for所有的PLC中的平面

將該平面通過坐標變換轉換到XOY平面上；

調用演算法進行二維的帶許可權定Delaunay三角剖分

將得到的二維帶許可權定Delaunay三角網格坐標變換到空間中其原來位置

endfor

調用演算法三維帶權Delaunay空洞演算法生成三維點集的帶權Delaunay四面體剖分

調用演算法RecoverConformSegments和演算法RecoverConformFacets恢復受限邊和受限面

刪除邊界外的多餘的四面體，得到邊界一致的帶許可權定Delaunay四面體剖分

}

❽ 　快速Delaunay剖分

在Delaunay剖分演算法中，2.2、2.3中（3）—（5）的計算量是一定的。而第一步，即找到所有待改三角形或四面體的過程，要消耗大量時間。為了使Delaunay剖分適應於快速人機交互處理，必須對其進一步優化。目前對三角形搜索的加速方法主要包含兩種方法。

（1）定向搜索方法

在已形成的三角形數據結構中搜索需要N/2次搜索，但如果考慮定向搜索，則可以將搜索次數降到N^0.5（N為已形成三角形的數目）。方法如下。

判斷新加入的點與三角形（圖2.2中V₁）三邊構成的面積，如果三個面積均為正，則加入點在三角形內，如果有至少一個為負（圖2.2中P₃—P₂邊），則該點位於為負的邊的外側。因此，可以進一步檢查該邊之相鄰三角形（圖2.2中V₂）。由此下去總能找到包含此新加入點的三角形。從這個包含新加入點的三角形出發，通過其相鄰三角形搜索，便可以找到所有待修改的三角形。

圖2.2定向搜索包含新加入點P之三角形

（2）樹狀存儲法

在Delaunay剖分中，如果將所有以前的剖分結果記錄下來，則可以找到一個樹形結構，使每個三角形被新的三角形細分後，該三角形的信息仍能記錄下來。這樣就可以由一個初始的大三角形出發，每次只查找其內所含的三角形，三角形的面積迅速縮小，最後找到所屬的小三角形，從而大大減少搜索時間。這種從大三角形到小三角形的搜索方法，計算量可以小於lgN，其代價是存貯量加大。

❾ 　Delaunay剖分的Bowyer演算法

在實際計算中Delaunay剖分通常採用如下定義：在形成的每個三角形的外接圓內都不包含網格點。

據此，Lawson和Bowyer提出的Delaunay三角形化演算法，是通過不斷地增加網格點迭代計算的。演算法分為如下幾點：

（1）判斷新加入的格點與三角形外接圓的內外關系，如果在某三角形外接圓內，則這個三角形需要改造。

（2）將所有需要改造的三角形集中起來，把它們的相鄰邊去掉，構成一個凸的多邊形。

（3）找到這個多邊形的外邊界，並利用它們的相鄰關系把它們連接起來構成一個頭尾相接的環。

（4）將環上的每兩個相鄰的網格點取出，與待加入的網格點構造三角形，計算其外心，並將相鄰三角形的信息建立起來，將三角形網格點和相鄰三角形信息儲貯在只包含這些三角形的Delaunay剖分的數據結構數組中。

（5）將上述新加入的三角形數據結構數組替換三角形數據結構數組中需要改造的三角形，並對三角形重新編號，從而得到新的結構數組。

❿ 空間點集的帶權Delaunay三角化演算法

構造點集的Delaunay三角化的著名增量演算法有兩種：一種稱為局部變換法（也稱為Flip-ping演算法），另外一種稱為Bowyer/Watson演算法。構造空間點集的帶權Delaunay三角化演算法也主要有兩種，分別是以上兩種演算法的推廣。我們只介紹推廣後的Bowyer/Watson演算法，稱之為「帶權Delaunay空洞演算法構造點集的帶權Delaunay三角化」演算法。

1.帶權Delaunay空洞定義

給定Ed空間的點集S，設有一點p∉S位於點集S的凸包中。Δ=ΔT是點集S的帶權Delaunay三角化中的任意一個單純形，z=z（Δ）為Δ的正交中心。如果滿足wp＞πz（p），則稱為Δ和p點沖突（也可以將單純形的正交中心理解為權為正交球半徑平方的帶權點，當該點與p點干涉時，單純形和p點沖突）。在帶權Delaunay三角化的結果中，將所有與p點沖突的單純形從帶權Delaunay三角化中刪除，將形成一個空洞，稱為帶權Delaunay空洞，又稱為Regular空洞（Regular Cavity）。

根據d維空間的帶權Delaunay三角化與d+1維空間的凸包之間的關系，可以在d+1維空間的凸包CH（S+）上考察將p點加入帶權Delaunay三角化中帶權Delaunay空洞的形成過程：如果Δ=ΔT和p點沖突，意味著p+點在過ΔT+=CH（T+）的超平面的下方。在帶權Delaunay三角化中，刪除CH（S+）的所有p+在其下方的下部小面對應的單純形，形成帶權Delaunay空洞。

2.帶權Delaunay空洞構造演算法

帶權Delaunay空洞構造演算法的思路如下：帶權Delaunay空洞構造演算法是一種增量演算法，S中的點是逐點加入、逐點處理的。與局部變換演算法一樣，需要選擇一個初始的足夠大的d-單純形。設點集S={p1，p2，…，pn}，選擇d+1的權為0的點構成點集S0={p-d，p-d+l，…，p0}，構造一個d-單純形ΔS0=CH（S0）。選擇的S0要保證ΔS0包含S中所有的點，並且保證WD（S）的每個d-單純形是WD（S ∪ S0）的d-單純形。

定義Si={p-d，p-d+1，…，pi}。給定R（Si-1），設Δ=ΔT是WD（Si-1）中包含pi點的d-單純形。如果加入pi後，Δ仍然是正則的，則WD（Si）=WD（Si-1）。否則，刪除Δ，並且根據鄰接關系，刪除Δ周圍所有與pi沖突的d-單純形，得到pi點的帶權Delaunay空洞，並且將空洞多面體的每個小面的頂點和pi相連形成新的d-單純形，從而得到WD（Si）。當點集S中所有的點處理完成後，將得到WD（S）。

演算法：帶權Delaunay空洞構造演算法

{

1 構造WD（S0）=ΔS0

2 for i：=1 to n do

3 在WD（Si-1）中找到包含pi點的d-單純形Δ

4 if WD（T ∪{pi}）≠ΔT then

刪除Δ，並且根據鄰接關系，刪除Δ周圍所有與pi沖突的d-單純形，得到pi點的帶權D elaunay空洞

6 while pi點的帶權Delaunay空洞中存在未處理的小面do

7 得到一個未處理的小面，設其所有頂點組成的集合為U，生成新的d-單純形ΔU ∪{pi}，在點集Si中是正則的，也就是說Δ屬於W D（Si）設置新生成的d-單純形之間的鄰接關系，以及新的

地下水三維可視化系統開發與應用