快速三維凸包算法的研究與改進.pdf

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

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

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

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