??最近計算幾何課程要求交一個結(jié)課論文，借這個機(jī)會，我就認(rèn)真地學(xué)習(xí)了下Delaunay三角剖分。
Delaunay三角剖分其實并不是一種算法，它只是給出了一個“好的”三角網(wǎng)格的定義，它的優(yōu)秀特性是空圓特性和最大化最小角特性，這兩個特性避免了狹長三角形的產(chǎn)生，也使得Delaunay三角剖分應(yīng)用廣泛。
空圓特性其實就是對于兩個共邊的三角形，任意一個三角形的外接圓中都不能包含有另一個三角形的頂點，這種形式的剖分產(chǎn)生的最小角最大。
假如以AC來剖分四邊形ABCD，這里B點在三角形ACD的外接圓內(nèi)，D點在三角形ABC的外接圓內(nèi)，所以不具有空圓特性
以BD來剖分四邊形ABCD，C點不在三角形ABD的外接圓內(nèi)，A點也不在三角形BCD的外接圓內(nèi)，具有空圓特性，而且它的最小角要比不滿足空圓特性的最小角大。
問題描述
??現(xiàn)在給定了平面上的一個點集V，求出它的Delaunay三角剖分
Bowyer逐點插入法
??Bowyer逐點插入法是一個很經(jīng)典的實現(xiàn)方法，網(wǎng)上的資料大多數(shù)都是采用的這種算法。這里使用的算法是按照 Paul Bourke在論文中提供的偽代碼實現(xiàn)的，這個偽代碼也寫的很好，非常容易懂
以下摘自他的論文
subroutine triangulate
input : vertex list 輸入：頂點鏈表
output : triangle list 輸出：三角形鏈表
initialize the triangle list 初始化三角形鏈表
determine the supertriangle 確定超級三角形
add supertriangle vertices to the end of the vertex list 將超級三角形的頂點加入到頂點鏈表中
add the supertriangle to the triangle list 將超級三角形加入到三角形鏈表中
for each sample point in the vertex list 對頂點鏈表中的每一個點
initialize the edge buffer 初始化邊數(shù)組
for each triangle currently in the triangle list 對于三角形鏈表中的每一個三角形
calculate the triangle circumcircle center and radius 計算出外接圓圓心和半徑
if the point lies in the triangle circumcircle then 如果這個點在三角形的外接圓內(nèi)
add the three triangle edges to the edge buffer 把這個三角形的三條邊加入到邊數(shù)組中
remove the triangle from the triangle list 從三角形鏈表中將這個三角形刪除
endif
endfor
delete all doubly specified edges from the edge buffer 把邊數(shù)組中所有重復(fù)的邊都刪除，注意這里是把所有的重復(fù)邊都刪除，比如有邊e1,e2,e2,e3，刪除后應(yīng)該只剩e1和e3
this leaves the edges of the enclosing polygon only 這步會得到一個閉合的多邊形
add to the triangle list all triangles formed between the point 用這個點和邊數(shù)組中的每一條邊都組合成一個三角形，加入到三角形鏈表中
and the edges of the enclosing polygon
endfor
remove any triangles from the triangle list that use the supertriangle vertices從三角形鏈表中刪除使用超級三角形頂點的三角形
remove the supertriangle vertices from the vertex list將超級三角形的頂點從頂點鏈表中刪除
end
??在使用過程中，發(fā)現(xiàn)“把超級三角形的頂點加入到頂點鏈表中”似乎沒什么必要，另外，頂點用數(shù)組存好一點，因為不需要添加和刪除。
??以四個點A、B、C、D舉例，首先建立一個超級三角形PQR，這個三角形要把所有點都包含進(jìn)去。
??接著分析A點，因為A點在三角形PQR的外接圓內(nèi)部，所以利用A點將三角形PQR分拆成三個子三角形。
??再考慮Ｂ點，它只在三角形AQR的內(nèi)部，再將三角形AQR分拆成三個子三角形。
??接著是C點，這時我們有5個三角形，對這5個三角形每一個檢查C點在不在它的外接圓內(nèi)。經(jīng)過檢測，發(fā)現(xiàn)它在三角形APR和三角形ABR的外接圓內(nèi)。
??刪除三角形APR和三角形ABR的公共邊AR，得到四邊形ABPR，并將C點與每一個邊組成一個三角形。
??最后對D點進(jìn)行分析，它在三角形ABC和三角形BCR的外接圓內(nèi)，所以應(yīng)刪除公共邊BC，再用D點與這兩個三角形的其他邊形成子三角形。
??最后把含有超級三角形的頂點的三角形全部刪除，就得到這四個點的三角剖分
??我編寫程序的時候使用三個點進(jìn)行測試，有時候結(jié)果出不來，是因為在最后一步刪除超級三角形的時候是這樣的
??另外關(guān)于這個方法，我在Github上看到了一個實現(xiàn)，作者是jeanbroid，用openGL做顯示，里面用了很多C++標(biāo)準(zhǔn)庫的東西，讓我大開眼界，非常感謝他，不過他用到了雙緩存，需要把demo.cpp中的GLUT_SINGLE改成GLUT_DOUBLE才能運行。
分治法
??分治法是我在查看維基百科的時候看到的，據(jù)維基百科說分治法是效率最高的一種方法。在維基百科的引用中發(fā)現(xiàn)了一個介紹delaunay三角剖分的分治法的一個非常好的網(wǎng)站，網(wǎng)站作者是Samuel Peterson，這個網(wǎng)站主要介紹了在給定條件下的Delaunay三角剖分。
??分治法進(jìn)行三角剖分需要對點集中所有點按照x坐標(biāo)的升序進(jìn)行排序，x坐標(biāo)相同時，按照y坐標(biāo)進(jìn)行排序，接著將整個點集遞歸地劃分?jǐn)?shù)量相近的兩個子集，直到子集中點的數(shù)目小于等于3。
??先給出一個定義方便后面敘述。對于一條邊，如果它的兩個端點都在分割線的左邊，稱它為LL邊，一端在左邊一端在右邊稱為LR邊，兩個端點都在右邊稱為RR邊。
??分治法的重點在于如何遞歸地合并三角網(wǎng)格。
??首先是確定一條LR基線，這條線位于最下方，且不與其他邊相交，如27邊
??接著，確定下一條LR邊。以右側(cè)三角網(wǎng)為例，按照順時針方向，計算出∠672，∠872，∠1072，∠972的值，并根據(jù)角度大小對頂點進(jìn)行排序，角度最小的點為第一候選點，以此類推，這里第一候選點為6，第二候選點為8。
??作三角形276的外接圓，發(fā)現(xiàn)第二候選點8不在該外接圓內(nèi)，且∠672小于180°，故右側(cè)的候選點為6。候選點的要求是以候選點與該側(cè)基線端點形成的角小于180°，且不包含下一候選點。若大于180°，則該側(cè)無候選點，若包含下一候選點，則考慮下一候選點是否滿足該條件。按照這種方法對左側(cè)三角網(wǎng)格進(jìn)行分析，可得到左側(cè)候選點為點3。
當(dāng)左右兩側(cè)都存在候選點時，如當(dāng)前情況，這時需要考慮下一條LR邊是37還是26。作三角形237的外接圓，可發(fā)現(xiàn)右側(cè)候選點6在此外接圓外，而左側(cè)候選點在三角形276外接圓內(nèi)，故下一條LR邊為邊37。
當(dāng)只有一側(cè)存在候選點時，將此候選點與基線另一側(cè)的端點連線作為下一條LR邊。
??將邊37作為下一條基線重復(fù)該過程，直到兩邊都不存在候選點，程序結(jié)束。
附一張Bowyer算法最后的顯示效果
