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

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

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

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

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