王斌君，王秋實，李璟瑩，沙俊松

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

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

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

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

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

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

但文獻[8] 提出的離散構造算法存在以下問題:

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

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

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

問題3斑馬紋問題。算法沒有考慮大權值的情況，同步擴展時大權值的實際擴展半徑(步)的增量如果大于1,就會因為跨步太大導致未著色區(qū)域,如圖2(a)所示。圖2(b)是一個示例的結果,其中,左下角和右上角存在兩個權值比較大的生成元,結果出現(xiàn)了錯誤。

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

與該問題相關的一個問題是,當生成元的權值太小時,原算法需要重復計算擴展弧,從而影響了算法的效率。

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

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

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

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

推論1對模擬生長法,當最大權值生成元覆蓋了繪圖區(qū)的所有點時,算法可結束。

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

所以,該結論對最大生成元也成立。

推論2對模擬生長算法,當繪圖區(qū)域所有點被著色后,算法可結束。

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

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

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

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

2 改進的算法設計

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

算法:改進的離散構造算法。

S1:初始化

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

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

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

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

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

Δθ= 1/r;

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

計算(curX, curY)的顏色;

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

置(curX, curY)為Ci1;

count++;}}

}

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

……}

}

S3:提取邊界

S4:結束

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

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

3 實驗的結果及分析

圖4分別是采用原離散構造算法[8]、文獻[9] 的改進算法和本算法的實驗結果。

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

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

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

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

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

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

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

4 結 語

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

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

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