王斌君，王秋實(shí)，李璟瑩，沙俊松

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

Voronoi圖[1]是計(jì)算幾何領(lǐng)域中的一個(gè)重要研究方向,Voronoi圖的生成算法是該領(lǐng)域的關(guān)鍵技術(shù)。Voronoi圖被廣泛應(yīng)用于氣象學(xué)、地理學(xué)、晶體學(xué)、信息科學(xué)、機(jī)器人路徑規(guī)劃、警力部署、商圈劃分、室內(nèi)布局、林業(yè)等應(yīng)用領(lǐng)域。目前,Voronoi圖的理論熱點(diǎn)集中在高階[2]和高維空間[3]的相關(guān)問題研究,但其核心思想和算法仍然是以傳統(tǒng)的分區(qū)加權(quán)Voronoi圖為基礎(chǔ)。因此,研究和改善基本的分區(qū)加權(quán)Voronoi圖生成算法的性能有一定的理論和實(shí)用價(jià)值。

截至目前為止,已有的基本分區(qū)加權(quán)Voronoi圖生成算法主要包括矢量法和柵格法兩大類。相對于Voronoi圖矢量法[4-5]的精度高但數(shù)據(jù)結(jié)構(gòu)和計(jì)算復(fù)雜,只適用于簡單Voronoi圖而言,柵格法[5-8]雖然精度較低,但能適用于任何Voronoi圖(生成元可為點(diǎn)、線或面,且各生成元可分區(qū)、加權(quán)),其擴(kuò)展性強(qiáng)、速度快,具有很強(qiáng)的泛化能力和適用性。

Voronoi圖的柵格法包括逐點(diǎn)掃描法[6]和模擬生長法,模擬生長法目前包括距離表[7]和離散構(gòu)造[8]兩種算法。本文對分區(qū)加權(quán)Voronoi圖模擬生長法進(jìn)行系統(tǒng)分析和研究,發(fā)現(xiàn)文獻(xiàn)[7-8] 存在諸多的缺陷。為此,我們設(shè)計(jì)并實(shí)現(xiàn)了一種改進(jìn)的算法,克服了原算法的不足,提高了原算法的效率。

1 現(xiàn)有算法研究

模擬生長法的基本思想是[4]:對于平面上n個(gè)生成元,每個(gè)生成元的每個(gè)扇區(qū)都被賦予不同顏色和權(quán)值,分別以每個(gè)生成元為圓心,同步在各扇區(qū)以指定速率(與權(quán)重成正比)向外擴(kuò)展畫弧,直到空間被顏色填滿,不同顏色區(qū)域的邊界即為分區(qū)加權(quán)Voronoi圖的近似邊界。在逐步擴(kuò)展畫弧過程中,畫每一個(gè)點(diǎn)前需檢查該點(diǎn)是否已被著色,如為白色,則用相應(yīng)扇區(qū)的顏色填涂;否則不作處理。該算法思路清晰,實(shí)現(xiàn)簡單。

但文獻(xiàn)[8] 提出的離散構(gòu)造算法存在以下問題:

問題1邊界粗糙問題。邊界線的形成是通過各生成元同步擴(kuò)展過程的“碰撞”來粗糙逼近的,最終生成的邊緣與擴(kuò)展過程中生成元的先后次序有關(guān)。圖1(a)和圖1(b)分別是模擬增長法對相同生成元的不同次序結(jié)果圖,邊界上有一定的差異，圖1(c)是逐點(diǎn)掃描法的對比結(jié)果圖。其實(shí),模擬生長法天生存在邊界上的缺陷問題,對其構(gòu)造的現(xiàn)有算法[7-8]都會存在邊界不精確問題。

問題2角度增量問題。為了對所有半徑的擴(kuò)展弧進(jìn)行逐點(diǎn)著色掃描,設(shè)置了一個(gè)足夠小的固定角增量,以便正確處理大半徑的情況,即對小半徑弧和大半徑弧掃描的角度增量一樣,這就導(dǎo)致原算法在前期(擴(kuò)展半徑小的時(shí)候)著色速度明顯很慢。改進(jìn)的方法是將角增量設(shè)定為與半徑成反比的動態(tài)值。理想情況下,角增量應(yīng)該是擴(kuò)展弧上相鄰兩個(gè)點(diǎn)對應(yīng)的角度。繪圖區(qū)域兩點(diǎn)之間的最小距離為1,對應(yīng)的劣弧會略大一點(diǎn)點(diǎn)。按照半徑、劣弧和角度的計(jì)算關(guān)系,將角增量設(shè)置為1/r。它既能滿足算法的正確性,而且在擴(kuò)展半徑小的時(shí)候,算法的運(yùn)算速度會明顯加快,提高了原算法的效率。

圖1 邊界粗糙問題Fig.1 The problem of boundary roughness

問題3斑馬紋問題。算法沒有考慮大權(quán)值的情況，同步擴(kuò)展時(shí)大權(quán)值的實(shí)際擴(kuò)展半徑(步)的增量如果大于1,就會因?yàn)榭绮教髮?dǎo)致未著色區(qū)域,如圖2(a)所示。圖2(b)是一個(gè)示例的結(jié)果,其中,左下角和右上角存在兩個(gè)權(quán)值比較大的生成元,結(jié)果出現(xiàn)了錯(cuò)誤。

圖2 斑馬紋問題Fig.2 The problem of zebra stripe

與該問題相關(guān)的一個(gè)問題是,當(dāng)生成元的權(quán)值太小時(shí),原算法需要重復(fù)計(jì)算擴(kuò)展弧,從而影響了算法的效率。

問題4不連續(xù)區(qū)域問題。該算法存在的更重要問題是沒有考慮不連續(xù)Voronoi圖的情況(文獻(xiàn)[4] 的性質(zhì)Ⅳ)。對于某個(gè)生成元，當(dāng)其周圍的邊界確定后,就不再擴(kuò)展,這只是在沒有不連續(xù)區(qū)域Voronoi圖的情況下是正確的。我們曾撰文討論了該問題[9],并簡單地修正了算法的終止條件(每個(gè)生成元都需要擴(kuò)展并判斷到所有繪圖區(qū)域),以保證算法的正確性。但文獻(xiàn)[9] 尚未對算法終止條件進(jìn)行詳細(xì)分析。

下面對模擬生長法的終止條件進(jìn)行討論。首先給出定理1。

定理1對模擬生長法,在算法依次擴(kuò)展過程中,如果繪圖區(qū)域的某個(gè)點(diǎn)第一次被某個(gè)生成元覆蓋,即確定了某個(gè)顏色,則該點(diǎn)在算法以后的擴(kuò)展過程中不會改變顏色。

證明按照模擬生長法的思想,某個(gè)點(diǎn)被標(biāo)記為某個(gè)顏色后,其算法的后續(xù)步驟不會再改變其顏色,該定理的結(jié)論顯然是正確的。

推論1對模擬生長法,當(dāng)最大權(quán)值生成元覆蓋了繪圖區(qū)的所有點(diǎn)時(shí),算法可結(jié)束。

證明先證明一般的情況。對任何一個(gè)生成元,如果其擴(kuò)展區(qū)域能覆蓋了所有繪圖區(qū)域的點(diǎn),則繪圖區(qū)域任何一個(gè)點(diǎn)都在本次或之前的算法擴(kuò)展過程中確定了顏色。根據(jù)定理1,算法可結(jié)束。

所以,該結(jié)論對最大生成元也成立。

推論2對模擬生長算法,當(dāng)繪圖區(qū)域所有點(diǎn)被著色后,算法可結(jié)束。

證明根據(jù)定理1可直接得到本推論。

推論1是從生成元的角度設(shè)置算法的終止條件,而推論2則是從繪圖區(qū)域的角度設(shè)置終止條件。按照推論1,當(dāng)出現(xiàn)圖3的情況(權(quán)值最大生成元靠近某一個(gè)角,而另一個(gè)相對權(quán)值比較大的生成元在另一個(gè)角)時(shí),盡管繪圖區(qū)域已經(jīng)完全被覆蓋(如圖3所示,在算法擴(kuò)展過程中的某個(gè)時(shí)刻,點(diǎn)虛線和細(xì)的杠虛線是右上角生成元的覆蓋情況;粗的杠虛線是左下角生成元的覆蓋情況),繪圖區(qū)域各點(diǎn)的顏色都確定了,但算法仍需繼續(xù),效率比較低。按照推論2,可用一個(gè)計(jì)數(shù)器,當(dāng)繪圖區(qū)域中被著色點(diǎn)的總數(shù)達(dá)到了繪圖區(qū)域所有點(diǎn)的總數(shù)即可結(jié)束算法,算法效率會更高。

圖3 以最大生成元覆蓋作為終結(jié)條件的情況Fig.3 The case of termination with maximum generator

需要注意的是,文獻(xiàn)[7] 也存在問題1和問題4。問題1是模擬生長法本身存在的共性問題,除非采用并行算法,否則任何模擬生長法的常規(guī)算法都存在問題1;而問題4是距離表算法[7]和離散構(gòu)造算法[8]本身設(shè)計(jì)不合理造成的。

2 改進(jìn)的算法設(shè)計(jì)

基于上文對現(xiàn)有離散構(gòu)造算法的分析,對其存在的問題,本文設(shè)計(jì)的改進(jìn)算法如下。

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

S1:初始化

繪圖區(qū)域置白色;著色點(diǎn)計(jì)數(shù)器count為0;生長步數(shù)計(jì)數(shù)器num為1;

S2:while (count<繪圖區(qū)域柵格總數(shù)) {

for (i=1;i≤生成元數(shù);i++){

S2.1://第1個(gè)扇區(qū)

for(r=(num-1)*Wi1;r

Δθ= 1/r;

for(θ=θi1;θ<θi2;θ=θ+Δθ){

計(jì)算(curX, curY)的顏色;

if ((curX, curY)的顏色為白色){

置(curX, curY)為Ci1;

count++;}}

}

S2.2://第2個(gè)扇區(qū)

……}

}

S3:提取邊界

S4:結(jié)束

其中,Wi1表示第i個(gè)生成元中第1扇區(qū)的權(quán)重,θi1和θi2分別表示第i個(gè)生成元中第1扇區(qū)的起始角度和結(jié)束角度,Ci1表示第i個(gè)生成元中第1個(gè)扇區(qū)的顏色。

本算法通過設(shè)立動態(tài)的角度增量1/r,解決了問題2;通過增加了一個(gè)步長循環(huán),解決了問題3;特別是通過count計(jì)數(shù)器建立終止條件,解決了問題4。

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

圖4分別是采用原離散構(gòu)造算法[8]、文獻(xiàn)[9] 的改進(jìn)算法和本算法的實(shí)驗(yàn)結(jié)果。

圖4 3種模擬生長算法的對比圖Fig.4 Constrast diagram of three simulated growth methods

圖4(a)是文獻(xiàn)[8] 離散構(gòu)造算法的結(jié)果,其中左側(cè)的不連續(xù)區(qū)域不能正確生成,結(jié)果中也存在斑馬線。圖4(b)是文獻(xiàn)[9] 改進(jìn)原始算法終止條件后得到的能正確處理具有不連續(xù)區(qū)域Voronoi圖的

結(jié)果,但仍然存在斑馬線。圖4(c)是本算法的結(jié)果,它能正確處理不連續(xù)區(qū)域問題和斑馬線問題。

表1是在相同軟硬件環(huán)境下,不同參數(shù)的對比數(shù)據(jù)。其中,所有生成元、生成元的扇區(qū)角度(本實(shí)驗(yàn)均采用一個(gè)生成元有3個(gè)扇區(qū))以及生成元各扇區(qū)的權(quán)重都是隨機(jī)生成的。

圖5是表1數(shù)據(jù)的趨勢對比圖。圖5(a)，圖5(b)和圖5(c)分別是對應(yīng)表1中300*300，500*500和800*800屏幕繪圖區(qū)的3種算法趨勢圖。從表1和圖5可以看出,文獻(xiàn)[9] 雖然糾正了原算法[8]不能正確處理具有不連續(xù)區(qū)域Voronoi圖的錯(cuò)誤,但需要將所有生成元擴(kuò)展到繪圖區(qū)域的邊界,所以計(jì)算速度慢。本算法能正確處理不連續(xù)區(qū)域Voronoi圖和斑馬線問題,且效率明顯快,甚至優(yōu)于文獻(xiàn)[8] 。雖然本算法也與生成元多少、屏幕大小成正比,但其增長速度比文獻(xiàn)[8] 和文獻(xiàn)[9] 明顯緩慢。

在表1中,500*500屏幕區(qū)域，50個(gè)生成元的情況,本算法生成Voronoi圖需要10.9s,而100個(gè)生成元的只需要6.3s,這與生成元的分布有關(guān),但并不影響算法的整體效果。

表1 3種模擬生長算法的數(shù)據(jù)對比Tab.1 The constrast of three simulated growth methods with different data

4 結(jié) 語

目前,Voronoi圖的理論熱點(diǎn)集中在高階[2, 10-11]和高維空間[3]的相關(guān)問題研究,更多的研究成果是Voronoi圖在區(qū)域劃分、覆蓋和選址[12-15]等方面的應(yīng)用研究,但其核心思想和算法仍然是以傳統(tǒng)的分區(qū)加權(quán)Voronoi圖為基礎(chǔ)。本文研究了Voronoi圖模擬生長法的相關(guān)問題,重點(diǎn)分析了文獻(xiàn)[8] 提出的算法,對其不完善和效率問題,提出了分區(qū)加權(quán)Voronoi圖離散構(gòu)造法的改進(jìn)算法。理論分析和實(shí)驗(yàn)結(jié)果表明,改進(jìn)的算法能正確處理不連續(xù)Voronoi圖、斑馬紋等問題,且改進(jìn)算法的效率優(yōu)于原算法。

圖5 3種模擬增長算法的趨勢對比Fig.5 Trend contrast of three simmulated growth methods

但是,由于Voronoi圖模擬生長法的本質(zhì)特征,模擬生長法除非采用并行算法,否則生成元覆蓋區(qū)域邊界都會出現(xiàn)不精確的問題，生成元分布不均時(shí),算法效率就會下降，下一步將結(jié)合逐點(diǎn)掃描法進(jìn)行研究。