基于flip的Delaunay三角剖分算法研究.pdf

1、三角剖分是計(jì)算幾何、CAD、曲面重構(gòu)以及計(jì)算機(jī)圖形學(xué)等領(lǐng)域的重要研究內(nèi)容。基于三角剖分的實(shí)際應(yīng)用極為廣泛，本文選擇三角剖分的剖分算法進(jìn)行研究，其目的是要設(shè)計(jì)出一個(gè)簡單高效的三角剖分算法，以便在計(jì)算機(jī)圖形學(xué)等領(lǐng)域加以應(yīng)用。因此本次研究，不僅具有一定的理論意義，而且還有很大的實(shí)際應(yīng)用價(jià)值。
　　 本文針對平面點(diǎn)集的三角剖分進(jìn)行研究。通過對經(jīng)典算法的研究可以發(fā)現(xiàn)，目前常見的平面點(diǎn)集的三角剖分算法，普遍存在著執(zhí)行效率低，候選節(jié)點(diǎn)可能出現(xiàn)

2、“位置違約”等缺陷，由于這些缺陷的存在，常?？赡軐?dǎo)致所得到的三角剖分結(jié)果不是最優(yōu)的。為了解決這一問題，本文提出了一種新的Delaunay三角剖分算法，其基本思想是：基于Graham掃描法并對之進(jìn)行改進(jìn)，在求出平面點(diǎn)集的凸包的同時(shí)，生成初期的Delaunay三角剖分，在此基礎(chǔ)上，采用Delaunayflip方法對之進(jìn)行優(yōu)化，使得剖分后得到的三角形的最小角最大化，從而得到性能最優(yōu)的Delaunay三角剖分。
　　 該算法很好地避免了