滑斌杰，林立忠，柴忠良

石家莊學院 計算機系，石家莊 050035

粗糙域Voronoi圖離散生成算法研究

滑斌杰，林立忠，柴忠良

石家莊學院 計算機系，石家莊 050035

1 引言

Voronoi圖是計算幾何的一個重要分支，是一種關于空間臨近關系的重要的數(shù)據(jù)結構，它在幾何形體重構、計算機圖形學、圖形圖像處理與模式識別、地學、物理、化學、生物學、地質、氣象以及城市規(guī)劃等領域有著廣泛的應用，隨著計算機技術的普及與發(fā)展，Voronoi圖的應用領域也在不斷擴大[1-2]。

在Voronoi圖的研究方面，有兩個主要方向，一是根據(jù)不同應用在母點（生成元）形狀和生成面上的擴展，二是Voronoi圖生成算法的研究。在母點和生成面的擴展方面有：線段Voronoi圖、面Voronoi圖、球面Voronoi圖及其加權Voronoi圖，流域Voronoi圖、斜面Voronoi圖和障礙Voronoi圖等[2-6]。Voronoi圖生成算法很多，總體上分為兩類：矢量法和離散法。矢量法有對偶生成法、增量法、分治法、平面掃描法等。相對于離散生成法，矢量法生成Voronoi圖算法和數(shù)據(jù)結構比較復雜，目前對Voronoi圖生成算法的研究主要是離散法的研究。

Voronoi圖離散生成算法的核心問題是生成面上兩點間距離的計算。典型的距離有Euclid距離、Manhattan距離等，這些距離計算的前提是生成面上任意點對距離的影響權相等，即距離僅由兩點的空間位置確定，而不考慮其他屬性對距離的影響。在實際的應用中（例如地學、城市規(guī)劃等），空間點所承載的信息量除了空間位置外，還有高程、人口密度、交通狀況等因素，這些因素都會對Voronoi圖的離散生成中距離的計算產(chǎn)生影響。

本文給出了粗糙域Voronoi圖的定義并對其生成算法進行了研究，實現(xiàn)了粗糙域Voronoi圖的離散生成，同時對粗糙域Voronoi圖在母點加權、生成面障礙等方面的擴展提供了有價值的思路。

2 粗糙域Voronoi圖

2.1 Voronoi圖的數(shù)學定義

Voronoi圖是根據(jù)已知點集（母點）對生成面的一種分割，其數(shù)學定義如下[2]：

定義1設 pi(i=1，2，…，n)為二維歐式空間（平面）上的n個互不相同的點。將由：

所給出的對平面的分割，稱為以 pi(i=1，2，…，n)為母點（或生成元）的Voronoi圖，簡稱V-圖，其中d(p，pi)為點 p與 pi間的Euclid距離。

在V-圖中，生成面被母點間的垂直平分線（段）分割成不相交的n各部分，如圖1所示。生成面的分割線稱為V-邊，V-邊的交點稱為V-點，包含母點的不多于n-1條邊的凸多邊形區(qū)域稱為母點的V-域。V-邊是兩母點間垂直平分線的一部分。

圖1 Voronoi圖

2.2 粗糙域的定義

一般V-圖的生成面為普通二維歐式平面（D），平面上兩點間的距離是兩點空間位置的函數(shù)，即

而在實際的應用中（例如地學、城市規(guī)劃等），空間點所承載的信息（空間點的某屬性）是復雜的，這些信息可能對兩點間距離的計算產(chǎn)生影響，這時，兩點間的距離看成是包含兩點空間位置在內的各種影響因素的函數(shù)，即

其中，w1、w2分別為 p1、p2兩點對距離的影響權。由此給出粗糙域的定義。

定義2在某二維區(qū)域D內，若各點所承載的某屬性值不同，稱為區(qū)域D在此屬性值上是粗糙的，把區(qū)域D稱為基于此屬性值的粗糙域。

圖2是模擬的基于某屬性值的粗糙域，粗糙域中各點的屬性值由各點的灰度值表示。

2.3 粗糙域V-圖的數(shù)學定義

生成面基于粗糙域的V-圖稱為粗糙域V-圖。由于粗糙域中空間點對距離的影響權不同，所以在V-圖的定義中以帶權距離W(p，pi)來代替歐式距離d(p，pi)。W(p，pi)為基于某種搜索算法所獲得的路徑。根據(jù)V-圖的一般定義，可知W(p，pi)為 p和 pi兩點間的最優(yōu)路徑。粗糙域V-圖數(shù)學定義如下：

定義3設 pi(i=1，2，…，n)為粗糙域上的n個互不相同的點。將由：

圖2 模擬的基于某種屬性值的粗糙域（粒度8×8）

所給出的對粗糙域的分割，稱為以 pi(i=1，2，…，n)為母點（生成元）的粗糙域V-圖。在粗糙域V-圖中，粗糙域被分割成不相交的n個部分，由于受粗糙域粗糙特性的影響，V-邊為不規(guī)則曲線（段），如圖3所示。

圖3 粗糙域V-圖

3 粗糙域Voronoi圖的離散生成算法

3.1 基本思路

根據(jù)粗糙域V-圖的數(shù)學定義可知，某母點的V-域是到本母點的最優(yōu)路徑長度比到其他母點的最優(yōu)路徑長度都短的點的集合。對于粗糙域上任意點p，如果能使用某種最優(yōu)路徑搜索算法，計算出點p到所有母點的最優(yōu)路徑，點p就屬于最優(yōu)路徑最短的母點的V-域。所以粗糙域V-圖的離散生成算法的關鍵是低復雜度且高效的最優(yōu)路徑搜索算法的選擇。

A*算法是目前最流行的最優(yōu)路徑搜索算法[7]，在粗糙域Voronoi圖的離散生成算法中，最優(yōu)路徑搜索算法選擇A*算法。

3.2 A＊算法

A*算法[8-10]是在寬度優(yōu)先搜索基礎上的一種啟發(fā)式有序搜索算法。所謂啟發(fā)式搜索就是在狀態(tài)空間中，對每一個搜索的位置進行評估，得到最好的位置，再從這個位置向下進行搜索直到目標。在啟發(fā)式搜索中，對位置的評估用估價函數(shù)來表示。A*算法的算法思想可以表示為：假設有一個估價函數(shù)F，它是狀態(tài)空間中節(jié)點狀態(tài)的實值函數(shù)。在最優(yōu)路徑搜索過程中，并不是把所有可能的節(jié)點全部展開，而是利用這個特定的估價函數(shù)F對所有沒有展開的節(jié)點逐個進行評估，從而找出最可能被展開的節(jié)點將其展開，直到找到目標節(jié)點為止。估價函數(shù)的定義如下：

其中，F(xiàn)(n)為起始節(jié)點到目標節(jié)點間通過節(jié)點n的最優(yōu)路徑的代價。g(n)為從起始節(jié)點到節(jié)點n的最優(yōu)路徑代價。h(n)為節(jié)點n到目標節(jié)點的代價估計。

在最優(yōu)路徑搜索過程中，為了增強估價函數(shù)的適應性和搜索效率，常常將估價函數(shù)乘以一權值W，即h*=h×W。權值W的確定沒有明確的規(guī)則，往往根據(jù)經(jīng)驗或經(jīng)過大量實驗來確定。這樣的不利結果是對W的精確度把握不夠，不能在低復雜度條件下獲得路徑的最優(yōu)結果，無法滿足實時最優(yōu)路徑搜索的需求。而在粗糙域V-圖的離散生成算法中，要進行多次最優(yōu)路徑搜索，所以快速、準確確定估價函數(shù)的最優(yōu)權十分重要。

3.3 A＊算法估價函數(shù)最優(yōu)權值的確定

基于粗糙域的最短路徑與粗糙域的粗糙特性有關。在進行最優(yōu)路徑搜索時，估價函數(shù)權值的選取直接影響所得的結果路徑是否最優(yōu)和算法的效率。為了能夠快速確定估價函數(shù)的最優(yōu)權值，進行了以下實驗：選取不同范圍、不同粗糙程度、不同粗糙分布的區(qū)域，通過制定不同的估價函數(shù)、改變估價函數(shù)的權值計算最優(yōu)路徑，通過分析，確定最優(yōu)權值與粗糙區(qū)域粗糙特性的關系。

3.3.1 算法步驟

（1）計算機模擬基于某種屬性值的粗糙域，用灰度值表示屬性值（如圖2）。

（2）在粗糙域上確定起始點和終止點。

（3）確定估價函數(shù)。

（4）給定某權值W，進行最短路徑搜索，記錄搜索結果，并記錄搜索的點數(shù)和路徑的總長度。

（5）改變權值W，重復（4）。

（6）改變估價函數(shù)，重復（4）、（5）。

（7）改變粗糙域和起始點和終止點，重復（2）～（5）。

3.3.2 A＊算法估價函數(shù)權值與粗糙域粗糙特性的關系

通過實驗，對A*算法估價函數(shù)權值與粗糙域粗糙特性的關系進行驗證，以下是一組典型實驗數(shù)據(jù)。

以8×8粒度、屬性值波動范圍在0～200產(chǎn)生隨機粗糙域，估價函數(shù)采用Manhattan距離。實驗中估價函數(shù)的權值取值1～50，進行50次最優(yōu)路徑搜索。圖4是實驗采取不同權值時A*算法最優(yōu)路徑所搜情況。圖4（a）～（f）分別是估價函數(shù)權值為1、10、20、30、40、50時的最短路徑。

表1是實驗中估價函數(shù)取不同權值進行最優(yōu)路徑搜索的詳細數(shù)據(jù)。W為估價函數(shù)所取的權值，L為最優(yōu)路徑的長度，SP為搜索的節(jié)點數(shù)。

圖5為不同權值最優(yōu)路徑搜索的詳細數(shù)據(jù)變化趨勢。X軸表示權重，Y軸表示在一定權值下計算的路徑長度和搜索點數(shù)。

圖4 不同權值下最短路徑情況

表1 不同權值最優(yōu)路徑搜索的詳細數(shù)據(jù)

圖5 不同權值最優(yōu)路徑搜索的詳細數(shù)據(jù)變化趨勢

根據(jù)實驗結果，分析如下：

（1）從圖5中看到，隨著估價函數(shù)權值W增大，最短路徑的長度先保持不變后逐漸增大，而搜索點數(shù)逐漸減小。同時圖4也說明，隨著權值W的增大，在狀態(tài)空間的搜索范圍逐漸減小，搜索范圍在從起點到終點的方向上有逐漸增大的趨向性。這說明了：在實驗中所選擇的估價函數(shù)是有效的，并且最優(yōu)路徑跟估價函數(shù)的權值相關；選擇合適的權值能夠在結果路徑保持最優(yōu)的情況下，大大降低算法的搜索點數(shù)，從而減小算法的復雜度。

（2）在表1中，W=19是最短路徑的長度逐漸增大的轉折點，轉折點對應的權值為估價函數(shù)的最優(yōu)權，其值接近狀態(tài)空間節(jié)點屬性值絕對差的1/10。大量實驗結果表明，A*算法估價函數(shù)最優(yōu)權值與粗糙域粗糙特性正相關，最優(yōu)權值均約為節(jié)點屬性值絕對差的1/10。

（3）根據(jù)結論（2），在實時性要求較高的應用情境下，可以根據(jù)已獲得的狀態(tài)空間節(jié)點屬性值的絕對差來確定估價函數(shù)的權值W。同時考慮不同應用對路徑是否最優(yōu)和算法復雜度的要求，在最優(yōu)權值周圍一小鄰域內調整W的取值。

圖6 一般V-圖

圖7 粗糙域V-圖

圖8 粗糙域Voronoi圖小區(qū)域誤差

3.4 粗糙域Voronoi圖的離散生成算法描述

根據(jù)粗糙域V-圖的數(shù)學定義和A*算法估價函數(shù)權值與粗糙域粗糙特性的關系，給出粗糙域V-圖離散生成算法如下：

（1）在粗糙域上設置母點位置和相應V-域顏色。

（2）對粗糙域上的點p，根據(jù)選定的最優(yōu)路徑搜索算法，計算p到各母點的最優(yōu)路徑。

①計算p與母點作為矩形的角點，計算矩形范圍內各點的灰度絕對差。

②根據(jù)矩形區(qū)域灰度絕對差確定A*算法估價函數(shù)權值。

③A*算法進行最優(yōu)路徑搜索。

④對所有母點重復①、②、③。

（3）比較 p點到各母點最優(yōu)路徑的大小，確定 p點屬于最優(yōu)路徑最小的母點的V-域，并將 p設定為本母點V-域的顏色。

（4）重復（2）、（3），直到粗糙域上所有點計算完畢。

（5）根據(jù)所設定的各母點V-域不同的顏色值，抽取V-邊和V-域。

4 實驗結果及分析

在MS.NET 2005平臺下開發(fā)程序，實現(xiàn)了粗糙域V-圖的離散生成。系統(tǒng)硬件配置為：Inter?CoreTM2 Duo CPU P8600@2.4 GHz；2.0 GB RAM。

圖6是不考慮其粗糙特性生成的一般V-圖，圖7是生成的粗糙域V-圖，與一般V圖相比，粗糙域V-圖的V-邊為任意曲線（段）且V-邊的形狀與母點的位置和粗糙域特性相關。

由A*算法估價函數(shù)最優(yōu)權值與粗糙域粗糙特性的關系（2.3節(jié)），根據(jù)粗糙域特性獲得估價函數(shù)的最優(yōu)權值，使得A*算法的復雜度遠小于O(n2)，對于母點個數(shù)為M的粗糙域V-圖的離散生成，其算法復雜度則遠小于O(n2×M)。

表2是不同母點個數(shù)，在不同大小、隨機生成的粗糙生成面下，使用A*算法和優(yōu)化A*算法生成粗糙域V-圖的生成時間及優(yōu)化率的比較。從結果數(shù)據(jù)可以看出，在粗糙域V-圖離散生成的過程中，由于采用了優(yōu)化算法，獲得了A*算法估價函數(shù)的最優(yōu)權值，使得進行每一次最優(yōu)路徑搜索的時間復雜度降低，最終導致粗糙域V-圖離散生成算法復雜度明顯降低。

表2 粗糙域V-圖的生成時間及優(yōu)化率比較

在粗糙域V-圖離散生成過程中，根據(jù)3.3.2節(jié)中所述確定最優(yōu)權值的方法，雖然算法的時間復雜度大大降低，但有時不能獲得路徑的最優(yōu)解，這就有可能導致在V-邊附近某些區(qū)域在V-域歸屬上的誤判現(xiàn)象。如圖8所示，圖中中間方格部分被判定為屬于V域①。

解決這種誤判現(xiàn)象的方法是確定最優(yōu)權值W時，令其減去一小常量ε(ε＞0)，這樣算法的時間復雜度相對有所提高，但是能夠保證得到最短路徑的最優(yōu)解，從而消除V-域的誤判。

5 結論

本文提出了粗糙域V-圖的概念，為了高效實現(xiàn)粗糙域V-圖的離散生成，對粗糙域下A*算法估價函數(shù)最優(yōu)權值進行了研究，給出了粗糙域V-圖的離散生成算法并對算法進行了驗證，算法的實現(xiàn)拓展了V-圖在復雜生成面條件下的應用。例如，在商業(yè)選址中，人口密度分布，同行業(yè)競爭分布，交通狀況等都是應考慮的因素，在選址過程中，可以根據(jù)各種因素構造粗糙域，并在此基礎上進行商業(yè)選址分析。同時本算法沒有考慮母點加權、生成面障礙等更為復雜的情況，需要在此方面做進一步的研究。

[1]劉金義，劉爽.Voronoi圖應用綜述[J].工程圖學學報，2004（2）：125-132.

[2]張有會.加權Voronoi圖畫法的研究[J].計算機科學，2001，28（6）：126-130.

[3]張有會.線段加權的Voronoi圖[J].計算機學報，1995，18（11）：822-829.

[4]Aichholzer O，Chen D Z.Skew Voronoi diagrams[J].International Journal of Computational Geometry and Application，1999，9（3）：235-246.

[5]NishidaT，SugiharaK.Stablemarker-particlemethod for the Voronoi diagram in a flow field[J].Journal of Computational and Applied Mathematics，2007，2（2）：377-391.

[6]趙仁亮.基于Voronoi圖的GIS空間關系計算[M].北京：測繪出版社，2006：39-53.

[7]Nilsson N J.人工智能[M].鄭扣根，譯.北京：機械工業(yè)出版社，2000.

[8]楊素瓊.基于A*算法的地圖路徑搜索的實現(xiàn)[J].鐵路計算機應用，2000（4）：24-27.

[9]史輝.A*算法的改進及其在路徑規(guī)劃中的應用[J].測繪與空間地理信息，2009，32（6）：208-211.

[10]鐘敏.A*算法估價函數(shù)的特性分析[J].武漢工程職業(yè)技術學院學報，2006，18（2）：31-33.

HUA Binjie,LIN Lizhong,CHAI Zhongliang

Department of Computer,Shijiazhuang University,Shijiazhuang 050035,China

Voronoi diagram is an important branch of computational geometry and Voronoi diagrams based rough area are extensions of Voronoi diagrams.In this paper,a conception of Voronoi diagram based rough area is proposed and it is generated with the minimum distance between points of forming face and mother-points which is calculated out using A-star algorithm.For reducing the complexity of generating algorithm,a research on relation between weight of evaluation function of A-star algorithm and character of rough area is launched.Experimental results show that the optimal weight of evaluation function positively correlates with the roughness characteristics of rough area.Based on this,the optimal weight of A-star algorithm is obtained and the complexity of generating algorithm of Voronoi diagrams based rough area is remarkably reduced.

Voronoi diagram;rough area;A-star algorithm;evaluation function;optimal weight

Voronoi圖是計算幾何的一個重要分支，粗糙域Voronoi圖是Voronoi圖概念在復雜生成面上的擴展。提出了粗糙域Voronoi圖的概念并利用A*算法計算生成面上點與各母點的最短路徑對其進行離散生成。為了降低粗糙域Voronoi圖離散生成算法的復雜度，對粗糙域下A*算法估價函數(shù)權值與粗糙域粗糙特性的關系進行了深入探索。實驗結果表明，A*算法估價函數(shù)權值與粗糙域粗糙特性正相關，并以此獲得A*算法估價函數(shù)的最優(yōu)權，大大降低了粗糙域Voronoi圖離散生成算法的復雜度。

Voronoi圖；粗糙域；A*算法；估價函數(shù)；最優(yōu)權

A

TP391

10.3778/j.issn.1002-8331.1203-0245

HUA Binjie,LIN Lizhong,CHAI Zhongliang.Research on discrete generation algorithm of Voronoi diagram based rough area.Computer Engineering and Applications,2013,49（23）：191-194.

河北省科技型中小企業(yè)技術創(chuàng)新基金（No.11C1303111004）。

滑斌杰（1974—），男，工程師，主要研究方向：圖形圖像處理；林立忠（1964—），男，副教授，主要研究方向：軟件工程；柴忠良（1961—），男，高級工程師，主要研究方向：人工智能、模式識別。E-mail：hbj.king.1974@163.com

2012-03-13

2012-06-25

1002-8331（2013）23-0191-04

◎信號處理◎