【定義】三角剖分 ：假設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 Procedure)，一般三角網經過LOP處理，即可確保成為Delaunay三角網，其基本做法如下所示：

1.將兩個具有共同邊的三角形合成一個多邊形。

2.以最大空圓準則作檢查，看其第四個頂點是否在三角形的外接圓之內。

3.如果在，修正對角線即將對角線對調，即完成局部優化過程的處理。

LOP處理過程如下圖所示：

Delaunay剖分的算法

Delaunay剖分是一種三角剖分的標準，實現它有多種算法。