李璟瑩, 王斌君

(中國人民公安大學(xué)信息技術(shù)與網(wǎng)絡(luò)安全學(xué)院， 北京 100038)

關(guān)于加權(quán)Voronoi圖離散構(gòu)造法的正確性研究

李璟瑩, 王斌君

(中國人民公安大學(xué)信息技術(shù)與網(wǎng)絡(luò)安全學(xué)院， 北京 100038)

針對(duì)加權(quán)Voronoi圖離散構(gòu)造法的正確性問題，系統(tǒng)研究了Voronoi圖的原始定義和性質(zhì)，并對(duì)照加權(quán)Voronoi圖的逐點(diǎn)掃描算法，發(fā)現(xiàn)離散構(gòu)造法是一個(gè)粗略的算法，在生成具有多個(gè)離散區(qū)域的加權(quán)Voronoi圖時(shí)，該算法不正確；通過實(shí)驗(yàn)也證實(shí)了離散構(gòu)造法的錯(cuò)誤。通過分析離散構(gòu)造法的算法，發(fā)現(xiàn)其擴(kuò)展終止條件有錯(cuò)誤，提出了相應(yīng)的改進(jìn)算法，保證了算法結(jié)果的正確性。

加權(quán)Voronoi圖； 分區(qū)加權(quán)Voronoi圖； 離散構(gòu)造法； 逐點(diǎn)掃描法

0 引言

Voronoi圖解決了平面上離散生成元的空間劃分問題，是描述空間鄰近關(guān)系的一種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，適用于解決幾何重構(gòu)、覆蓋模擬、路徑規(guī)劃、空間分析等問題，在氣象學(xué)、地理學(xué)、晶體學(xué)、信息科學(xué)、機(jī)器人路徑規(guī)劃等領(lǐng)域應(yīng)用廣泛[1]。

最初的Voronoi圖是基于最短距離的空間剖分[2]，考慮的因素比較理想化，但在實(shí)際應(yīng)用中生成元往往具有不同的“影響力”，于是又?jǐn)U展出加權(quán)Voronoi圖[2]、分區(qū)加權(quán)Voronoi圖[3]、線段加權(quán)Voronoi圖[4]等各種加權(quán)Voronoi圖。

對(duì)于生成元被加權(quán)的Voronoi圖，生成算法包括矢量算法和柵格算法。矢量算法結(jié)果精確但計(jì)算復(fù)雜，柵格算法相對(duì)簡(jiǎn)單但精度受柵格大小影響。在柵格算法中，常用的有離散構(gòu)造法和逐點(diǎn)掃描法。1980年， B.N.Boots提出的模擬生長(zhǎng)模型(Growth Simulation Model)奠定了離散構(gòu)造法的基本思路，即通過模擬母點(diǎn)的動(dòng)態(tài)生長(zhǎng)過程來生成Voronoi圖[2]。1996年，Watanabe T等人按照模擬生長(zhǎng)的思想，提出了用于生成Voronoi圖的離散構(gòu)造法[5]。隨后，離散構(gòu)造法被不斷完善，適用于加權(quán)Voronoi圖[6]、分區(qū)加權(quán)Voronoi圖[3]、線段加權(quán)Voronoi圖[4]等。離散構(gòu)造法不涉及復(fù)雜運(yùn)算，實(shí)現(xiàn)簡(jiǎn)單，適用于各類生長(zhǎng)元。

逐點(diǎn)掃描法是計(jì)算每個(gè)柵格與所有生成元的距離(歐氏距離、棋盤距離、街區(qū)距離等)來確定最近生成元。1998年張有會(huì)提出了逐點(diǎn)掃描法生成Voronoi圖[7]，該方法是按照定義來計(jì)算距離，結(jié)果準(zhǔn)確。

1 基本概念及性質(zhì)

1.1 相關(guān)概念

下面分別給出Voronoi圖、加權(quán)Voronoi圖和分區(qū)加權(quán)Voronoi圖的定義。

定義1 Voronoi圖

設(shè)S={p1,p2,…,pn}是二維歐氏空間上的一個(gè)點(diǎn)(也稱生成元)集合，稱

定義2 加權(quán)Voronoi圖

設(shè)S={p1,p2,…,pn}為二維歐氏空間上的一個(gè)點(diǎn)集合，對(duì)每個(gè)點(diǎn)pi賦予正實(shí)數(shù)權(quán)重

圖1 加權(quán)Voronoi圖

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

設(shè)S={p1,p2,…,pn}為二維歐氏空間上的一個(gè)點(diǎn)集合，對(duì)每個(gè)生成元pi，以pi為原點(diǎn)、水平向右為坐標(biāo)軸的正向，建立極坐標(biāo)系，將生成元pi周圍區(qū)域分成mi個(gè)扇區(qū)，以θ=αik(k=1,2,…,mi)為扇區(qū)分界線，其中，0<αi1<αi2<…<αimi<2π，并給每個(gè)扇區(qū)賦予權(quán)重wik(k=1,2,…,mi)，稱

為點(diǎn)pi在第k扇區(qū)的權(quán)重為wik的Voronoi區(qū)域，或稱點(diǎn)pi的第k加權(quán)扇區(qū)[3]。

1.2 相關(guān)性質(zhì)

凡是生成元被加權(quán)的Voronoi圖都具有以下典型性質(zhì)[2-3]：

(1)相鄰兩個(gè)生成元pi和pj之間的邊界是一條直線(當(dāng)wi=wj，i≠j)或阿波羅尼圓(當(dāng)wi≠wj，i≠j)。在圖1中，p6與p8的權(quán)重大小一樣，兩者的分界線是直線，而其他生成元之間的邊界線都是圓弧。

(2)“洞”的存在。當(dāng)一個(gè)生成元權(quán)重與相鄰生成元權(quán)重相比足夠小時(shí)，該生成元的加權(quán)Voronoi區(qū)域可能完全被另一個(gè)生成元的加權(quán)Voronoi區(qū)域包圍，如圖1所示，p1的覆蓋區(qū)域完全被p2的覆蓋區(qū)域包圍。

(3)越區(qū)覆蓋。某個(gè)生成元的加權(quán)Voronoi區(qū)域可能由若干塊不連續(xù)的區(qū)域組成，即某個(gè)生成元的加權(quán)Voronoi區(qū)域可能跨越其他生成元的加權(quán)Voronoi區(qū)域。如圖1所示，p7的權(quán)重最大，它的加權(quán)Voronoi區(qū)域跨越了p4和p5的加權(quán)Voronoi區(qū)域。

由于難以直觀判斷一個(gè)生成元是否存在越區(qū)覆蓋，所以前人雖然提出過該性質(zhì)，但在設(shè)計(jì)生成算法時(shí)往往會(huì)忽略該性質(zhì)。越區(qū)覆蓋作為加權(quán)類的Voronoi圖的一種性質(zhì)，雖然有時(shí)會(huì)出現(xiàn)這種情況，但它反映了權(quán)重分布的不均衡，在實(shí)際應(yīng)用中能幫助發(fā)現(xiàn)和分析問題，例如基站、變電站等設(shè)備的功率設(shè)定過大和覆蓋盲區(qū)等問題。

2 離散構(gòu)造法的正確性分析

在對(duì)比離散構(gòu)造法和逐點(diǎn)掃描法的性能時(shí)，兩種算法在大多數(shù)情況下結(jié)果一致，但在生成加權(quán)類的Voronoi圖時(shí)，部分結(jié)果存在明顯差異。下面從實(shí)驗(yàn)證實(shí)和理論分析兩個(gè)方面分別進(jìn)行闡述。

2.1 實(shí)驗(yàn)證實(shí)

實(shí)驗(yàn)1：加權(quán)Voronoi圖實(shí)驗(yàn)。

圖2和圖3是分別使用兩種生成算法得到的關(guān)于12個(gè)生成元的加權(quán)Voronoi圖。比較發(fā)現(xiàn)，圖2中的p7僅覆蓋了①區(qū)域，而圖3中的p7卻覆蓋了①、②、③三塊不連續(xù)的區(qū)域，其余部分的空間劃分是一致的。

圖2 加權(quán)離散構(gòu)造法的結(jié)果

圖3 加權(quán)逐點(diǎn)掃描法的結(jié)果

實(shí)驗(yàn)2：分區(qū)加權(quán)Voronoi圖實(shí)驗(yàn)。

圖4和圖5分別是使用兩種生成算法得到的關(guān)于10個(gè)生成元的分區(qū)加權(quán)Voronoi圖。比較發(fā)現(xiàn)，圖4中p6的第二加權(quán)扇區(qū)僅覆蓋了①區(qū)域，而圖5中p6的第二加權(quán)扇區(qū)卻覆蓋了①、②、③三塊不連續(xù)區(qū)域。

圖4 分區(qū)加權(quán)離散構(gòu)造法的結(jié)果

圖5 分區(qū)加權(quán)逐點(diǎn)掃描法的結(jié)果

實(shí)驗(yàn)結(jié)果顯示，對(duì)于同一生成元，離散構(gòu)造法得到的覆蓋區(qū)域是一塊、連續(xù)的，而逐點(diǎn)掃描法得到的覆蓋區(qū)域是多塊、不連續(xù)的。

2.2 理論分析

按照定義，所有Voronoi圖都是按照最鄰近原則進(jìn)行空間劃分，加權(quán)類Voronoi圖的衡量標(biāo)準(zhǔn)是加權(quán)的歐氏距離。逐點(diǎn)掃描法通過計(jì)算加權(quán)距離得到每個(gè)像素點(diǎn)的最近生長(zhǎng)元，思路與定義一致，所以結(jié)果是準(zhǔn)確的。

那么，離散構(gòu)造法為什么會(huì)出現(xiàn)與逐點(diǎn)掃描法不同的結(jié)果呢？

從WatanabeT提出離散構(gòu)造法到后來人們不斷擴(kuò)展其應(yīng)用，離散構(gòu)造法都遵循與算法1同樣的算法思路[3-6]。

算法1：原離散構(gòu)造法。

(1)初始化，建立集合S，用于存放所有待擴(kuò)張的生成元。

(2)S中的生成元(扇形)依次一層層向外擴(kuò)張畫圓(弧)，每次畫圓(弧)的半徑與權(quán)重成正比，所有生成元(扇區(qū))填涂的顏色互不相同，擴(kuò)張過程中只填涂空白柵格。

(3)擴(kuò)張終止條件：在畫某一層圓周時(shí)，如果該層圓周上的柵格都已被填涂，則判斷該生成元的Voronoi區(qū)域(加權(quán)Voronoi區(qū)域)生成完畢，就將該生成元從S集合中刪去。直到S集合中沒有生成元，畫圖結(jié)束。

(4)掃描全屏幕，提取邊界。

按照離散構(gòu)造法的終止條件，當(dāng)算法擴(kuò)張到某個(gè)時(shí)刻，如果某個(gè)生成元的擴(kuò)張空間被其他生成元完全包圍，該生成元就會(huì)從S中刪除，即不再擴(kuò)展，如圖6中的P7。這意味著在該判定條件下任何生成元都不可能生成多塊、不連續(xù)的覆蓋區(qū)域。

圖6 加權(quán)Voronoi圖的離散構(gòu)造法過程

3 改進(jìn)的算法

通過以上分析，在遵循B.N.Boots模擬生長(zhǎng)模型的基礎(chǔ)上，為了確保所有生成元能正確地按照權(quán)重正比例擴(kuò)張，需要將WatanabeT提出的離散構(gòu)造法終止條件設(shè)為“某層擴(kuò)張圓周的全部柵格都超出屏幕邊界”。

下面以加權(quán)Voronoi圖的生成為例，給出改進(jìn)的算法，如算法2所示。

算法2：改進(jìn)的離散構(gòu)造法。

輸入：生成元集合S={p1,p2,…,pn}，生成元權(quán)重的集合W={w1,w2,…,wn}。

輸出：以S為生成元集、W為權(quán)重的加權(quán)Voronoi圖。

Step1：建立集合L，用于存放待擴(kuò)張的生成元數(shù)據(jù)，L=S，擴(kuò)展半徑r=1。

Step2：給每個(gè)生成元賦予各不相同的顏色，使得相鄰加權(quán)Voronoi區(qū)域可以區(qū)分開。

Step3：當(dāng)L不為空時(shí)，執(zhí)行如下循環(huán)：

{

對(duì)L中的每個(gè)元素pi，執(zhí)行如下循環(huán)：

{

f=0；∥用于判斷某層擴(kuò)張圓周的柵格是否都超出邊界；

對(duì)生成元pi在擴(kuò)展半徑為r*wi的圓周上的每個(gè)點(diǎn)，執(zhí)行以下循環(huán)：

{

如果沒有超出整個(gè)區(qū)域的邊界，則f=f+1，并將空白柵格填涂為所設(shè)的顏色；

}

圓周掃描結(jié)束后，如果f=0，則表明該圓周上的所有柵格都超出邊界，將該生成元從L中刪除。

}

r++；

}

Step4：依次橫向和縱向掃描屏幕，將與后繼柵格顏色不同的柵格設(shè)置為黑色。

Step5：橫向掃描全屏幕，將非黑色柵格置為白色，提取加權(quán)Voronoi圖的邊界。

經(jīng)實(shí)驗(yàn)比對(duì)，改進(jìn)算法與逐點(diǎn)掃描法的生成結(jié)果一致，保證了正確性，但是改進(jìn)算法相比原離散構(gòu)造法需要掃描更多次數(shù)，時(shí)間復(fù)雜度更高。

4 結(jié)束語

模擬生長(zhǎng)模型提出了一種Voronoi圖的生成方法，后人提出的離散構(gòu)造法是該模型的一種具體實(shí)現(xiàn)。本文通過對(duì)比試驗(yàn)和理論分析，找出了離散構(gòu)造法存在的問題，并提出了一種改進(jìn)算法，在繼承原有算法思想的基礎(chǔ)上，保證了算法的正確性。但不足之處是，改進(jìn)算法的效率較低，未來還需要仔細(xì)研究越區(qū)覆蓋的特征和規(guī)律，就如何降低時(shí)間復(fù)雜度開展進(jìn)一步研究。

[1] MU L. Polygon Characterization With the Multiplicatively Weighted Voronoi Diagram?[J]. The Professional Geographer，2004，56(2)：223-239.

[2] BOOTS B N. Weighting thiessen polygons[J]. Economic Geography，1980，56(3)：248-259.

[3] 馬立玲. 分區(qū)加權(quán)Voronoi圖的生成及其面積計(jì)算[D]. 石家莊：河北師范大學(xué), 2004.

[4] 董蕊, 張有會(huì), 劉淑娟,等. 線段加權(quán)Voronoi圖的離散生成算法的研究與實(shí)現(xiàn)[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2009, 26(7):245-247.

[5] WATANABE T，MURASHIMA S. A method to construct a Voronoi diagram on 2-D digitized space in O (1) computing time[J]. IEICE Trans. DI，1996，79：114-122.

[6] 趙志輝, 李平, 黃曉芹. 加權(quán)Voronoi圖的離散生成[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2007, 24(1):135-136.

[7] 張有會(huì).關(guān)于加權(quán)Voronoi圖的研究[D].北京：北京航空航天大學(xué),1998.

(責(zé)任編輯 于瑞華)

李璟瑩(1992—)，女，湖南懷化人，2014級(jí)在讀碩士研究生。研究方向?yàn)榫W(wǎng)絡(luò)安全執(zhí)法技術(shù)、公安信息化。

O18