本文關(guān)鍵詞：高維Voronoi算法研究　出處：《華南理工大學》2016年碩士論文　論文類型：學位論文

  更多相關(guān)文章： 高維 Voronoi Delaunay 增量插入算法 qudatree 廣度優(yōu)先搜索 均勻網(wǎng)格

【摘要】：Voronoi圖乃是計算幾何的一個重要問題,被應(yīng)用在很多重要的領(lǐng)域。Voronoi圖它擁有很多優(yōu)良性質(zhì),包括最鄰近性質(zhì)、區(qū)域控制性質(zhì)。這些優(yōu)良性質(zhì)使其被廣泛應(yīng)用的2維平面和3維空間的領(lǐng)域,包括GIS、數(shù)據(jù)索引、路徑規(guī)劃、城市規(guī)劃等。平面點的Voronoi算法已經(jīng)非常多,有如增量構(gòu)建法、增量插入法、分治法、和掃描線算法等精確算法,還有使用柵格和距離變換技術(shù)的近似算法。但是高維度的Voronoi圖并沒有像平面Voronoi圖一樣的直接求解算法。因此本文就高維Voronoi算法進行研究。高維Voronoi圖一般使用間接求解法,如利用對偶Delaunay圖、利用更高維的凸包或者半空間交。本文詳細闡述和證明了Voronoi圖和其他三者之間的關(guān)系,并介紹了高維Delaunay、高維凸包、高維半空間交的算法。本文詳細闡述了Watson提出的利用對偶Delaunay求解高維Voronoi算法的實現(xiàn)細節(jié),論述了算法實現(xiàn)時存在的問題,并針對這些問題提出了解決方案,如超球外心計算方法。重點對算法主要耗時點“沖突單形查找”進行研究。闡述了多個優(yōu)化方案,包括1)利用鄰接關(guān)系和廣度優(yōu)先搜索策略,2)記錄歷史單形的Delaunay Tree,3)均勻網(wǎng)格索引,4) Quadtree動態(tài)索引,5)單形共同頂點索引。利用以上優(yōu)化可以快速定位首個沖突單形,然后查找利用廣度優(yōu)先搜索找到剩余沖突單形,大大提高程序效率。最后提出外存優(yōu)化方案,解決了高維計算時內(nèi)存不足問題和結(jié)果持久化問題。最后進行了多個對比實驗,比較了筆者實現(xiàn)的高維Watson算法與已有計算幾何庫的高維Delaunay實現(xiàn)的性能差別。實驗數(shù)據(jù)表明本文提出的查找優(yōu)化帶來的提升效果明顯,而外存優(yōu)化方案使程序只使用少量的內(nèi)存就能應(yīng)對更大的數(shù)據(jù)量。
【學位授予單位】：華南理工大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：O18;TP391.7
，

本文編號：1327026