障礙Voronoi圖性質(zhì)及其應(yīng)用研究.pdf

1、自90年代以來(lái),Voronoi圖應(yīng)用在各個(gè)領(lǐng)域,Voronoi圖不僅在計(jì)算幾何學(xué)的方面上扮演重要的角色,而且在人們現(xiàn)實(shí)生活中的很多地方也是發(fā)揮著重要的作用,可以說(shuō)它是一種非常有用、重要的圖形。
　　 隨著計(jì)算機(jī)技術(shù)的普及和發(fā)展,Voronoi圖的應(yīng)用范圍也在不斷擴(kuò)大,利用Voronoi圖的理論可有效地解決最近點(diǎn)的查找、求最大空?qǐng)A、求最小樹(shù)、求,n個(gè)平面點(diǎn)的凸包等問(wèn)題。通常意義下的Voronoi圖是以歐氏距離為度量,對(duì)平面區(qū)域進(jìn)行

2、的一種分割,這是一種不考慮障礙物的理想模式。
　　 為擴(kuò)大Voronoi圖的應(yīng)用領(lǐng)域,本文對(duì)Voronoi圖進(jìn)行了擴(kuò)展,主要研究障礙Voronoi圖的生成算法及應(yīng)用。首先從Voronoi圖的定義出發(fā),將Voronoi圖的性質(zhì)及生成算進(jìn)行全面的歸納和總結(jié),進(jìn)而提出了基于Voronoi圖的分塊劃分空間的算法,將二維或多維空間劃分為具有周期性的分塊區(qū)域空間,具有廣泛的應(yīng)用價(jià)值。
　　 通過(guò)對(duì)Voronoi圖的全面研究,將Vor

3、onoi圖推廣到障礙環(huán)境中,給出了障礙Voronoi圖的概念,定義了城市中的障礙Voronoi圖,包括城市距離和障礙城市距離。并對(duì)障礙Voronoi圖的各種生成算法進(jìn)行了詳細(xì)的研究,比較各種算法的優(yōu)缺點(diǎn),得出較好的生成障礙Voronoi圖的算法。最后將障礙Voronoi圖與可視圖有效結(jié)合,應(yīng)用到障礙環(huán)境中的最短路徑規(guī)劃,給出可視Voronoi圖的算法?？捎糜谌我忾g隙值c、任意起點(diǎn)和終點(diǎn)間的有效路徑規(guī)劃,時(shí)間復(fù)雜度為O(n2 log n)