Delaunay三角剖分算法的定義？【定義】三角剖分：假設(shè)V是二維實數(shù)域上的有限點集，邊e是由點集中的點作為端點組成的閉合線段，e是e的集合，則點集V的三角剖分t=（V，e）是平面圖G，滿足下列條件：

Delaunay三角剖分算法的定義？

【定義】三角剖分：假設(shè)V是二維實數(shù)域上的有限點集，邊e是由點集中的點作為端點組成的閉合線段，e是e的集合，則點集V的三角剖分t=（V，e）是平面圖G，滿足下列條件：

1。除了端點，平面圖中的邊在點集中不包含任何點。

2. 沒有相交的邊。

3. 平面圖中所有的面都是三角形的，所有的三角形面集都是散亂點集v的凸包，Delaunay三角剖分是實踐中應(yīng)用最廣泛的三角剖分，是一種特殊的三角剖分。讓我們從Delaunay邊開始：【定義】Delaunay邊：假設(shè)e中的邊e（兩個端點是a和b）滿足以下條件，則稱之為Delaunay邊：有一個圓通過兩點a和b，并且在圓的內(nèi)部（注意它在圓的內(nèi)部，并且圓上最多有三個點在同一個圓中）不包含點集V中的任何其他點。此屬性也稱為空圓屬性。

[定義]Delaunay三角剖分：如果點集V的三角剖分t僅包含Delaunay邊，則該三角剖分稱為Delaunay三角剖分。

優(yōu)化處理：在理論上，為了構(gòu)造Delaunay三角網(wǎng)，Lawson提出了局部優(yōu)化方法（LOP）。一般情況下，經(jīng)過lop處理后的三角剖分可以保證是Delaunay三角剖分?；痉椒ㄈ缦拢?/p>

1。具有相同邊的兩個三角形組合成一個多邊形。

2. 根據(jù)最大空圓準(zhǔn)則檢查第四個頂點是否在三角形的外接圓內(nèi)。

3. 如果對對角線進行了修改，即對角線發(fā)生了偏移，即完成了局部優(yōu)化過程。

Lop過程如下圖所示：

Delaunay三角剖分算法

Delaunay三角剖分是三角剖分的標(biāo)準(zhǔn)，實現(xiàn)它的算法很多。