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

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

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

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