約束Delaunay三角剖分算法的研究與應(yīng)用.pdf

1、三角剖分在曲面重構(gòu)、有限元分析和地學(xué)領(lǐng)域中都扮演著重要的角色。隨著研究對(duì)象越來越復(fù)雜,大規(guī)模的帶有約束邊的三角網(wǎng)格剖分和如何提高三角網(wǎng)格的生成效率和構(gòu)網(wǎng)質(zhì)量成為了當(dāng)前網(wǎng)格剖分的研究熱點(diǎn),Delaunay三角網(wǎng)格的優(yōu)良特性受到了諸多學(xué)者的青睞。本文主要研究了約束Delaunay三角剖分算法,在合成法的基礎(chǔ)上進(jìn)行改進(jìn),并將其編程實(shí)現(xiàn),最后將其應(yīng)用到某高爐爐襯侵蝕曲線預(yù)測(cè)工程項(xiàng)目中。本文主要研究了以下幾個(gè)問題:
　　 (1)基于逐點(diǎn)插

2、入法思想的Delaunay三角剖分算法雖具有算法容易編程實(shí)現(xiàn)的優(yōu)勢(shì),但是算法復(fù)雜度最壞情況下達(dá)到了o(n2),在處理海量數(shù)據(jù)時(shí)效率不高。歸并法的時(shí)間復(fù)雜度能達(dá)到o(nlogn),但由于其對(duì)內(nèi)存要求太高,在處理海量數(shù)據(jù)時(shí)對(duì)內(nèi)存空間的要求極為苛刻。本文將逐點(diǎn)插入法和歸并法的優(yōu)點(diǎn)予以結(jié)合,較好的降低算法的時(shí)間復(fù)雜度和空間復(fù)雜度。
　　 (2)對(duì)于逐點(diǎn)插入法,針對(duì)每一個(gè)插入點(diǎn)都需要遍歷所有的三角形鏈表,該過程算法的優(yōu)劣直接影響算法的總體

3、效率。本文提出了一種“基于三角形方向搜索法”的算法,在該算法中不涉及乘法、開方和三角函數(shù)等復(fù)雜運(yùn)算,并能實(shí)現(xiàn)高效準(zhǔn)確的對(duì)插入點(diǎn)進(jìn)行定位。
　　 (3)在約束Delaunay三角剖分中,針對(duì)搜索約束邊的影響域的問題,本文提出了一種”影響域快速搜索“算法,采用先預(yù)處理再搜索的方法,降低了算法的復(fù)雜度。
　　 (4)在基于以上對(duì)算法的改進(jìn)基礎(chǔ)上,本文將改進(jìn)后的算法應(yīng)用到實(shí)際的工程項(xiàng)目中,驗(yàn)證了算法的可行性、穩(wěn)定性和高效性,收到