對Voronoi圖生成的矢量和柵格算法的分析評價

[摘 要]對現有Voronoi圖的生成算法進行深入研究，從多種角度對Voronoi圖生成的矢量算法和柵格算法進行了分析，并針對這兩種算法的優點與不足進行了比較和評價。

[關鍵詞]Voronoi圖 基于矢量的算法 基于柵格的算法 算法評述

[中圖分類號]O1 [文獻標識碼]A [文章編號]1009-5489(2009)12-0198-03

Voronoi圖在不同的科學領域都有應用和發展，許多人對Voronoi圖進行了綜述和評價。Aurenhammmer于1991年發表了一篇關于Voronoi圖的歷史、定義、性質、算法、擴展和應用的綜述。Fortune于1992年側重對Voronoi圖的算法進行了比較和分析。關于Voronoi圖生成算法的文獻已有很多，但很少涉及到Voronoi圖生成的矢量和柵格算法比較分析。本文在介紹Voronoi圖的基礎上，側重對這兩種進行分析和評價。

一、Voronoi圖的定義

Voronoi圖是在計算幾何中被廣泛研究的一個問題，其原理非常簡單，是一種由點內插生成面的方法。根據有限的采樣點數據生成多個面區域，每個區域內，包含一個采樣點，且各個面區域到其內采樣點的距離小于任何到其他采樣點的距離，那么該區域內其他未知點的最佳值就由該區域內的采樣點決定，該方法也稱最近鄰點法，用于鄰域分析。其幾何定義為:假設P={P1，P2，...，Pn}(3≤n≤∞)是歐幾里德平面上的一個離散點集，并且這些點不共線，四點不共圓，用d(Pi，Pj)表示點Pi，Pj的歐幾里德距離。設x為點集P上的點，則區域V={x∈E2|d(x，pi)≤d(x，pj)，j=1，2，...，n，j≠i}稱為Voronoi多邊形，各點的Voronoi多邊形共同組成Voronoi圖(如圖1所示)。

圖1 Voronoi圖

二、Voronoi圖生成算法評價

Voronoi圖的構建構建方法很多，可歸結為基于離散點的矢量坐標來實現和基于柵格的擴張原理來進行。

1.矢量Voronoi圖生成算法評價

矢量Voronoi圖的生成方法有多種，散見于國內外不同領域的研究刊物和文獻上，如根據周培德研究，構建Voronoi圖的矢量算法有分治算法、減量算法、增量構造算法、平面掃瞄算法、間接法等幾種。

利用基于矢量方法生成Voronoi圖，優點是:Voronoi數據的存儲結構簡單，存取便捷，便于實際應用。缺點是:①生成Voronoi圖算法不僅計算復雜，而且占用的計算機空間開銷大，由該類方法產生的數據結構復雜，其存儲量可達到原幾何數據的9～10倍，因此，雖然Voronoi圖應用到GIS中使查詢效率提高，但這種查詢效率的提高是建立在空間開銷增大基礎之上的。②矢量法構建Voronoi圖，處理的生成元只能是點和線(或半線)，生成線集的Voronoi圖比較困難，對于面和其他更復雜的空間目標要分解為點和線(半線)來處理，這種分解破壞了空間目標的完整性。③由于算法復雜，計算機難于實現，不易向高維目標或高維空間擴展。

Aurenhammer和Edelsbrunner提出了構建倍增的加權Voronoi圖的算法，是一種基于矢量方法的算法，實現了點的加權Voronoi圖，可基于這種算法，生成某省份多個城市(如河南省38個城市)的加權Voronoi圖，分別計算一這些城市單元影響區的變化，一方面可得出城市中心性強度的差異性，另一方面也可直觀地看出這些城市在空間分布上的不均衡性。

當前，較高版本的GIS軟件(如Arc/Info)可以實現普通的Voronoi圖，但在具體實現過程中仍存在著問題，如:美國的Gahegan和澳大利亞的Lee共同開發的軟件可生成六種Voronoi圖，用其開發的Demo軟件課可實現點集的動態倍增的加權Voronoi圖，但其演示效果并不理想，如，當點的數量較多時會出現錯誤。在對大量的點集或遇到復雜發生元的情況下，基于矢量方法的算法的有效性和穩健性受到限制，構建Voronoi圖有一定的困難。

2.柵格Voronoi圖生成算法評價

柵格Voronoi圖的生成算法主要有距離變換算法、鄰近柵格擴張法、柵格鄰近歸屬法等幾種。

利用基于柵格方法生成的柵格Voronoi圖的優點表現在:①Voronoi圖及其直線對偶的算法更容易從低維目標和低維空間向高維擴展。②處理GIS中線、面或更復雜的空間目標同處理點的方式方法一樣。③基于柵格方法生成Voronoi圖的算法復雜性小，易于在計算機上實現。

利用基于柵格方法生成的柵格Voronoi圖的缺點表現在:①Voronoi數據的存儲結構復雜，占據的存儲空間大;②計算歐幾里德距離時，柵格空間中的單位是像素，點與點之間的距離不是一個整數，如點(1，1)與點(2，2)之間的距離為2，不便于計算，一般用整數近似代替。所以選擇的整數直接影響到生成的Voronoi圖的精度。③離散采樣點通常情況下是矢量數據，在進行矢量數據到柵格數據的轉換過程中柵格尺寸的選擇會影響Voronoi圖的生成質量。

下面以距離變換算法來分析評價柵格算法。

通常情況下，用最大偏差(Maxdiff)作為由距離變換生成的柵格Voronoi圖評價指標。為方便計算，本文采用3×3、7×7局部模板，見圖2(Ⅰ)—(Ⅱ)，圖中的a、b和c的取值需滿足1

baba0abab

edde

ecce

dcbabcd

a0a

dcbabcd

ecce

edde

(Ⅰ) (Ⅱ)

圖2 常用局部模板

最大偏差是指在某一固定距離下，任意方向上的整數近似距離與歐幾里德距離都有差異，其中絕對值最大者即為最大偏差。設M表示水平方向上的距離。對于3×3模板的最大偏差為:

Maxdiff=Max(1-2b-b2，|b-2|)×M(1)

對于7×7模板的最大偏差為:

Maxdiff=Max(diff1，diff2，diff3，diff4，diff5，diff6，diff7，diff8)(2)

其中

diff1=〔1-1-(d-3)2〕×M

diff2=(d-10)×M3d

diff3=〔d-c-1-(3c-d)2〕×M

diff4=(c-5)×M2

diff5=〔2c-e-1-(2e-3c2)〕×M

diff6=(e-13)×M3

diff7=〔b-e-1-(e-2b)2〕×M

diff8=(b-2)×M

根據式1、2，對于使用3×3、7×7模板定義的近似距離，a、b、c、e分別取不同的值，它與歐幾里德距離最大的距離偏差分別見表1和表2。

表1 3×3模板距離偏差

abMaxdiff

230.1340M

340.0809M

8110.0730M

11150.0685M

14170.0660M

19230.0644M

………

表2 7×7模板距離偏差

abcdeMaxdiff

14203144—0.0197M

15213347—0.0180M

17243853—0.0147M

19274260—0.0142M

12172738430.0140M

19274260680.0128M

可從表1和表2看出，a、b、c、d、e無論取何值，最大距離偏差總是與M成正比，M越大，最大距離偏差越大，由距離變換生成的柵格Voronoi圖與矢量Voronoi圖差異就越大。對于一個點而言，在矢量空間，歐幾里德距離作用該點后，其結果是一個圓，在柵格空間里，不管所采用的模板多么近似歐幾里德距離，但兩者總是有差異，并且這個差異隨距離增大而增大。

三、結束語

Voronoi圖作為一種重要的空間插值方法，已被應用在與幾何信息相關的各個領域。近幾年來，對Voronoi圖算法的研究越來越多，本文深入研究了Voronoi圖的矢量算法和柵格算法，比較了它們的優點和不足，并以實例進行了分析評價。通過對這兩種算法的綜合分析評價，對Voronoi圖的生成算法有了更清晰深刻的理解，為快速、準確的生成Voronoi圖提供了參考，避免在生成Voronoi圖中浪費大量的時間，提高了生成效率。

[參考文獻]

[1]Aurenhammer F.Voronoi diagrams-a survey of a fundamental data structure.ACM Computing Surveys，1991，23.

[2]Fortune S.Voronoi diagrams and delaunay triangulations.In:Computing in Euclidean Geometry.Du D-Z and Hwang F，eds.，World Scientific，1992.

[3]周培德:《計算幾何——算法分析與設計》，清華大學出版社2000年版。

[4]Okabe A，Boots B，Sugihara K.Nearest neighbourhood operations with gener—alized Voronoi diagram.International Journal of Geographical Information Systems，1994，8(1).

[5]Okabe A，Boots B，Sugihara K，et al.Spa—tional tessellation:concepts and app— lications of Voronoi diagrams(second edition).New York:John Wiley and Sons，2000.

[6]李成名、陳軍:《Voronoi圖生成的柵格算法》，《武漢測繪科技大學學報》1998.9，23(3).

[7]Aurenhammer F，Edalsbrunner H.An optional algorithm for constructing the weighted Voronoi diagram in the plane.PatternRecognition，198，17(2).