Voronoi圖模擬生長算法的性能研究

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

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

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

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

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

1 現有算法研究

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 改進的算法設計

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

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

S1:初始化

繪圖區域置白色;著色點計數器count為0;生長步數計數器num為1;

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

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

S2.1://第1個扇區

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

Δθ= 1/r;

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

計算(curX, curY)的顏色;

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

置(curX, curY)為Ci1;

count++;}}

}

S2.2://第2個扇區

……}

}

S3:提取邊界

S4:結束

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

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

3 實驗的結果及分析

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

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

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

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

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

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

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

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

4 結 語

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

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

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