Voronoi圖混合柵格算法改進(jìn)研究

沙俊淞, 王秋實(shí), 張學(xué)軍, 王斌君

(1.中國(guó)人民公安大學(xué)信息技術(shù)與網(wǎng)絡(luò)安全學(xué)院， 北京 100038； 2.公安部第一研究所物聯(lián)網(wǎng)部， 北京 100048)

0 引言

Voronoi圖是計(jì)算幾何的一個(gè)重要分支。計(jì)算幾何中的voronoi圖常被用于解決地理學(xué)、氣象學(xué)、移動(dòng)通信等領(lǐng)域的選址優(yōu)化、空間劃分、路徑規(guī)劃等問(wèn)題。此外Voronoi圖在考古、生態(tài)研究、城市規(guī)劃等領(lǐng)域也有廣泛的應(yīng)用[1]。在公安領(lǐng)域內(nèi)，通過(guò)構(gòu)造關(guān)于基站分析的分區(qū)加權(quán)Voronoi圖，有助于公安機(jī)關(guān)更加準(zhǔn)確地確定偵查范圍。

隨著社會(huì)的高速發(fā)展，普通的Voronoi圖已經(jīng)無(wú)法滿(mǎn)足實(shí)際應(yīng)用的需要。所以，研究者們?cè)赩oronoi圖的基礎(chǔ)上擴(kuò)展出了加權(quán)Voronoi圖[2]、分區(qū)加權(quán)Voronoi圖[3]等。

對(duì)于分區(qū)加權(quán)Voronoi圖，主要有兩種柵格生成算法：逐點(diǎn)掃描法[4]和模擬生長(zhǎng)法[5]。逐點(diǎn)掃描法的基本思想是：通過(guò)計(jì)算平面上所有點(diǎn)與生成元的距離來(lái)生成Voronoi圖。后人根據(jù)分區(qū)加權(quán)Voronoi圖的定義，提出了適用于分區(qū)加權(quán)Voronoi圖的逐點(diǎn)掃描算法[6]。模擬生長(zhǎng)法的基本思想是：將空間生長(zhǎng)目標(biāo)作為圓心，不斷向四周擴(kuò)張占領(lǐng)空白像素，直到所有區(qū)域被覆蓋。根據(jù)分區(qū)加權(quán)Voronoi圖的定義，馬立玲在原方法的基礎(chǔ)上，提出了分區(qū)加權(quán)Voronoi圖的模擬生長(zhǎng)算法[3]。

1 基本概念和算法介紹

1.1 基本概念

1.1.1 Voronoi圖

定義1：設(shè)S={p1,p2, …,pn}為平面上n個(gè)互不相同的點(diǎn)集，由：

Vn(pi)={p|d(p,pi)

所給出對(duì)平面的分割，稱(chēng)為以pi(i=1,2,…,n)為生成元(或母點(diǎn))的Voronoi圖，簡(jiǎn)稱(chēng)Voronoi圖。其中d(p,pi)稱(chēng)為p和pi之間的Euclid距離。區(qū)域V(pi)稱(chēng)為pi的Voronoi區(qū)域[4]。同時(shí)，在pi的Voronoi區(qū)域內(nèi)的所有點(diǎn)到pi的距離比到其他母點(diǎn)的距離都更近。圖1是一個(gè)Voronoi圖的示例。

圖1 Voronoi圖

1.1.2 加權(quán)Voronoi圖

定義2：設(shè)S={p1,p2, …,pn}為平面上n個(gè)互不相同的點(diǎn)集，對(duì)每個(gè)生成元p1,p2, …,pn賦以非負(fù)實(shí)數(shù)權(quán)重λ1,λ2, …,λn。稱(chēng)D(p,pi)=d(p-pi)/λi為p和pi之間的加權(quán)距離。稱(chēng)

(i,j=1,2,…,n)

為點(diǎn)pi的權(quán)重為λi的加權(quán)Voronoi區(qū)域。將V(pi，λi)(i=1, 2, …,n)及其邊界，稱(chēng)為以p1,p2, …,pn為生成元(或母點(diǎn)),以λ1,λ2, …,λn為權(quán)重的加權(quán)voronoi圖[4]。圖2是加權(quán)voronoi圖的示例，圖中的數(shù)字代表每個(gè)生成元的權(quán)重。

圖2 加權(quán)Voronoi圖

1.1.3 分區(qū)加權(quán)Voronoi圖

定義3：設(shè)S={p1,p2, …,pn}為平面上n個(gè)互不相同的點(diǎn)集，對(duì)每個(gè)生成元pi，以pi為原點(diǎn)，水平向右為坐標(biāo)軸的正向，建立極坐標(biāo)系，將生成元pi周?chē)鷧^(qū)域分為mi個(gè)扇區(qū)，以θ=αij(j=1,2,3,…,mi)為扇區(qū)分界線(xiàn)，其中0≤αi1<αi2<αi3…≤2π，并給每個(gè)扇區(qū)賦以權(quán)重λij(j=1,2,3…mi)。稱(chēng)

(i,j=1,2,…,n)

(當(dāng)j≠mi時(shí)，p在射線(xiàn)θ=αij與θ=αi(j+1)之間；當(dāng)j=mi時(shí),p在射線(xiàn)θ=αi1與θ=αimi之間)為點(diǎn)p在第j扇區(qū)權(quán)重為λij的Voronoi區(qū)域。將V(pi,αij,λij) (j=1,2,3…mi) (i=1,2,3…n)及其邊界稱(chēng)為以pi(i=1,2,3…n)為生成元或母點(diǎn)，以(λi1，λi2，…λim)(i=1,2,3…n)為相關(guān)扇區(qū)權(quán)重的分扇區(qū)加權(quán)Voronoi圖，簡(jiǎn)稱(chēng)分區(qū)加權(quán)Voronoi圖[3]，圖3是分區(qū)加權(quán)Voronoi圖的示例。

圖3 分區(qū)加權(quán)Voronoi圖

1.2 混合柵格算法

通過(guò)研究發(fā)現(xiàn)：逐點(diǎn)掃描法結(jié)果準(zhǔn)確，但效率較低，一般用于生成元數(shù)量少且范圍和邊界要求嚴(yán)格的應(yīng)用領(lǐng)域；而對(duì)于生成元數(shù)量較多，但范圍和邊界要求不嚴(yán)格的應(yīng)用領(lǐng)域，則一般采用效率更高但結(jié)果不夠準(zhǔn)確的模擬生長(zhǎng)法。

針對(duì)逐點(diǎn)掃描法和模擬生長(zhǎng)法的優(yōu)缺點(diǎn)。王斌君教授提出了一種生成分區(qū)加權(quán)Voronoi圖的混合柵格算法。其基本思想是：對(duì)于平面上的生成元，首先對(duì)生成元進(jìn)行預(yù)處理，預(yù)處理環(huán)節(jié)是通過(guò)預(yù)先擴(kuò)展一定大小的覆蓋區(qū)域，相當(dāng)于每個(gè)生成向外擴(kuò)展一大步；然后，對(duì)每個(gè)生成元扇區(qū)擴(kuò)展的覆蓋區(qū)域按照特點(diǎn)的顏色著色，同時(shí)將相交區(qū)域內(nèi)的點(diǎn)置白；最后，對(duì)剩余像素和相交區(qū)域按照原逐點(diǎn)掃描法進(jìn)行處理，生成分區(qū)加權(quán)Voronoi圖。

混合柵格算法在提高效率的同時(shí)，又保證了精度，可以很好的滿(mǎn)足生成元數(shù)量多且對(duì)范圍和邊界要求嚴(yán)格的領(lǐng)域。但是，該算法在重疊區(qū)域處理方面不夠精細(xì)，增加了算法的時(shí)間復(fù)雜度的描述。所以，針對(duì)這個(gè)問(wèn)題本文提出了一種改進(jìn)算法。

2 改進(jìn)的混合柵格算法

在文獻(xiàn)[6]的混合柵格算法中，對(duì)生成元扇區(qū)進(jìn)行預(yù)處理的相交部分用逐點(diǎn)掃描算法進(jìn)行處理雖然正確，但存在冗余。這是因?yàn)?，重疊區(qū)域點(diǎn)的隸屬問(wèn)題不需要按照原始的逐點(diǎn)掃描法計(jì)算重疊區(qū)域點(diǎn)與所有生成元之間的距離，只需與曾覆蓋該點(diǎn)的生成元扇區(qū)進(jìn)行計(jì)算即可。通過(guò)這個(gè)方法可進(jìn)一步降低混合柵格算法的時(shí)間復(fù)雜度，提高算法效率。

2.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

算法涉及的主要數(shù)據(jù)結(jié)構(gòu)是生成元和重疊區(qū)域點(diǎn)的數(shù)據(jù)結(jié)構(gòu)：Generator記錄各生成元的二維坐標(biāo)、各扇區(qū)起始角度、權(quán)重和顏色等信息；AllGen是一個(gè)包括所有生成元的數(shù)組；spot記錄離每個(gè)重疊區(qū)域內(nèi)點(diǎn)加權(quán)距離最近的生成元編號(hào)和扇區(qū)編號(hào)，Overlap[,]是一個(gè)包括平面上所有點(diǎn)的二維數(shù)組。

structGenerator

{

x; ∥生成元x坐標(biāo)

y; ∥生成元y坐標(biāo)

w[]; ∥生成元扇區(qū)權(quán)重

a[]; ∥生成元扇區(qū)角度

RGB[][3];∥生成元扇區(qū)顏色

} AllGen[];

Struct spot

{

I; ∥生成元編號(hào)

j; ∥生成元扇區(qū)號(hào)

}OverLap[,]

2.2 算法設(shè)計(jì)

算法1：重疊區(qū)域隸屬計(jì)算算法

輸入:當(dāng)前生成元編號(hào)CurI，當(dāng)前生成元扇區(qū)號(hào)CurJ，重疊點(diǎn)坐標(biāo)(CurX,CurY)

輸出:null

S1:∥初始化

OldI = OverLap[CurX,CurY].i;

OldX = AllGen[ OldI].x;

OldY = AllGen[ OldI].y;

OldJ = OverLap[CurX,CurY].j;

OldW = AllGen[OldI].w[OldJ];

CurW = AllGen[CurI].w[CurJ];

S2:∥計(jì)算(CurX,CurY)到兩生成元的加權(quán)距離

OldD=(float)(Math.Sqrt((CurX-OldX)·(CurX-OldX)+(CurY-OldY2)·(CurY-OldY)))/OldW;

CurD=(float)(Math.Sqrt((CurX-AllGen[CurI]·x)·(CurX-AllGen[CurI].x)+(CurY-AllGen[CurI].y)·(CurY-AllGen[CurI].y)))/CurW;

S3:if (CurD

將CurI和CurJ存入OverLap[CurX,CurY];

}

S4:結(jié)束

經(jīng)典的區(qū)域填充算法主要有兩種，一種是通過(guò)確定橫跨區(qū)域的掃描線(xiàn)的覆蓋間隔來(lái)填充的掃描線(xiàn)算法[7]，另一種是從給定的位置開(kāi)始填充直到指定的邊界為止的種子填充算法[8]。而本算法涉及的填充域著色是一個(gè)關(guān)于扇區(qū)的填充問(wèn)題。所以，設(shè)計(jì)了一種簡(jiǎn)單而高效的扇區(qū)填充域算法。

首先，考慮簡(jiǎn)單情況，即僅需要填充的扇區(qū)只在某一個(gè)象限。如圖4所示的4種情況，分別對(duì)應(yīng)算法2.1、算法2.2、算法2.3和算法2.4。

圖4 單象限的扇區(qū)

算法2.1：填充扇區(qū)只在第一象限

輸入:圓心(x1、y1)，角度α1，角度α2，半徑r，顏色c[3]

輸出:對(duì)給定的第一象限扇區(qū)按顏色c填充著色，重復(fù)區(qū)域調(diào)用算法1

S1: if (α1==0) 從(x1,y1)到(x1+r,y1)畫(huà)線(xiàn); ∥畫(huà)線(xiàn)就是在兩點(diǎn)之間依次對(duì)點(diǎn)著色，如果該點(diǎn)是白色則將其置為顏色c，若不是則調(diào)用算法1

else將點(diǎn)(x1,y1)置為顏色c;

S2:for (y=y1;i≤y1+r·sin(=α2);y++) { ∥從y=3到y(tǒng)=y2逐行畫(huà)線(xiàn)

x1=x1+y·tan(α1);

x2=x1+y·tan(α2);

從(x1,y)到(x2,y) 畫(huà)線(xiàn);

}

S3:for(y=y1+r·sin(α2)+1;i<=y1+r·sin(α1);y++) { ∥從y=y2到y(tǒng)=y1逐行畫(huà)線(xiàn)

x1=x1+y·tan(α1);

x2=sqrt(r·r-y·y);

從(x1,y)到(x2,y)畫(huà)線(xiàn);

}

S4:結(jié)束

算法2.2、算法2.3和算法2.4的基本思想與算法2.1相同，不再贅述。

然后，再考慮一般的情況，即需要填充的區(qū)域跨象限。先把扇區(qū)按照象限劃分為若干個(gè)處于同一象限的子扇區(qū)，再對(duì)這些子扇區(qū)分別調(diào)用對(duì)應(yīng)的算法2.1、算法2.2、算法2.3和算法2.4，即可完成對(duì)跨象限扇區(qū)的填充。例如，在圖5中，扇區(qū)P0P1P2跨越了第一、第二和第三扇區(qū)，可分別用算法2.1、算法2.2和算法2.3填充P0aP2、P0ba和P0P1b，即可完成對(duì)P0P1P2扇區(qū)的填充。

圖5 跨象限的扇區(qū)

算法2：扇區(qū)填充算法

輸入:圓心(x1,y1)，角度α1，角度α2，半徑r，顏色c[3]

輸出:對(duì)給定的任意扇區(qū)按顏色c填充著色，重復(fù)區(qū)域調(diào)用算法1

S1:switch(α1) {

caseⅠ:switch (α2){

caseⅠ:算法2.1(x1,y1,α1,α2,r,c);

caseⅡ:算法2.1(x1,y1,α1,90,r,c);

算法2.2(x1,y1,90,α2,r,c);

caseⅢ:算法2.1(x1,y1,α1,90,r,c);

算法2.2(x1,y1,90,180,r,c);

算法2.3(x1,y1,180,α2,r,c);

caseⅣ:算法2.1(x1,y1,α1,90,r,c);

算法2.2(x1,y1,90,180,r,c);

算法2.3(x1,y1,180,270,r,c);

算法2.4(x1,y1,270,α2,r,c);

}

caseⅡ:…∥與Ⅰ相似，不再贅述。

caseⅢ:…∥與Ⅰ相似，不再贅述。

caseⅣ:…∥與Ⅰ相似，不再贅述。

}

S2:結(jié)束

算法3 改進(jìn)的混合柵格算法

S1:∥初始化環(huán)節(jié)

將屏幕初始化為白色

S2:∥預(yù)處理環(huán)節(jié)

S2.1:設(shè)定一個(gè)經(jīng)驗(yàn)參數(shù)k;

S2.2:for (對(duì)每一個(gè)生成元i的每個(gè)扇區(qū)j) { ∥所有生成元的初始覆蓋

S2.2.1:R=k·AllGen[i].w[j];

S2.2.2:算法2

(AllGen[i].x,AllGen[i].y,AllGen[i].a[j] ,AllGen[i].a[j+1],R,AllGen[i].a[j].RGB);

}

S2.3:for (OverLap中的非空元素) {

根據(jù)對(duì)應(yīng)生成元扇區(qū)的顏色進(jìn)行著色;

}

S3:∥計(jì)算剩余點(diǎn)環(huán)節(jié)

for (掃描所有空白像素點(diǎn)){

按照逐點(diǎn)掃描法著色;

}

S4:∥確定邊界環(huán)節(jié)

掃描繪圖區(qū)域，抽取邊界，得到分區(qū)加權(quán)Voronoi圖;

S5:結(jié)束

3 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)平臺(tái)的處理器為Intel(R)Core(TM) i5-5257U CPU@2.70GHz，內(nèi)存8GB。開(kāi)發(fā)平臺(tái)是Visual Studio 2010，編程語(yǔ)言為c#。實(shí)驗(yàn)分別實(shí)現(xiàn)了模擬生長(zhǎng)法、逐點(diǎn)掃描法，以及混合柵格算法和本文的改進(jìn)算法。各組測(cè)試點(diǎn)集都是隨機(jī)生成點(diǎn)集。表1是幾種算法在不同分辨率和生成元數(shù)量下的時(shí)間效率。

表1 時(shí)間效率對(duì)比

從實(shí)驗(yàn)結(jié)果可以看出，改進(jìn)的混合柵格算法在時(shí)間效率上總體優(yōu)于模擬生長(zhǎng)法、逐點(diǎn)掃描法和混合柵格算法。

圖6 是采用混合柵格算法以及本文算法生成500×500柵格大小100個(gè)生成元的效果圖的對(duì)比。

圖6 兩種算法結(jié)果對(duì)比

由上圖可以看出，兩種算法在實(shí)驗(yàn)結(jié)果上是完全相同的。說(shuō)明在精確度上，本文算法達(dá)到了原有算法的標(biāo)準(zhǔn)。

4 結(jié)束語(yǔ)

混合柵格算法是一種將逐點(diǎn)掃描法和模擬生長(zhǎng)法優(yōu)點(diǎn)相結(jié)合的分區(qū)加權(quán)Voronoi圖生成算法。本文針對(duì)混合柵格算法重疊區(qū)域處理不夠精細(xì)的問(wèn)

題，提出了一種改進(jìn)算。在保證算法正確性的基礎(chǔ)上，提高了效率。