劉青平，趙學(xué)勝，王 磊，孫文彬

1. 中國礦業(yè)大學(xué)(北京)地球科學(xué)與測繪工程學(xué)院,北京 100083； 2. 河南理工大學(xué)測繪與國土信息工程學(xué)院,河南 焦作 454000

Voronoi圖(簡稱V圖)是計算幾何學(xué)中一個重要的數(shù)據(jù)結(jié)構(gòu)，具有自然鄰近、動態(tài)穩(wěn)定等特性，在計算機圖形學(xué)、地理信息系統(tǒng)、生態(tài)學(xué)、分子化學(xué)、氣象學(xué)、機械、醫(yī)學(xué)、藝術(shù)等領(lǐng)域得到了廣泛應(yīng)用[1-6]。其中，V圖結(jié)構(gòu)的高效、準(zhǔn)確生成是其諸多應(yīng)用順利實現(xiàn)的關(guān)鍵。國內(nèi)外學(xué)者對V圖生成算法進行了許多研究，其成果主要分為矢量算法和柵格算法兩類。

經(jīng)典矢量算法包括分治算法[7]、插入算法[8]、掃描線算法[9]、投影算法[10]等。矢量算法對生長元有一定的局限性[11]，只能將點和線段(或半線)作為生長元處理，較難生成線集圖[12]，對于面和其他更復(fù)雜的空間目標(biāo)要將其分解為點和線后才能處理，這種分解嚴(yán)重地破壞了空間生長目標(biāo)的完整性。矢量算法不僅算法復(fù)雜，而且產(chǎn)生的數(shù)據(jù)結(jié)構(gòu)復(fù)雜，不利于海量數(shù)據(jù)的處理[13]。

為彌補矢量算法的不足，許多學(xué)者提出了基于柵格數(shù)據(jù)的V圖生成算法。柵格V圖生成算法的關(guān)鍵是為每個格網(wǎng)找到距其最近的種子點(或線、面)。依據(jù)格網(wǎng)得到種子點歸屬方法的不同，現(xiàn)有柵格V圖生成算法可分為3類。第一類算法，是較為傳統(tǒng)的通過多邊形的擴張和距離變換來得到V圖，如距離變換算法[13-14]、擴張算法[15-16]等。這類算法通過使用柵格距離代替歐氏距離來提升效率，所用模板有棋盤距離、城市距離、八角距離等。這些距離指標(biāo)只是最優(yōu)距離度量(歐幾里得距離)的粗略近似。這類算法的誤差很難控制，隨著格網(wǎng)和種子點數(shù)量增多而加大。第二類算法是利用四叉樹等數(shù)據(jù)結(jié)構(gòu)通過區(qū)域劃分并判斷區(qū)域歸屬的方式來得到V圖，如層次算法[17-18]、細(xì)分算法[19]等。此類算法大多較為復(fù)雜，不同層次、區(qū)域拓?fù)潢P(guān)系不明朗，且很難動態(tài)添加刪除數(shù)據(jù)。第三類算法是通過計算與比較格網(wǎng)與種子點之間的距離得到V圖，如確定歸屬算法[20-21]、柵格掃描算法[22]等。此類算法使用歐氏距離作為距離基準(zhǔn)，大多具有較好的精度指標(biāo)。除此之外，一些學(xué)者也通過并行計算來對上述各類算法的效率進行改進[16,21,23-24]，但是通常情況下，計算機技術(shù)并不能提升算法的精度。

綜合精度和效率因素，柵格掃描算法是最優(yōu)的柵格V圖生成算法之一。此類算法通常利用鄰域模板對所有格網(wǎng)進行向前向后兩次掃描得到V圖。算法既符合計算機離散特征，又優(yōu)化了歐氏距離算法，在大數(shù)據(jù)量情況下，較其他第三類柵格V圖生成算法具有效率上的優(yōu)勢[25]。但是由于柵格距離與歐氏距離的差異，在掃描過程中部分單元的歸屬不可避免地產(chǎn)生一定的誤差[26]。然而，在地圖、軍事、醫(yī)學(xué)[3-5]等高精度領(lǐng)域的應(yīng)用中，V圖的誤差可能會造成嚴(yán)重的后果。例如，在海洋劃界工作中，V圖是問題的理想解決辦法[6]。不過，在海洋區(qū)域的劃界中出現(xiàn)任何位置誤差，就會增加一個國家的海洋空間，而損害另一個國家的海洋空間。這種情況可能對有關(guān)國家的經(jīng)濟、軍事活動和國家關(guān)系產(chǎn)生嚴(yán)重影響。

為此，本文提出了一種基于橫-縱掃描的V圖生成改進算法，即根據(jù)傳統(tǒng)算法產(chǎn)生誤差的區(qū)域特征，在一個正常周期的水平(橫向)掃描后，增加一個周期豎直(縱向)掃描，實現(xiàn)柵格V圖的高效、準(zhǔn)確生成，并把誤差控制在一個格網(wǎng)以內(nèi)，最后進行了試驗對比分析。

1 傳統(tǒng)掃描算法原理及缺陷

1.1 傳統(tǒng)掃描算法原理

與矢量空間Voronoi區(qū)域是連續(xù)的相同，在柵格空間，一般情況下Voronoi區(qū)域也是連續(xù)的，即一個柵格格網(wǎng)和它的部分鄰近格網(wǎng)屬于相同的Voronoi區(qū)域。根據(jù)這個特點，利用鄰近格網(wǎng)之間最近種子點的傳遞，格網(wǎng)就可以從它鄰近格網(wǎng)處得到它所屬的Voronoi區(qū)域，而不必與所有種子點進行距離比較。

傳統(tǒng)柵格掃描算法[22]原理是通過一個33的鄰域模板將一個格網(wǎng)的信息傳遞給它的鄰近格網(wǎng)(如圖1所示)。首先，進行正反兩次掃描：掃描開始之前格網(wǎng)P被賦予一個空值，正向掃描按從左到右、從上到下的順序逐行進行，掃描過程中格網(wǎng)P分別計算并比較與Q1、Q2、Q3和Q4這4個鄰近格網(wǎng)(臨時)最近種子點之間的距離，然后將距離最短的種子點作為當(dāng)前格網(wǎng)P的(臨時)最近種子點，可用公式(1)來表示；反向掃描按從右到左、從下到上的順序逐行進行掃描，通過距離的計算與比較從P的臨時最近種子點及Q5、Q6、Q7和Q8的最近種子點中獲取P的最終最近種子點。一般情況下，Q1到Q8至少有一個與格網(wǎng)P有相同的最近種子點。在正反兩次掃描過程中，格網(wǎng)P通過與其鄰近格網(wǎng)的(臨時)最近種子點的距離計算與比較得到其最近種子點，這一過程稱為格網(wǎng)P得到其正確歸屬種子點。

圖1 3×3鄰域示意圖Fig.1 3 × 3 neighborhood diagram

(1)

1.2 傳統(tǒng)算法缺陷分析

本文將一次正向掃描和一次反向掃描稱作一個水平周期掃描。按上述算法進行了一個周期掃描之后，大多數(shù)的格網(wǎng)單元都得到了正確的種子點，但仍有少數(shù)格網(wǎng)單元的歸屬信息是錯誤的(如圖2)。

如圖2所示，格網(wǎng)A、B和C為該V圖種子點，其正確結(jié)果如圖2(a)所示，格網(wǎng)M、N、P和Q的正確歸屬均為種子點B。但是，一個水平掃描周期后，格網(wǎng)M、N、P和Q沒有得到其正確歸屬，如圖2(d)。這是由于正向掃描為從上到下的逐行掃描，格網(wǎng)M、N、P和Q的掃描順序在種子點B之前，它們歸屬判斷的種子點并不包括種子點B，正向掃描完成后這4個格網(wǎng)暫時歸屬于種子點A，如圖2(b)所示；當(dāng)反向掃描到格網(wǎng)M時，此時它的鄰近格網(wǎng)5-8歸屬于種子點C，格網(wǎng)1-4歸屬于種子點A，格網(wǎng)M只能從其臨近格網(wǎng)的歸屬(種子點A和C)中進行判斷比較，而不能得到其正確歸屬(種子點B)，如圖2(c)。在整個水平掃描周期過程中，正反兩次與格網(wǎng)M進行距離計算和比較的種子點中都沒有包括其正確的最近種子點(種子點B)，造成了錯誤的出現(xiàn)。

掃描算法核心是在掃描過程中通過每個格網(wǎng)的與部分種子點之間的距離計算和比較得到該格網(wǎng)的最近種子點。然而由于傳統(tǒng)算法掃描的不完備，上述錯誤的出現(xiàn)主要因為在掃描過程中對某一格網(wǎng)(如格網(wǎng)M)所進行的距離計算與比較并沒有包括其最近種子點，致使該格網(wǎng)的歸屬出現(xiàn)錯誤。圖3(a)為一隨機種子點情況下傳統(tǒng)柵格掃描算法得到的V圖，圖3(c)為確定歸屬算法得到的正確的V圖，可以看出它們之間有較大的差異，如圖3(b)黑色區(qū)域所示。

也有學(xué)者在掃描算法結(jié)果的基礎(chǔ)上，進行多周期的相同掃描過程以減少不正確歸屬格網(wǎng)的數(shù)量，但是為得到正確V圖，重復(fù)掃描周期的次數(shù)n是難以控制的。

2 改進算法

2.1 歸屬出錯單元范圍界定

首先分析種子點經(jīng)一個周期掃描后錯誤歸屬單元的空間分布特征。

如圖4所示，格網(wǎng)A和格網(wǎng)B為種子點。在進行正向掃描時，掃描順序為從左到右、從上到下順序逐行進行掃描。因為所選模板為3×3模板，所以掃描順序在種子點A左上方格網(wǎng)1之前的格網(wǎng)，都沒有計算和比較過與種子點A之間的距離。與格網(wǎng)1為同一行且掃描順序在格網(wǎng)1之后的格網(wǎng)，都可以從其左側(cè)格網(wǎng)處得到種子點A。種子點A同一行的格網(wǎng)中，最早得到種子點A的是格網(wǎng)2，它是從其右上方格網(wǎng)1處得到的。這樣臨時歸屬于種子點A的格網(wǎng)就形成了一個135°的角度，由格網(wǎng)1向左下方延伸。在掃描到達種子點B附近時，經(jīng)過了與種子點A相同過程。于是在正向掃描結(jié)束時，就形成了如圖4所示的臨時種子點歸屬圖，其中淺藍色格網(wǎng)歸屬于種子點A，淺綠色格網(wǎng)歸屬于種子點B。

單次反向掃描過程與正向掃描過程類似。其結(jié)果如圖5所示。

在傳統(tǒng)掃描算法中，一個格網(wǎng)需經(jīng)過正反兩次掃描，如果其在任意一次掃描過程中得到正確種子點，那么便能得到正確歸屬。如圖6所示，藍色部分格網(wǎng)在正向掃描后必定可以得到種子點C，綠色部分格網(wǎng)在反向掃描時必定可以得到種子點C，紫色部分格網(wǎng)是它們的重合部分。白色部分格網(wǎng)想要得到種子點C就需要反向掃描時藍色格網(wǎng)的傳遞，如果傳遞被阻隔的話(例如圖2)，那么部分格網(wǎng)就不能得到其正確歸屬，造成單元歸屬出錯。從上面的分析可以看出：可能出現(xiàn)歸屬錯誤的區(qū)域單元(圖6白色單元)位于其正確種子點的左下方(Ⅰ區(qū))與右上方(Ⅱ區(qū))。

2.2 改進方法

在找到了出現(xiàn)單元歸屬錯誤的區(qū)域后，本文設(shè)計了一種水平掃描后接豎直掃描的解決方案。豎直掃描保持?jǐn)?shù)據(jù)結(jié)構(gòu)不變，掃描模板仍為3×3模板(如圖1所示)。豎直掃描方向為豎直方向，掃描順序為先從左上角開始由下至上的逐列向右掃描一次為正向掃描，模板中心格網(wǎng)P從Q1、Q4、Q6和Q2這4個鄰近格網(wǎng)中得到其最近種子點。再從右下角開始從下至上的逐列向左掃描一次為反向掃描，模板中心格網(wǎng)P從Q8、Q5、Q3和Q2這4個鄰近格網(wǎng)中得到其最近種子點。正反兩次掃描稱為一個豎直掃描周期。

與水平掃描周期相同，豎直掃描周期正反掃描同樣具有類似的過程，其結(jié)果如圖7所示，其中圖7(a)為單次正向掃描后的結(jié)果，圖7(b)為單次反向掃描后的結(jié)果。

水平掃描后接豎直掃描的解決方案對一個格網(wǎng)進行兩個周期共4次掃描，可以完全覆蓋該種子點周圍所有區(qū)域，如圖8所示。藍色格網(wǎng)為豎直周期正向掃描覆蓋區(qū)域，綠色格網(wǎng)為豎直周期反向掃描覆蓋區(qū)域，紫色區(qū)域為他們重合區(qū)域。左側(cè)的淺綠色區(qū)域(Ⅰ區(qū))和右側(cè)的淺藍色區(qū)域(Ⅱ區(qū))為水平周期無法完全覆蓋的區(qū)域，但是可以被豎直周期覆蓋。這樣就保證了種子點周圍所有區(qū)域在經(jīng)過水平、豎直兩個周期掃描后都可以得到該種子點。

3 試驗與分析

確定歸屬算法是根據(jù)V圖定義，計算并比較所有柵格與每一個種子點之間的距離，來確定格網(wǎng)單元的最近種子點。其需要進行大量的距離計算與比較，隨著空間分辨率的增大，要處理的數(shù)據(jù)量急劇上升，算法效率大大降低，實際操作性較差。但是其算法精度高，相較于正確矢量結(jié)果，其誤差在一個格網(wǎng)以內(nèi)。因此，本文選擇確定歸屬算法作為算法精度評判的基準(zhǔn)。

本文算法所用的編程語言為C++，顯示所用的三維圖形接口為Microsoft OpenSceneGraph SDK (17.1)，硬件環(huán)境為Intel(R) Core(TM) i5-3337U CPU @1.80 GHz， 2.70 GB內(nèi)存。并與改正前算法和確定歸屬算法在精度和效率方面進行了對比，如圖9為改正后算法在10、100和1000種子點數(shù)量時生成的結(jié)果示意圖，表1為確定歸屬算法、原掃描算法和改正后的算法在不同格網(wǎng)數(shù)和不同種子點數(shù)情況下所花費的時間。

表1 不同算法生成V圖所用時間

由表1可以看出，在格網(wǎng)數(shù)和種子點數(shù)較少情況下，確定歸屬算法與掃描算法效率相差不大。但是在數(shù)據(jù)量較大的情況下，掃描算法具有明顯的速度優(yōu)勢，且隨著格網(wǎng)數(shù)和種子點數(shù)量的增加這種優(yōu)勢越來越明顯。而改進后掃描算法與原算法效率大體相當(dāng)。

圖10為在3000×3000格網(wǎng)數(shù)情況下，3種算法所需時間隨種子點數(shù)量增加而變化的情況，確定歸屬算法在10 000種子點數(shù)量情況下由于所需時間太長而無法在圖中表示。由圖可以看出，確定歸屬算法那所需時間隨種子點數(shù)量增加而劇烈增加，而掃描算法時間幾乎不變。改正后的算法在時間上略高于原算法，但遠低于確定歸屬算法。

(2)

表2 算法的誤差分析

注：表中數(shù)字表示100次隨機試驗中兩種算法得到的格網(wǎng)的最大誤差在各區(qū)間的數(shù)量。

圖2 出現(xiàn)錯誤的原因Fig.2 Reason of sweeping errors

圖3 一周期水平掃描后出現(xiàn)的誤差Fig.3 Errors after the horizontal cycle sweeps

圖4 單次正向掃描結(jié)果Fig.4 Result of single positive scan

圖5 單次反向掃描結(jié)果Fig.5 Result of single reverse scan

圖6 正反掃描后一定能得到種子點的區(qū)域Fig.6 The area which can get the seed point after the positive and reverse scanning

圖7 豎直掃描周期單次正反掃描后結(jié)果Fig.7 The result of single positive and reverse scan of vertical scanning cycle

圖8 水平加豎直兩周期掃描后結(jié)果Fig.8 The results of horizontal plus vertical two-period scan

圖9 不同種子點數(shù)生成結(jié)果示意圖Fig.9 The results of different seed points

圖10 各算法效率情況Fig.10 The efficiency of different algorithms

由上表可以看出，原算法大概率會出現(xiàn)單元歸屬錯誤，且誤差隨數(shù)據(jù)量的增加而增加，嚴(yán)重影響了某些需要高精度的應(yīng)用，而改進后的算法，以確定歸屬算法生成結(jié)果為基準(zhǔn)，生成的V圖把每個格網(wǎng)的誤差都控制在了一個格網(wǎng)以內(nèi)，所以本文提出的算法達到了與確定歸屬算法相當(dāng)?shù)木取?/p>

4 結(jié) 論

本文在深入分析了傳統(tǒng)掃描算法產(chǎn)生誤差缺陷的原因和區(qū)域特征后，在傳統(tǒng)柵格掃描算法基礎(chǔ)上，提出了一種基于橫-縱掃描的V圖生成改進算法，并進行了相關(guān)效率和精度試驗，結(jié)果表明：

(1) 改進后的算法保留了掃描算法效率上的優(yōu)勢，在大數(shù)據(jù)量情況下速度遠高于確定歸屬算法，與原掃描算法的效率基本一致。

(2) 改進后算法彌補了原算法不完備的掃描缺陷，在高效生成的同時把誤差限制在一個格網(wǎng)以內(nèi)，達到了與確定歸屬算法相當(dāng)?shù)木取?/p>