Voronoi圖的性質及離散構造綜述

劉　欣,李海明，劉穎華

(承德石油高等專科學校 社科與數理部，河北　承德　067000)

?

Voronoi圖的性質及離散構造綜述

劉欣,李海明，劉穎華

(承德石油高等專科學校 社科與數理部，河北承德067000)

摘要：本文給出Voronoi圖的背景和定義以及應用概述，在介紹傳統算法的基礎上，介紹擴展Voronoi圖的離散構造算法，即直接從離散的生成元點出發，而不需要考慮生成元的具體形狀，避免了對Voronoi邊的形狀的計算，對使用計算機算法提供了有效依據。

關鍵詞：Voronoi圖；離散Voronoi圖；離散構造

Voronoi圖概念最早源于以下自然問題：宇航員研究宇宙結構；考古學家試圖識別不同部落影響下的地區；氣象學家在儀器不靈時估算降雨(雪)量；城市規劃者在城市中進行公共學校定位[1]；物流園區范圍的設定等。它們雖然表面涉及了完全不同的現象，但具有一點共同之處，即都可以用Voronoi圖的概念來解決。

1Voronoi圖背景

1.1Voronoi圖的定義

給定平面上有限個(大于1個)孤立點的集合，我們依照歐氏距離將平面上的所有位置點分配給點集中距它最近的點。結果將平面分成了一個網格，這個網格中的區域與平面給出的點集有關，我們稱這個網格為由這個點集生成的平面普通Voronoi圖，形成Voronoi圖的區域為普通Voronoi多邊形。在不混淆的情況下，簡稱普通Voronoi圖為Voronoi圖，普通Voronoi多邊形為Voronoi多邊形。

下面給出精確的數學語言描述：

定義設P={p1,…,pn}∈R2,2≤n<∞,xi≠xj(i≠j),i,j∈In={1,…,n}，稱由下式

(1)

給出的區域為與點pi關聯的普通平面Voronoi多邊形，由Vor={V(p1),…,V(pn)}給出的集合為由P生成的平面普通Voronoi圖[2](或簡稱P的Voronoi圖)。我們稱Voronoi多邊形的頂點為Voronoi頂點，V(pi)中的pi為生成元點，集合P={p1,…,pn}為Voronoi圖Vor的生成元集。

有時可以簡單的將V(pi)記作Vi。用V(xi1,xi2)或V(xi)表示，如果想特別指出生成元集P的Voronoi圖，也可以用Vor(P)。圖1顯示了一個平面普通Voronoi圖的實例。

1.2Voronoi圖的基本性質

性質1生成元pi的Voronoi區域V(pi)無界的充分必要條件是pi∈BCH(P)，其中，BCH(P)表示生成元集合P的凸殼邊界[3]。

性質2n個點的點集P的Voronoi圖至多有2n-5個頂點和3n-6條邊。

性質3在不退化的情況下，每個Voronoi頂點恰好是三條Voronoi邊的交點。

1.3Voronoi圖的應用概述

Voronoi圖概念最初研究的是有規律的分布于空間上的點，起源于19世紀晚期。經過一百多年的發展，Voronoi圖已經廣泛應用于實際生活的各個領域。首先是Voronoi圖在計算幾何理論中的應用，Voronoi圖在計算幾何當中，常用來解決最近鄰近問題；Voronoi圖在模式識別領域中也有很多應用，尤其是在機器人路線設計領域中的應用更為突出。同時，也有不少應用對Voronoi圖理論提出了新的要求，等待理論上的新成果問世。

2Voronoi圖的傳統算法

Voronoi圖的概念到19世紀70年代早期，發展了許多二維和三維Voronoi圖的算法，Voronoi圖的構造方法在最近幾十年中得到了快速的發展。有半平面的交算法、隨機增量等傳統算法，隨后重點介紹具有較高效率的離散生成算法。

2.1半平面的交算法

半平面的交是生成Voronoi圖的最直接的方法。它直接利用Voronoi圖的定義，即對點集P中的每一個生成元點pi，確定該點與其它所有生成元點之間的等分線，每條等分線將平面分為兩個半平面，構造n-1個半平面的交集，得到點集P的Voronoi圖。

2.2隨機增量算法

與第一個算法相比，隨機增量算法更快速有效。基本思想是數學歸納的“追加法”概念。假設點集P={p1,p2,…,pn}，已構造出k(k

2.3分治法

3Voronoi圖的離散構造算法

3.1離散Voronoi圖的定義

對屏幕上任一像素點p(x,y)，(0≤x≤k,0≤y≤l)，其中，x和y為整數，k和l分別為屏幕坐標系中橫、縱坐標的最大值。設屏幕像素點的集合P={p1,p2,…,pn}，則由像素點pi確定的離散Voronoi區域定義如下：

(2)

由該定義得到的Voronoi圖稱為二維離散Voronoi圖，p1,p2,…,pn為生成元點。如果屏幕上某一像素到兩生成元點的距離相等，則該像素屬于下標較小的生成元點所在的Voronoi區域(見圖2)。

3.2離散Voronoi圖構造思想

首先對每一個生成元點指定一種顏色，使不同生成元點之間的顏色互不相同；然后以每個生成元點為圓心，圍繞它以該生成元點的顏色畫圓；在給像素點涂顏色之前先進行判斷：如果該點已經有了顏色，就越過，否則就給該像素點涂上指定顏色；當屏幕上所有的像素點都畫上了顏色時，結束。此時，不同顏色的像素之間即為Voronoi邊。圖3以三個生成元點為例，顯示了平面Voronoi圖的離散生成過程。

需要注意的是，按照定義，到若干個生成元點距離相等的像素，屬于下標較小的生成元點的Voronoi區域。因此，畫圖時先從下標小的生成元點畫起，即按生成元點的下標從小到大畫圓。

4Voronoi圖的應用

Voronoi圖在其它許多方面如：數據壓縮、圖象處理、通訊中的頻率分配[4]、皮膚紋路的模擬、神經網絡、地域規劃[5]以及物理學、生態學、經營學、調查學、靜態學、考古學等學科都有著廣泛的應用，此類問題均可由Voronoi圖理論及推廣成果加以解決。

參考文獻：

[1]鄧平，王志城.基于Voronoi 圖的農村居民點空間分布特征研究[J].地理空間信息,2015(1)：125-127.

[2]周德培.計算幾何-算法分析與設計[M ].北京:清華大學出版社, 2000.

[3]劉金義，劉爽.Voronoi圖應用綜述[J].工程圖學學報,2004(2):125-132.

[4]禤家裕.基于Voronoi圖的應急通信系統基站選址方法研究[J].信息通信,2014(6)：61-65.

[5]王新生.Voronoi圖和非數值隨機優化算法在城市與區域規劃中的應用研究[D].武漢:武漢大學,2012.

Nature of Voronoi Diagram and Dynamic Structure

LIU Xin, LI Hai-ming, LIU Ying-hua

(Department of Social Sciences, Mathematics and Physics, Chengde Petroleum College,Chengde 067000, Hebei, China)

Abstract:This paper presents the background and definition of Voronoi diagram, and application overview presentation on the basis of the traditional algorithm, it also gives the extension of the discrete Voronoi diagram construction algorithm. That is, starting directly from generators at discrete points without regard to the specific generator shape, which avoids computing Voronoi edge shape, and provides an efficient algorithm for computing.

Key words:Voronoi diagram; dynamic Voronoi diagram, discrete construction

基金項目：承德市軟科學研究計劃項目(基于Voronoi圖的承德物流園區腹地界定及強度提升研究)：20153019；河北省高等學校人文社會科學研究規劃項目(高職院校數學課程“模塊化-案例驅動-上機實踐”三位一體教學模式研究與實踐)：GH151013；河北省高等學校科學研究青年基金項目：(高職高專高等數學分級教學的研究與實踐)：SQ141019

收稿日期：2015-11-01

作者簡介：劉欣(1977-)，女，河北承德人，承德石油高等專科學校社科與數理部副教授，碩士，研究方向為應用數學、計算幾何、數學建模等。

中圖分類號：TP391.41

文獻標識碼：A

文章編號：1008-9446(2016)02-0041-03