張 娟， 杜全葉

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

1 Voronoi圖的基礎(chǔ)

1.1 Voronoi 圖的概念[1]

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

d(P左,P1)

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

圖2 n= 6時(shí)的一種Voronoi圖

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

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

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

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

3） 每個(gè)Voronoi 點(diǎn)恰好是3條Voronoi 邊的交點(diǎn)（Voronoi 點(diǎn)是S中3點(diǎn)形成的三角形的外接圓的圓心）。

1.3 Voronoi 圖的應(yīng)用

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

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

2 Voronoi 圖生成算法

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

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

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

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

2.2 減量算法

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

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

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

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

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

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

圖4 減量算法流程圖

圖5 實(shí)驗(yàn)結(jié)果

4 結(jié) 論

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

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

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

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

[2]劉金義, 劉 爽. Voronoi 圖應(yīng)用綜述[J]. 工程圖學(xué)學(xué)報(bào), 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]王曉東, 廖士中. 一個(gè)基于桶技術(shù)的平面點(diǎn)集Voronoi 圖增量算法[J]. 遼寧師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 2002, 25(2): 139-143.

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