3.2.1.1 基本理論
B.Delaunay於1934年提出了Delaunay三角網格的概念，它是Voronoi圖(簡稱V圖)的幾何對偶圖，具有嚴格的數學定義和完備的理論基礎。
圖3.1 Voronoi圖(虛線)及對應的Delaunay三角剖分(實線)
3.2.1.1.1 Voronoi圖
假設V={v1，v2，…，vN}，N≥3是歐幾裏得平面上的壹個點集，並且這些點不***線，四點不***圓。用d(vi，vj)表示點vi與vj間的歐幾裏得距離。
設x為平面上的點，則:
區域V(i)={x∈E2d(x，vi)≤d(x，vj)，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 Procedure，LOP)優化使其滿足Delau-nay三角網的要求，其主要步驟如下:
圖3.2 包含點集的三角形
第壹步:構建壹個三角形或多個三角形(通常情況下為壹個三角形，該三角形也稱超級三角形)，使點集中所有點都落在該三角形內，如圖3.2所示。另外，也可以用壹個矩形包圍所有點，再將矩形對角線相連生成壹對三角形作為初始網格。
第二步:將包含點集的三角形作為第壹個三角形單元加入初始三角形網格中。
第三步:依次插入壹個點P，並在三角網中找出包含P的三角形T，此時存在3種情況:
(1)P在三角形T內部，即P不落在三角形T的邊或頂點上，把P與T的3個頂點相連，生成3個新的三角形，將新生成的三角形加入三角網，刪除三角形T，如圖3.3(a)所示。
(2)P在三角形T的壹條邊上，但不在頂點上，把P與T的3個頂點中與P相對的頂點相連，生成兩個新的三角形，將新生成的三角形加入三角網，刪除三角形T，如圖3.4(b)所示。
(3)P在三角形T頂點上，不需處理，進行下壹步操作。實際上，若點集中不存在相互重合的點，則P落在三角形T頂點上這種情況不會發生。
圖3.3 向三角形網格中插入點P
上壹步處理中，直接將三角形的頂點與P相連生成新的三角形單元不壹定滿足Delau-nay三角剖分的要求，因此，需要采用LOP算法對局部三角形進行優化。該算法的主要操作是進行邊交換使新生成的三角形單元及其相鄰的單元滿足空外接圓特性。這樣壹個重要的過程其實非常簡單，它就是運用Delaunay三角剖分的空外接圓特性對由兩個有***用邊的三角形組成的四邊形進行判斷，如果其中壹個三角形的外接圓包含第四個頂點，則將這個四邊形的對角線交換，如圖3.4所示，在交換對角線後兩個新三角形都滿足空外接圓特性。
當兩個有***用邊的三角形具有相同的外接圓時，即存在四點***圓情況，此時，按照空外接圓特性，可以交換對角線也可以不交換對角線，那麽這時候就要按照最小角最大化特性進行處理。具體做法是，先計算不進行邊交換前三角形對中的6個內角的最小值，再計算進行邊交換後6個內角的最小值，判斷邊交換前、後最小角是否變大，若是，交換，否則，不交換。上述操作就是為了盡量滿足最小角最大化特性。
圖3.4 四點不***圓時的邊交換
圖3.5 點集的Delaunay三角網格
第四步:在所有點被插入之後，從網格中刪除多余的三角形單元，最後得到的網格就是點集的Delaunay三角網格，如圖3.5所示。
按照上述算法，編程環境為VC++，Lawson算法的代碼如下，其中參數CSurf*surf表示網格平面，網格結點和單元分別存儲在成員pNodes和pTrgls中。函數IsPointInTrian-gle(x，y，tx［0］，ty［0］，tx［1］，ty［1］，tx［2］，ty［2］)用於判斷點(x，y)是否落在由三點(tx［0］，ty［0］)、(tx［1］，ty［1］)和(tx［2］，ty［2］)組成的三角形中;函數LOP(CTrgl*ta，CTrgl*tb)采用LOP方法優化三角形對ta和tb。
三維地質建模方法及程序實現
三維地質建模方法及程序實現
三維地質建模方法及程序實現
3.2.1.2.2 Bowyer-Watson算法
Bowyer-Watson算法也是壹種先形成初始網格，再逐步插入數據點進行細化的算法。與Lawson算法不同的是，Bowyer-Watson算法插入點時需要判斷網格中三角形單元的外接圓是否包含該結點，而不是判斷該三角形單元本身是否包含該結點;另外壹個區別是Bowyer-Watson算法在每次插入壹個點之後不需要像Lawson算法那樣用LOP算法優化三角網。
Bowyer-Watson算法的主要步驟如下:
第壹步:建立壹個包含整個點集的初始網格。通常情況下初始網格為壹個三角形或由壹個矩形連接對角線得到的壹對三角形。
第二步:依次將數據點插入到最近更新後得到的網格中，形成新的網格並更新，分為三小步:
(1)插入壹個新點 P 到現有的 Delaunay 三角網格中，如圖 3.6(a)所示。
(2)尋找並刪除所有外接圓包含 P 點的三角單元，形成壹個 Delaunay 空腔。圖3.6(a)中的陰影三角形為外接圓包含 P 點的三角單元; 圖 3.6(b)所示為形成的壹個Delaunay 空腔。
(3)連接 P 點和 Delaunay 空腔邊界上所有各點，形成新的 Delaunay 三角網格，如圖3.6(c)所示。
圖3.6 向三角形網格中插入點
第三步:刪除多余的三角形，即如果某個三角形中的某個結點不屬於原始的點集，則刪除該三角形;最後結果即為點集的Delaunay三角剖分網格。
按照上述算法，編程環境為VC++，Bowyer-Watson算法的完整代碼如下，其中參數CSurf*surf表示網格平面，網格結點和單元分別存儲在成員pNodes和pTrgls中。函數TriangleInCircle()的作用是判斷點(xp，yp)是否落在由三點(x1，y1)、(x2，y2)和(x3，y3)組成的三角形的外接圓內。
三維地質建模方法及程序實現
三維地質建模方法及程序實現
三維地質建模方法及程序實現
三維地質建模方法及程序實現
采用上述算法和代碼，對壹個包含46個點的點集進行Delaunay剖分，圖3.7(a)所示為輸入的點集，得到擁有74個三角形單元的網格，如圖3.7(b)所示。
圖3.7 Bowyer-Watson算法剖分實例