空間散亂點(diǎn)集Delaunay三角剖分的算法優(yōu)化及實(shí)現(xiàn).pdf

1、三角剖分在曲面重構(gòu)、三維有限元方法的預(yù)處理、醫(yī)學(xué)可視化及地理信息系統(tǒng)(GIS)等領(lǐng)域有廣泛的應(yīng)用。Delaunay三角剖分是計(jì)算機(jī)輔助幾何設(shè)計(jì)、幾何造型及計(jì)算機(jī)圖形學(xué)中的重要研究?jī)?nèi)容之一。對(duì)于設(shè)計(jì)一個(gè)三角剖分算法來(lái)說(shuō)，最重要的就是其復(fù)雜度低和高質(zhì)量網(wǎng)格的形成。Delaunay三角剖分算法由于其良好的優(yōu)化特性受到青睞，本文對(duì)其算法進(jìn)行研究及優(yōu)化改進(jìn)有著重要的理論意義和重大的應(yīng)用價(jià)值。 本文討論的空間三維散亂點(diǎn)Delaunay三角剖

2、分的方法，由散亂點(diǎn)的導(dǎo)入、三角剖分到最后的結(jié)果顯示輸出，涉及到了計(jì)算幾何、計(jì)算機(jī)圖形學(xué)及Direct3D編程等相關(guān)知識(shí)。平面的Delaunay三角剖分已經(jīng)較為成熟，而三維Delaunay三角剖分仍需進(jìn)一步完善和改進(jìn)，這正是本文對(duì)其進(jìn)行研究的目的。 本文在詳細(xì)研究和分析了典型的Delaunay三角剖分算法的思想后，針對(duì)增量算法中的關(guān)鍵問(wèn)題提出改進(jìn)的方法，從降低算法的時(shí)間復(fù)雜度的角度出發(fā)，以點(diǎn)定位搜索這一關(guān)鍵問(wèn)題為切入點(diǎn)，提出新的改

3、進(jìn)搜索的方法，該算法利用四面體三角面的法矢與該面的點(diǎn)到插入點(diǎn)之間形成的向量的夾角來(lái)確定定位方向，不需額外的搜索數(shù)據(jù)結(jié)構(gòu)，且對(duì)于每個(gè)搜索四面體只需三個(gè)面的法矢和夾角的計(jì)算，減少了搜索過(guò)程中的計(jì)算量，且定位的路徑較優(yōu)，有效提高了算法的效率，使整個(gè)Delaunay三角剖分算法的時(shí)間復(fù)雜度約為O(NL12)，接近線性時(shí)間。 算法的實(shí)現(xiàn)和結(jié)果的輸出顯示是一個(gè)重要的環(huán)節(jié)，本文集成了Direct3D與MFC單文檔框架，并基于該框架建立三維散亂