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

Delaunay三角剖分算法的定義？

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

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

2. 沒有相交的邊。

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

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

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

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

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

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

Lop過程如下圖所示：

Delaunay三角剖分算法

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