什么是三角剖分？在幾何中，三角剖分是指將平面對象細分為三角形，并且通過擴展將高維幾何對象細分為單純形。 對于一個給定的點集，有很多種三角剖分，如：

OI 中的三角剖分主要指二維幾何中的完美三角剖分（二維Delaunay三角剖分，簡稱DT）。

這個算法本身也不容易，有幾個難點，如何高效的找到可疑邊和對立點？如果高效的進行點定位（Point Location）操作？即確定插入點落在哪個三角形內(nèi)部？如何判斷點是否在某三個點的外接圓內(nèi)部？如果能把這幾個疑問弄清楚，相信大家用好三角剖分也沒有問題了。

三角剖分定義

在數(shù)學和計算幾何中，對于給定的平面中的離散點集P，其 Delaunay 三角剖分 DT(P) 滿足：

（1）空圓性：DT(P) 是 唯一 的（任意四點不能共圓），在 DT(P) 中，任意 三角形的外接圓范圍內(nèi)不會有其它點存在。

（2）最大化最小角：在點集P可能形成的三角剖分中，DT(P) 所形成的三角形的最小角最大。從這個意義上講，DT(P) 是 最接近于規(guī)則化 的三角剖分。具體的說是在兩個相鄰的三角形構(gòu)成凸四邊形的對角線，在相互交換后，兩個內(nèi)角的最小角不再增大。

性質(zhì)

（1）最接近：以最接近的三點形成三角形，且各線段（三角形的邊）皆不相交。

（2）唯一性：不論從區(qū)域何處開始構(gòu)建，最終都將得到一致的結(jié)果（點集中任意四點不能共圓）。

（3）最優(yōu)性：任意兩個相鄰三角形構(gòu)成的凸四邊形的對角線如果可以互換的話，那么兩個三角形六個內(nèi)角中最小角度不會變化。

（4）最規(guī)則：如果將三角剖分中的每個三角形的最小角進行升序排列，則 Delaunay 三角剖分的排列得到的數(shù)值最大。

（5）區(qū)域性：新增、刪除、移動某一個頂點只會影響鄰近的三角形。

（6）具有凸邊形的外殼：三角剖分最外層的邊界形成一個凸多邊形的外殼。

三角剖分算是一個計算幾何里常用的算法，它的構(gòu)造方案有許多，其中一個算法是 Bowyer-Watson。樸素的 Bowyer-Watson 算法實現(xiàn)復(fù)雜度是的，而我使用的這個算法基于的是隨機增量方法，期望時間復(fù)雜度為。雖然也是暴力，時間復(fù)雜度看起來不對，但由于我們是隨機的選擇插入順序，超過的情況幾乎不存在。