障礙Voronoi圖性質及其應用研究.pdf

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

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

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