快速三維凸包算法的研究與改進(jìn).pdf

1、摘要本論文主要提出了一種改進(jìn)的快速三維凸包構(gòu)造新算法。在過(guò)去幾十年凸包算法的研究取得了一系列的進(jìn)步，如二維的Graham掃描算法，Javis卷包裹(wrapping)算法等等，基于排序的算法平均時(shí)間復(fù)雜度都是O(r1109n)。而在三維凸包算法領(lǐng)域里，則有經(jīng)典的Clarkson和Shor算法，以及QuickHull算法。本質(zhì)上講，這兩個(gè)算法都基于隨機(jī)增量算法，通過(guò)動(dòng)態(tài)地添加外部點(diǎn)來(lái)逐步構(gòu)造出完整的凸包，優(yōu)點(diǎn)是易于理解操作，并且時(shí)間復(fù)雜度

2、仍然是凸包構(gòu)造的下限O(nlogn)。而根據(jù)大量的統(tǒng)計(jì)數(shù)據(jù)表明，對(duì)于任意一個(gè)充分大的點(diǎn)集而言，絕大部分點(diǎn)不是最終凸包的頂點(diǎn)。所以，本文在詳細(xì)研究了這兩個(gè)算法的隨機(jī)性基礎(chǔ)上，進(jìn)一步、引入了非隨機(jī)的性質(zhì)，加速了QuickHull算法。全文主要內(nèi)容為：1)提出了一種新的三維凸包的構(gòu)造算法，這種改進(jìn)的快速算法參考了QuickHuU算法里面每輪迭代選取外部集合中的極值點(diǎn)來(lái)作為候選點(diǎn)，更新成新的凸包的思想，并在這個(gè)基礎(chǔ)上改進(jìn)為選用二次極值點(diǎn)來(lái)構(gòu)造新

3、凸包的方法，同時(shí)綜合使用了一個(gè)二部圖數(shù)據(jù)結(jié)構(gòu)“沖突圖”來(lái)記錄外部點(diǎn)與當(dāng)前的凸包的可見(jiàn)性關(guān)系，最終達(dá)到了排除內(nèi)部點(diǎn)，迅速縮小構(gòu)建的規(guī)模，實(shí)現(xiàn)了高效地構(gòu)建凸包，本文的實(shí)驗(yàn)也說(shuō)明了兩者相比，新算法比QuickHull算法效率更高。2)采用VisualC和OpenGL語(yǔ)言為工具，設(shè)計(jì)了一個(gè)完整的實(shí)驗(yàn)平臺(tái)，包括STLViewerexe主程序和五個(gè)動(dòng)態(tài)鏈接庫(kù)。從數(shù)據(jù)生成，采集，加工，算法實(shí)現(xiàn)，到最后的結(jié)果顯示，整個(gè)平臺(tái)都是完全按照標(biāo)準(zhǔn)的CAD軟件設(shè)

4、計(jì)模式開(kāi)發(fā)，使得這個(gè)平臺(tái)具有了一定的實(shí)用性和可操作性。3)完成了實(shí)驗(yàn)數(shù)據(jù)的加工，比較，改進(jìn)算法相對(duì)于QuickHuU算法在效率上平均提升了20％。關(guān)鍵詞：構(gòu)造三維凸包；二次極值；隨機(jī)增量算法；lIlllllIlrllllllIIllIIfY1868663maneuverability3)CompletetheprocessingofexperimentaldataandcomparisonComparingwithQuickHull，t