??最近計算幾何課程要求交一個結課論文，借這個機會蔑滓，我就認真地學習了下Delaunay三角剖分。
Delaunay三角剖分其實并不是一種算法，它只是給出了一個“好的”三角網(wǎng)格的定義巢块，它的優(yōu)秀特性是空圓特性和最大化最小角特性，這兩個特性避免了狹長三角形的產(chǎn)生巧号，也使得Delaunay三角剖分應用廣泛族奢。
空圓特性其實就是對于兩個共邊的三角形，任意一個三角形的外接圓中都不能包含有另一個三角形的頂點丹鸿，這種形式的剖分產(chǎn)生的最小角最大越走。
假如以AC來剖分四邊形ABCD，這里B點在三角形ACD的外接圓內靠欢，D點在三角形ABC的外接圓內廊敌，所以不具有空圓特性
以BD來剖分四邊形ABCD，C點不在三角形ABD的外接圓內掺涛，A點也不在三角形BCD的外接圓內庭敦，具有空圓特性，而且它的最小角要比不滿足空圓特性的最小角大薪缆。
問題描述
??現(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 如果這個點在三角形的外接圓內
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ù)組中所有重復的邊都刪除减拭，注意這里是把所有的重復邊都刪除蔽豺，比如有邊e1,e2,e2,e3，刪除后應該只剩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绢记，這個三角形要把所有點都包含進去扁达。
??接著分析A點，因為A點在三角形PQR的外接圓內部蠢熄，所以利用A點將三角形PQR分拆成三個子三角形跪解。
??再考慮Ｂ點，它只在三角形AQR的內部签孔，再將三角形AQR分拆成三個子三角形惠遏。
??接著是C點，這時我們有5個三角形骏啰，對這5個三角形每一個檢查C點在不在它的外接圓內。經(jīng)過檢測抽高，發(fā)現(xiàn)它在三角形APR和三角形ABR的外接圓內判耕。
??刪除三角形APR和三角形ABR的公共邊AR，得到四邊形ABPR翘骂，并將C點與每一個邊組成一個三角形壁熄。
??最后對D點進行分析，它在三角形ABC和三角形BCR的外接圓內碳竟，所以應刪除公共邊BC草丧，再用D點與這兩個三角形的其他邊形成子三角形。
??最后把含有超級三角形的頂點的三角形全部刪除莹桅，就得到這四個點的三角剖分
??我編寫程序的時候使用三個點進行測試昌执，有時候結果出不來，是因為在最后一步刪除超級三角形的時候是這樣的
??另外關于這個方法唐断，我在Github上看到了一個實現(xiàn)，作者是jeanbroid杭抠，用openGL做顯示脸甘，里面用了很多C++標準庫的東西，讓我大開眼界祈争，非常感謝他斤程，不過他用到了雙緩存，需要把demo.cpp中的GLUT_SINGLE改成GLUT_DOUBLE才能運行。
分治法
??分治法是我在查看維基百科的時候看到的忿墅，據(jù)維基百科說分治法是效率最高的一種方法扁藕。在維基百科的引用中發(fā)現(xiàn)了一個介紹delaunay三角剖分的分治法的一個非常好的網(wǎng)站，網(wǎng)站作者是Samuel Peterson疚脐，這個網(wǎng)站主要介紹了在給定條件下的Delaunay三角剖分亿柑。
??分治法進行三角剖分需要對點集中所有點按照x坐標的升序進行排序，x坐標相同時棍弄，按照y坐標進行排序望薄，接著將整個點集遞歸地劃分數(shù)量相近的兩個子集，直到子集中點的數(shù)目小于等于3呼畸。
??先給出一個定義方便后面敘述痕支。對于一條邊，如果它的兩個端點都在分割線的左邊蛮原，稱它為LL邊卧须，一端在左邊一端在右邊稱為LR邊，兩個端點都在右邊稱為RR邊儒陨。
??分治法的重點在于如何遞歸地合并三角網(wǎng)格花嘶。
??首先是確定一條LR基線，這條線位于最下方蹦漠，且不與其他邊相交椭员，如27邊
??接著，確定下一條LR邊笛园。以右側三角網(wǎng)為例隘击，按照順時針方向，計算出∠672研铆，∠872闸度，∠1072，∠972的值蚜印，并根據(jù)角度大小對頂點進行排序莺禁，角度最小的點為第一候選點，以此類推窄赋，這里第一候選點為6哟冬，第二候選點為8。
??作三角形276的外接圓忆绰，發(fā)現(xiàn)第二候選點8不在該外接圓內浩峡，且∠672小于180°，故右側的候選點為6错敢。候選點的要求是以候選點與該側基線端點形成的角小于180°翰灾，且不包含下一候選點缕粹。若大于180°，則該側無候選點纸淮，若包含下一候選點平斩，則考慮下一候選點是否滿足該條件。按照這種方法對左側三角網(wǎng)格進行分析咽块，可得到左側候選點為點3绘面。
當左右兩側都存在候選點時，如當前情況侈沪，這時需要考慮下一條LR邊是37還是26揭璃。作三角形237的外接圓，可發(fā)現(xiàn)右側候選點6在此外接圓外亭罪，而左側候選點在三角形276外接圓內瘦馍，故下一條LR邊為邊37。
當只有一側存在候選點時应役，將此候選點與基線另一側的端點連線作為下一條LR邊扣墩。
??將邊37作為下一條基線重復該過程，直到兩邊都不存在候選點扛吞，程序結束。
附一張Bowyer算法最后的顯示效果
