Delaunay三角剖分演算法

⑴ 閉合多邊形的三角剖分演算法

當剖面位於邊界時，為了建立完整三維表面模型，需要對地層最小多邊形(即閉合多邊形)本身進行三角剖分，以便進行地層的縫合，構成一個閉合的三維地層表面模型。除了做約束Delaunay三角剖分之外，採用凸出點刪除法(Øyvind et al.，2006)直接進行二維閉合多邊形的三角剖分，從而避免Delaunay方法中還需將多邊形進行垂直方向與水平方向來回的轉換過程。

點p_i為閉合簡單多邊形C(P)上的有序點列之一，如果滿足如下兩個條件，則稱p_i為凸出點，如圖4.19a所示。

(1)相鄰三節點p_i、p_i-1和p_i+1，滿足∠p_i-1p_ip_i+1＜π；

(2)三角形T_i-1，i，i+1不包含p_i、p_i-1和p_i+1之外的點。

凸出點刪除方法如下：

(1)查找多邊形C(P)任意一個凸出點p_i。

(2)連接點p_i-1和p_i+1，創建三角形T_{i-1，i，i+1}，並將其存入三角形鏈表。然後，在多邊形C(P)的點鏈表中刪除點p_i。

(3)如果C(P)只剩三個點，則構成最後一個三角形；停止查找。

(4)回到(1)。

圖4.19 閉合多邊形三角剖分凸出點刪除法過程

該方法所得到的多邊形三角剖分結果不唯一。

局部優化方法：刪除當前凸出點p_i後，優先判斷點p_i-1和p_i+1是否為凸出點，若只有其中一個為凸出點，則將其作為當前凸出的點；若兩個點都為凸出點，則選擇角度最接近60°的凸出點。圖4.19顯示了一個閉合多邊形三角化的整個過程。

⑵ 　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三角化的演算法步驟及實現

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三角剖分

從上文中介紹的對點集的Delaunay三角剖分方法可以知道，點集的Delaunay的三角剖分方法是最簡單、最基礎的，所以，可以考慮在點集的Delaunay三角剖分方法的基礎上獲得區域的Delaunay三角剖分，實際上，區域的Delaunay三角剖分方法正是這樣做的。

為了利用點集的Delaunay三角剖分方法，首先應該將剖分對象從區域轉換到點集，而為了實現上述目的，需要經過兩個過程:布點、離散邊界。布點即是向區域內插入一些合適的點，離散邊界即是將區域邊界分割成若干小線段。在進行上述處理後，就將需要剖分的對象從一個區域轉變成一個點集，點集中的點為向區域內插入的點和邊界離散後形成小線段的端點;然後採用點集的Delaunay三角剖分方法，如Lawson演算法或Bowyer-Wat-son演算法，對從區域轉換過來的點集進行Delaunay三角剖分操作;最後需要刪除那些在區域之外的三角形，因為對一個點集進行Delaunay三角剖分操作，最後獲得的三角剖分的范圍是該點集的凸殼，而點集的凸殼絕大多數情況下與需要剖分的區域不一致，通常情況下是凸殼的范圍大於需要剖分的區域，因此那些屬於凸殼但不屬於需要剖分的區域的三角形需要刪除。

區域的Delaunay三角剖分方法可以概括為3個步驟:

第一步:布點並離散邊界，將剖分對象從區域轉換為點集。根據剖分規模或想要得到的三角形單元的大概邊長，向區域內插入一系列的內部點，並將內外邊界離散成一系列的小線段。圖3.14(a)為某剖分區域，圖3.14(b)為向區域內布點的結果，圖3.14(c)則時在布點之後進行離散邊界的結果。

三維地質建模方法及程序實現

三維地質建模方法及程序實現

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

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

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

⑺ 誰對opencv裡面的delaunay三角剖分方法比較熟悉的

具體什麼不太懂，不過我收藏了一個以前別人講這方面的東西，你看看，希望對你有幫助。

Delaunay三角網是俄國數學家B.Delaunay於1934年發現的。關於Delaunay三角網構建的研究有許多，但由於本課題具有數據量大的特徵，不宜直接沿用已有構建方法，筆者針對本課題數據特徵，研究獲得了適應本課題，速度較快的構建方法。Delaunay三角網有一個特性，每個三角網形成的外接圓都不包含其他參考點。利用這一個性質，我們可以直接構成Delaunay三角網：
一、建立第一個三角形
1、判斷用來建立TIN的總腳點數，小於3則報錯退出。
2、第一點的選擇：
鏈表的第一節點，命名為Pt1;
3、第二點的選擇：
A.非Pt1點； B.距Pt1最近
命名為Pt2
4、第三點的選擇
A.非Pt1，Pt2點；
B.與Pt1，Pt2點組成的三角形的外接圓內無其他節點；
C.與Pt1，Pt2組成的三角形中的角Pt1Pt3Pt2最大。
命名為Pt3
5、生成三邊，加入邊表
6、生成第一個三角形，組建三角形表
二、擴展TIN
1、從邊表頭取一邊，要求：該邊flag標志為假（只在一個三角形中）
2、從點鏈表中搜索一點，要求：
A、與邊中的Pixel3在邊的異側；
B、該點與邊組成的三角形的外接圓內無其他點
C、滿足上面兩條件的點中角Pt1Pt3Pt2最大的點為Pt3。
3、判斷新生成的邊，如果邊表中沒有，則加入邊表尾，設定標志flag為假，如果有，則設定該邊flag為真。
4、將生成的三角形假如三角形表
5、設定選中的邊的標志flag為真
6、轉至1，直至邊表邊的標志flag全部為真。

數據結構：
struct Pixel //腳點數據
{
double x,y,z,g;
bool flag;
};
struct List //數據鏈表
{
Pixel *pixel;
List *next;
};
struct Line //三角形邊
{
Pixel *pixel1; //三角形邊一端點
Pixel *pixel2; //三角形邊另一端點
Pixel *pixel3; //三角形邊所對頂點
bool flag;
};
struct Linelist //三角形邊表
{
Line *line;
Linelist *next;
};
struct Triangle //三角形表
{
Line *line1;
Line *line2;
Line *line3;
Triangle *next;
};

以下是我程序中關於建網的部分：
// DelaunayTIN.cpp: implementation of the CDelaunayTIN class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Reconstruction.h"
#include "DelaunayTIN.h"

#include "MyMath.h"
#include <math.h>
#include "ListControl.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CDelaunayTIN::CDelaunayTIN()
{

}

CDelaunayTIN::~CDelaunayTIN()
{

}

/////////////////////////////////////////////////////////////////////////////
//函數名： CreateDelaunayTIN
//編寫者： Polaris
//參考資料：
//功能： 用給定的數據鏈表數據，組建Delaunay不規則三角網
//輸入參數：數據鏈表list;區域范圍(XMin,YMin),(XMax,YMax)
//輸出參數：不規則三角網首三角形地址
//備註：
/////////////////////////////////////////////////////////////////////////////
struct Triangle * CDelaunayTIN::CreateDelaunayTIN(List *list)
{
//組建第一個三角形
CMyMath MyMath;
CListControl ListControl;
struct List *node;
struct Pixel *pt1,*pt2,*pt3;
bool flag;
struct Triangle *TIN;
pt1=list->pixel;
pt2=list->next->pixel;
node=list->next->next;
while(node!=NULL)
{
if(MyMath.Calculate2PtDistanceIn3D
(pt1->x,pt1->y,pt1->z,node->pixel->x,node->pixel->y,node->pixel->z)
<MyMath.Calculate2PtDistanceIn3D
(pt1->x,pt1->y,pt1->z,pt2->x,pt2->y,pt2->z))
{
pt2=node->pixel;
}
node=node->next;
}
node=list->next;
pt3=NULL;
while(node!=NULL)
{
if(node->pixel==pt1 || node->pixel==pt2)
{
node=node->next;
continue;
}
if(pt3==NULL)
{
pt3=node->pixel;
}
else
{
if((pow(MyMath.Calculate2PtDistanceIn2D(pt1->x,pt1->y,node->pixel->x,node->pixel->y),2)+pow(MyMath.Calculate2PtDistanceIn2D(pt2->x,pt2->y,node->pixel->x,node->pixel->y),2)-pow(MyMath.Calculate2PtDistanceIn2D(pt1->x,pt1->y,pt2->x,pt2->y),2))/(2*MyMath.Calculate2PtDistanceIn2D(pt1->x,pt1->y,node->pixel->x,node->pixel->y)*MyMath.Calculate2PtDistanceIn2D(pt2->x,pt2->y,node->pixel->x,node->pixel->y))
<(pow(MyMath.Calculate2PtDistanceIn2D(pt1->x,pt1->y,pt3->x,pt3->y),2)+pow(MyMath.Calculate2PtDistanceIn2D(pt2->x,pt2->y,pt3->x,pt3->y),2)-pow(MyMath.Calculate2PtDistanceIn2D(pt1->x,pt1->y,pt2->x,pt2->y),2))/(2*MyMath.Calculate2PtDistanceIn2D(pt1->x,pt1->y,pt3->x,pt3->y)*MyMath.Calculate2PtDistanceIn2D(pt2->x,pt2->y,pt3->x,pt3->y)))
{
pt3=node->pixel;
}
}
node=node->next;
}
//LineList
Linelist *linehead,*linenode,*linelast;
Line *ln1,*ln2,*ln3;
linenode=new Linelist;
linenode->line=new Line;
linenode->line->pixel1=pt1;

⑻ 最優三角剖分的「最優」指的是什麼最優

最優三角剖分的「最優」指的是應該是內角最接近最優。

定義一個t[i][j]，1<=i<=j<=N,為凸子多邊形{vi-1,vi,…,vj}的最優三角剖分所對應的權函數值，即其最優值。據此定義，要計算的凸(n+1)邊形P的最優權值為t[1][n]。
Delaunay三角剖分演算法指的是點集的三角剖分(Triangulation)，對數值分析(比如有限元分析)以及圖形學來說，都是極為重要的一項預處理技術。尤其是Delaunay三角剖分，由於其獨特性，關於點集的很多種幾何圖都和Delaunay三角剖分相關，如Voronoi圖，EMST樹，Gabriel圖等。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剖分

約束Delaunay剖分就是強迫點按所需的連線進行連接。這種方法在構制含斷層的曲面時非常有用。由於構造面上有斷層存在，斷層內是不需要連接線的，連接線必須含所需的線段。在這種情況下，就要用到約束Delaunay剖分。

Cline和Renka（1990）提出一種約束Delaunay剖分方法，這種方法首先將點按無約束Delaunay方法進行剖分。然後將所需的邊加進去，形成對這種結構進行描述的數據矩陣。

約束Delaunay剖分的定義如下：一個三角形的外接圓內可以包含另一個結點，僅當該結點與該三角形被所需的連接邊隔開的時候。

實際計算時，有如下演算法：

（1）找到所有與要求的連接線相矛盾的三角形，將其中的內邊去掉，構成一個多邊形；

（2）將所要求的連接線加入到該多邊形內；

（3）按照所對的頂點內角最大的原則，繼續形成剩餘的三角形邊。

圖2.3～圖2.6給出了約束Delaunay剖分用於含斷層構造面的三角形化的例子。

圖2.3無約束Delaunay剖分（虛線為斷層線）

圖2.4約束Delaunay剖分（虛線）與無約束Delaunay剖分（實線）的比較

圖2.5約束Delaunay剖分後挖去的斷層

圖2.6約束Delaunay剖分用於含斷層的網路