增刪點后的Voronoi圖生成算法

張 娟， 杜全葉

（1. 蘭州交通大學(xué)，甘肅 蘭州 730070；2. 中國測繪科學(xué)研究院，北京 100380）

1 Voronoi圖的基礎(chǔ)

1.1 Voronoi 圖的概念[1]

如圖1，L是P1P2的垂直平分線，并將平面分成L左和L右兩部分，位于L左內(nèi)的點P左 具有特性：

d(P左,P1)

圖 1 V(P1)，V(P2)圖示

圖2 n= 6時的一種Voronoi圖

給定平面上n個點的點集S={P1，P2，…，Pn}，定義V(Pi)=H(Pi，Pj)，即V(Pi)表示比其他點更接近Pi的點的軌跡是n-1個半平面的交，它是一個不多于n-1條邊的凸多邊形域，稱為關(guān)聯(lián)于Pi的Voronoi多邊形或關(guān)聯(lián)于Pi的Voronoi域。

S中的每個點都可做一個 Voronoi多邊形，這樣的n個多邊形組成的圖稱為Voronoi圖，記作Vor(S)，其頂點和邊分別稱為Voronoi頂點和Voronoi邊，如圖2為n= 6時的一種Voronoi圖。Voronoi圖的定義可以推廣到三維或多維，也可以推廣到二階或高階（以2個站點或多個站點為一組來劃分臨近區(qū)域）[2]。1.2 Voronoi 圖的特性

1） 每個Voronoi多邊形內(nèi)僅含有一個離散點數(shù)據(jù)；

2） Voronoi多邊形內(nèi)的點到相應(yīng)離散點的距離最近；

3） 每個Voronoi 點恰好是3條Voronoi 邊的交點（Voronoi 點是S中3點形成的三角形的外接圓的圓心）。

1.3 Voronoi 圖的應(yīng)用

簡單來說，Voronoi圖是一個關(guān)于空間劃分的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)[2]，已知平面上有任意n個點，按照這些點的分布將平面劃分成n部分，從而得到一種對平面的劃分圖。Voronoi圖理論成功地解決了找最近點、求最大空圓、求n個點的凸包、求最小樹等問題，與其對偶圖Delaunay三角剖分已被廣泛地應(yīng)用到幾何形體重構(gòu)、計算機圖形學(xué)、圖像處理、模式識別、機器人運動規(guī)劃、分子生物學(xué)等眾多領(lǐng)域。

隨著計算機的發(fā)展和工程設(shè)計自動化的要求以及建立地理信息系統(tǒng)的需要，出現(xiàn)了用數(shù)字形式表示地面的方式，即“數(shù)字地面模型（DTM）”。而數(shù)字高程模型（DEM）中地表面形態(tài)只用點的高程來表示，具有存儲量小，可以進(jìn)行壓縮，便于使用管理的優(yōu)點，是目前使用最廣泛的地形模型[3]。DEM 中不規(guī)則三角網(wǎng) TIN的建立和優(yōu)化是地圖正射影像的一個基礎(chǔ)研究問題，其要求所建的TIN模型具有存儲效率高、數(shù)據(jù)冗余度小、圖形網(wǎng)格強度好、三角網(wǎng)拓?fù)潢P(guān)系強、且能較好地顧及地形特征等優(yōu)勢。用Voronoi圖及其對偶圖 Delaunay，發(fā)展了帶約束的D-網(wǎng)特征建模，充分地考慮了地形特征（如地性線、陡坎、地物地貌等）[4]。

2 Voronoi 圖生成算法

平面點集的Voronoi 圖構(gòu)造算法有多種：半平面的交、增量構(gòu)造方法、分治法、減量算法、平面掃描算法等，由于增量算法不僅適用于靜態(tài)點集，而且還適用于動態(tài)點集，因而受到重視[5]。本文為了方便實現(xiàn)增刪點式Voronoi 圖的動態(tài)生成，選用了聯(lián)機增量和減量算法。

2.1 聯(lián)機增量算法

已知點集S={P1，P2，…，Pn}，并設(shè)已經(jīng)構(gòu)造出k(k

算法中分別計算了Pi至P1，P2，…，Pi-1的距離，并相互比較求得與Pi最近的點，因此需要進(jìn)行i-1次的距離計算和i-2次的距離比較。因為n個點的Voronoi圖至多有3n-6條邊和2n-5個頂點，所以每個V多邊形邊的數(shù)目為一常數(shù)，修改與Pi關(guān)聯(lián)的Voronoi多邊形邊與頂點時，其邊數(shù)決定了計算的復(fù)雜性，即耗費常數(shù)時間[1]。

2.2 減量算法

已知點集S={P1，P2，…，Pn}的Voronoi圖，現(xiàn)刪除點Pi之后，要求構(gòu)造Voronoi圖Vor（{P1，P2，…，Pi-1，Pi+1，…，Pn}），算法流程圖如圖4所示。

圖3 聯(lián)機增量算法流程圖

執(zhí)行該算法時，首先判定點Pi是否為凸殼頂點或在凸殼內(nèi)，這需要求出凸殼CH(S)進(jìn)行比較，耗時為O(nlogn)。如果點Pi-1，Pi，Pi+1是凸殼邊界BCH(S)上連續(xù)的3個點，刪除點Pi后耗費O(log2n)時間可以恢復(fù) BCH(S-{Pi})，即判定Pi-1與Pi+1之間是否有新的凸殼頂點。刪去點Pi及Pi關(guān)聯(lián)的Voronoi多邊形的邊和頂點，修改相應(yīng)的Voronoi多邊形的邊和頂點，耗費常數(shù)時間。因此算法的時間復(fù)雜度為O(nlogn)[1]。

3 數(shù)據(jù)類型定義

在程序設(shè)計中，數(shù)據(jù)類型定義的好壞對程序設(shè)計的影響是很大的，良好合理的數(shù)據(jù)類型定義，將極大地方便程序中數(shù)據(jù)的處理，本文根據(jù)Voronoi邊和頂點在數(shù)據(jù)文件中的存儲方式定義及其相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，對其定義如下：

其中x，y為Voronoi點的位置坐標(biāo)，next為指向下一個點數(shù)據(jù)的指針，點和點之間以此指針相連形成單向鏈表，從而構(gòu)成Voronoi圖（圖5為任意添加12個Voronoi頂點后，算法運行得到的結(jié)果）。

圖4 減量算法流程圖

圖5 實驗結(jié)果

4 結(jié) 論

Voronoi 圖是計算幾何學(xué)科的一個重要結(jié)構(gòu)，它與一些自然結(jié)構(gòu)十分相像，已廣泛應(yīng)用于天文、地理、網(wǎng)絡(luò)等領(lǐng)域[6]。隨著計算機技術(shù)的普及和發(fā)展，Voronoi 圖的應(yīng)用范圍也在不斷擴大，可將其擴展到三維，用于DTM的建模等。本文實現(xiàn)了增刪點后Voronoi圖的生成，所選用的算法還存在著不足，需進(jìn)一步改進(jìn)：

1） 增量算法中每次增加點Pi需要進(jìn)行i-1次的距離計算及i-2次最小值比較，循環(huán)耗時。

2） 執(zhí)行減量算法時，每刪除一個點就要對與之關(guān)聯(lián)的Voronoi多邊形邊和頂點進(jìn)行修改，修改量大，影響算法效率。

[1]周培德. 計算幾何——算法設(shè)計與分析[M]. 北京:清華大學(xué)出版社, 2005: 88-101.

[2]劉金義, 劉 爽. Voronoi 圖應(yīng)用綜述[J]. 工程圖學(xué)學(xué)報, 2004, 25(2): 125-132.

[3]李德仁, 周月琴, 金為銑. 攝影測量與遙感概論[M].北京: 測繪出版社, 2001: 163-164.

[4]彭儀普, 劉文熙. Delaunay三角網(wǎng)與 Voronoi圖在GIS中的應(yīng)用研究[J]. 測繪工程, 2002, 11(3): 39-41.

[5]王曉東, 廖士中. 一個基于桶技術(shù)的平面點集Voronoi 圖增量算法[J]. 遼寧師范大學(xué)學(xué)報(自然科學(xué)版), 2002, 25(2): 139-143.

[6]秦志霞, 沈 煒, 劉文昊. 二維 Voronoi 圖刪除任意生成點算法研究[J]. 浙江理工大學(xué)學(xué)報, 2010,27(3): 421-425.