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

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

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

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