基于Voronoi圖的凸多邊形快速求交與距離計算方法.pdf

1、　　距離計算、多邊形求交等問題是計算機(jī)輔助設(shè)計與制造(CAD/CAM)、計算幾何、機(jī)器人和自動化、工程分析、計算機(jī)圖形學(xué)、虛擬現(xiàn)實(shí)等領(lǐng)域的基礎(chǔ)問題，是解決碰撞檢測、路徑規(guī)劃、裁剪、消隱等問題常用的基礎(chǔ)方法。其算法的優(yōu)劣，也影響著相應(yīng)應(yīng)用算法。由于凸多邊形/凸多面體具有良好的凸性，相應(yīng)算法的構(gòu)造簡單，所以對于復(fù)雜的物體，往往分解成凸多邊形/凸多面體，進(jìn)行復(fù)雜問題的求解。
　　因此，本文主要研究兩個凸多邊形的快速求交與距離計算方法。通

2、過對多邊形Voronoi圖性質(zhì)的深入分析，利用Voronoi圖所記錄的空間連貫性和最鄰近性質(zhì)，設(shè)計實(shí)現(xiàn)了基于凸多邊形的外部Voronoi圖的兩個凸多邊形的快速求交和兩個分離凸多邊形的快速距離計算方法。算法簡單、易于理解和編程，速度快?？蓱?yīng)用于數(shù)字博物館等室內(nèi)三維場景的漫游，用于路徑規(guī)劃、碰撞檢測、文物布展等方面。
　　本文所做的主要工作與貢獻(xiàn)如下：
　　1.給出了一個基于Voronoi圖的凸多邊形求交算法。該算法是基于凸多邊

3、形的外部Voronoi圖來對兩多邊形邊界進(jìn)行遍歷。此算法在最壞的情況下的時間復(fù)雜度是D(n+m)，算法速度較快，易于理解和編程實(shí)現(xiàn)。此外，本文的算法不僅能發(fā)現(xiàn)兩個凸多邊形的所有交點(diǎn)，同時還能報告出兩個凸多邊形的位置關(guān)系。
　　2.設(shè)計實(shí)現(xiàn)了一種基于Voronoi圖的計算兩分離凸多邊形間最短距離的算法。其時間復(fù)雜度為D(log m+log n)，同時不需要任何預(yù)處理和特殊的存儲結(jié)構(gòu)，易于編程與實(shí)現(xiàn)。
　　3.給出了本文兩個算法