1、Voronoi圖的構建和應用侯玉昭（南京航空航天大學機電學院，南京市，210016）摘要：Voronoi圖是計算幾何中常用而又重要的幾何結構，它有很強的實用價值。本文介紹了平面點集上的Voronoi圖的一些生成方法，主要是矢量法和柵格法的原理與生成過程。其次就是V圖在各個領域中的應用和分析了 V圖的一些優勢特點。以此希望我國科研人員關注V圖的研發工作。關鍵詞：Voronoi圖；矢量法；柵格法；V圖應用Construction and application of V oronoi diagramHou Yuzhao(College of Aerospace Engineering, Nanji

2、ng University of Aeronautics & Astronautics, Nanjing, 210016, China;)Abstract: Voronoi graph is a common and important computational geometry in diagram geometry,it has a strong practical value.This paper introduces some generation method for planar point set on the Voronoi graph,it is mainly th

3、e principle and formation process of the vector method and the grid method.The second is the application of V graphs in various fields and analyzes some advantages of V graphs. We hope our researchers focus on R&D of V graph.Key words : Voronoi graph;Vector method;Grid method;Application of V or

4、onoi graph引言Voronoi圖的歷史是相當古老的。許多不同的自然結構都與Voronoi圖十分接近，并且這些結構曾經被很多早期的科學家甚至普通人注意過。早在1908年，俄國數學家G.Voronoi在對二次型的研究中首先使用了這種圖，后被計算機研究者稱之為Voronoi圖。1944年，笛卡爾使用了一種圖來顯示太陽系內部和外部物質的性質。盡管沒有特殊的注解來解釋那些圖的結構，但實際上這些圖已經十分接近今天我們所說的加權Voronoi圖。Voronoi圖在許多領域都在嘗試它的應用，并取得了成功。如天文學家用來研究宇宙結構；考古學家用來識別新石器時代不同部落影響下的地區；氣象學家在儀器分布不足

5、時估算降雨（雪）量；城市規劃者在城市中用來進行設施定位；生物學家用來研究毛細血管供應肌肉組織情況。這些研究表面上涉及完全不同的現象，但實際上都可以用Voronoi圖的概念來解釋。近年來，Voronoi圖已被納入計算幾何的范疇，成為計算幾何的一個重要分支。隨著計 算機科學與技術的飛速發展，尤其是計算機在圖像處理方面的廣泛應用，使得計算幾何的研究，越來越受重視并日益蓬勃發展起來。計算幾何在計算機輔助設計、計算機圖形學、數字圖像處理、地理信息處理、機器人等許多領域都有重要應用。它已成功解決了找最近點，求最大空圓，求 n個點的凸包，求最小樹等問題。另外，Voronoi圖在模式識別、生態研究、城市規劃、

6、最優化配置、物理學等許多領域也有廣泛的應用1。Voronoi圖構建V圖有著按距離劃分鄰近區域的普遍特性，應用范圍廣。生成V圖的方法很多，一般分為兩種：矢量方法；柵格方法。1.1矢量方法（基于GIS軟件）矢量方法生成 V圖大多是對點實體。 方法分為：對偶生成法；增添法；部件合成法等。1.1.1對偶生成法對偶生成法：主要是指生成V圖時先生成其對偶元 Delaunay三角網，再通過做三角網每一三角形三條邊的中垂線，形成以每一三角形頂點為生成元的多邊形網。如圖1所示。圖2增添法圖2增添法圖1對偶生成法生成V圖對偶生成法的關鍵是 Delaunay三角網的生成。Delaunay三角網的特性：任一三角形外

7、接圓內部包含其他點；三角形均衡或三邊均衡，其最小角最大；使三角網總邊長最小；在確定的n個點上，構造的 Delaunay三角網網形唯一。1.1.2增添法增添法生成 V圖的基本思想是：假設平面上原有n個點（生成元），已生成了 Vn圖,現在增加一個生成元 Pn+1，這時生成新的 Vn+i圖。由于V圖的特性，加入一個新生成元只 與該新生成元所在 Voronoi多邊形及與之相鄰其它 Voronoi多邊形"迎向半邊”有關，與這 些多邊形的“另半邊”無關，也與除它們之外的其它生成元的Voronoi多邊形無關。增添法的基本步驟： 搜索最鄰近單元和相鄰單元。最鄰近單元為Pn+i所在原V圖中某點的Vor

8、onoi多邊形Vk以及原來與它相鄰的若干個多邊形及相應生成元，如圖2（a）。 局部更新。對于各鄰近單元，首先與最鄰近單元Vk中Pk作中垂線，并找其余Vk的交點，由于Vk是凸多邊形，因而只產生兩個交點1、2, 1與2連線把與Vk相關的單元分為“兩半”：與Pn+1相關的一半”及“不相關的一半”，使Pn+1與相關一半的各生成元Pk+1 , Pk+2Pn+1生成元后的新的Vn+1圖。類此，可不斷加入新作中垂線圍成各封閉多邊形，即是加入 的生成元，直至所需。如圖 2 （b ）。(a)(b)圖2增添法1.1.3部件合成法部件合成法：是指把生成元點集分為若干個子集，并且這些子集的并集必須為生成元點集，為避免

9、不必要的麻煩，這些子集相互的交集盡可能小或為空集心先對這些子集生成子V圖，然后把這些子 V圖合并，修正其相互影響部分的Voronoi多邊形，從而得到全生成元點集的V圖。如下圖3所示。矢量方法生成 V圖的分析：以上三種方法是矢量方法中常用的，隨著并行處理技術的發展，V圖生成頁、也出現了并行算法，它使各生成元同時進行各點的V圖計算；矢量方法生成V圖的算法和數據結構都較為復雜，其生成元是基于離散點集的，對 于實際的地理信息，這遠遠不夠，應該拓展成點、線、面、體及其組合的復雜形體； 目前矢量方法用離散點集代替線面，使空間實體的完整性遭到破壞，同時生成的V圖，要經過復雜的識別和修補工作，這是一個尚待克服

10、的困難；對于光滑、不光滑組合曲線及相應組合成的封閉面域，盡管可用折線逼近，但折線 畢竟不是曲線，在曲線光滑處，每一點都是轉折點，而化為折線，折線交接處的點 就成為唯一轉折點，性質突變處。1.2柵格方法(基于GIS軟件和編程)目前利用矢量法生成的Voronoi圖的算法和數據結構復雜，其生成元基于離散點集，對于線、面和其他更復雜的空間目標需分解為點集進行處理。這種分解使空間實體的完整性遭到破壞，同時生成的Voronoi圖需經過復雜的識別和修補。由于基于矢量方法生成的矢量Voronoi圖存在的問題和不足，進而提出基于柵格方法生成柵格Voronoi圖。距離變換是基于柵格方法的核心，下面給出了利用基于柵

11、格方法生成Voronoi圖的原理和步驟。任意形狀發生元Voronoi圖構建的柵格方法：1dw(p，Pi)d(p, pj - Wi2，WiiWi >0、W2是加權Voronoi圖的權重。當 W2=0 時產生倍增的加權 Voronoi 圖(multiplicatively weightedVoronoi diagram ),是在發生點集的擴散速度與權重成比例情況下形成的；當 W1 =1 時產生相加的加權 Voronoi 圖(additively weighted Voronoi diagram )；當w豐1, W2工0時產生復合的加權 Voronoi圖(compoundly weighted

12、 Voronoi diagram )。下面介紹加權 Voronoi圖的柵格構建方法：用 gridpoint 命令將包含有空間點位坐標的矢量圖層數據轉換為柵格數據，并把柵格 數據放置在一個文本文件中。利用方程計算每一個柵格單元與各發生點的加權距離，以距離最短的發生點柵格的 代碼作為該柵格單元的隸屬代碼，如此下去，直至所有柵格單元的歸屬都被確定為 止。把新的柵格單元代碼數據寫入到一個新的文本文件中，再用 gridpoly 命令將該代碼 數據轉變為一個點的加權 Voronoi 圖圖層（在該方法的實現中，注意數據轉換中所 需要的文件頭的內容） ，完畢 。下面是對柵格方法的一些改進性研究。 如李成名等提

13、出一個基于鄰域擴張的 Voronoi 圖 生成算法 ,分析了利用傳統的距離變換生成柵格Voronoi 圖的誤差情況 ,對各種柵格算法的精度進行了分析 ,并引入動態距離變換的柵格鄰域擴張模式。王新生等提出了一種新的基于柵 格的 Voronoi 生成方法 ,通過確定每個柵格的歸屬來定義Voronoi 區域 ,為了減少計算時間 ,設計了一種搜索某個柵格所屬最近發生元柵格的方法。 柵格法的核心問題是柵格空間中兩點的 距離定義 ,關于柵格的距離典型定義有 :街區距離、棋盤距離、八角形距離、斜面3-4 距離、斜面 2-3 距離 ,無論是普通 Voronoi 圖還是加權 Voronoi 圖 ,這些距離計算的

14、前提是每個柵格是 等距的基元。故馬林兵提出一個非均質柵格 Voronoi 圖的生成方法 24 。V 圖的意義和應用2.1 V 圖的特點Voronoi 多邊形圖由點集生成擴展為由點、線、面集生成后， V 圖就具有了以下特性：（ 1）每個 V 多邊形內有一個生成元；（ 2）每個 V 多邊形內點到該生成元距離短于到其它生成元距離；（3）多邊形邊界上的點到生成此邊界的生成元距離相等；（ 4）鄰接圖形的 Voronoi 多邊形界線以原鄰接界線作為子集。V 圖是空間鄰近關系客觀、全面、準確的體現， V 圖給出了鄰近的準確量度。鄰近決定 于空間尺度 , 是一種幾何關系 ,而“鄰”是一種拓撲關系 , 兩者不一

15、樣。復雜的連續函數內插 要在鄰近點間進行， V 圖給出了主影響元、鄰近影響元，提供了優良內插方法的優秀環境。V 圖、障礙 V 圖、廣義 V 圖的多邊形邊界提供了點、線、面全形態，障礙、非障礙完 備空間，廣義加權距離的等距線、等比線、等勢線等，是具有嚴密數學意義且極廣泛使用價 值的軌跡線。2.2 V 圖的應用Voronoi 圖的在計算幾何學科中的重要地位，是由于 Voronoi 圖在求解點集或其它幾何 對象與距離有關的問題時起的重要作用而決定的。 這種根據 Voronoi 圖的性質對區域的合理 劃分，廣泛應用在地理學、氣象學、結晶學、航天、核物理學、機器人等領域。例如，它可 以應用于運動規劃問題

16、， 即在充滿障礙物的環境中為機器人尋找一條無碰撞的路徑 解決的 方法，可以利用障礙物的 Voronoi 圖，因為它描述出了距離障礙物最遠，也就是最安全的路 徑。隨著 Voronoi 圖的定義和算法被廣泛傳播， Voronoi 圖的應用領域也在不斷擴展。這些 應用實例盡管從專業角度千差萬別，但從 Voronoi 圖所發揮的作用角度，可以歸結為如下 3 個方面：（ 1）把 Voronoi 圖作為表示各種元素之間關系的一個結構，通過這個結構可以提取出 重要信息。這樣的實例多見于用 Voronoi 圖研究自然界物質結構的性質。例如 Nullans 等將 Voronoi 圖用在了地質結構的幾何模型重構中

17、，目標是將不同巖性的地質結構表示為不同的實體， 以便工程設計與分析之用。 他們首先對各種工程地質勘探數據 進行預處理，得到一個帶顏色的點集(巖性相同的點具有相同的顏色)；然后以這些帶顏色點為站點作出 Voronoi 圖；最后再合并顏色相同的 Voronoi 區域，將相鄰的且巖性相同的地質 結構表示為同一實體。 如果不考慮地質結構的方向異性因素， 這種方法所確定的地質結構分 布范圍應是非常合理的。 這種方法也適合于根據 CT 數據重構人體組織器官的幾何模型，比 連接等高輪廓線的方法更具有通用性( 2)把 Voronoi 圖作為一個輔助數據結構，通過這個數據結構可以完成許多物體形態 或鄰近關系的計

18、算任務。例如，近年來， Voronoi 圖被廣泛地用在分析蛋白質等生物大分子的結構。在此領域， 人們一般首先用 X 射線衍射測量的方法或分子動力計算的方法得到蛋白質表面上原子的位 置和溶劑分子的位置。然后以蛋白質原子和溶劑分子為站點生成三維 Voronoi 圖，把蛋白質 原子的 Voronoi 多面體加在一起就可以得到蛋白質分子的體積， 進一步還可以得到可接觸表 面積和包裝密度等參數。在這里之所以采用 Voronoi 圖進行計算，而不是把原子看成球體來 計算，是因為人們不必關心蛋白質內部的原子類型和位置。 在此領域， 在一個分子中原子之 間的距離比較近，如果不區分原子的大小而一概以原子的中心為

19、站點劃分 Voronoi 圖，小原 子計算出的體積比實際要大， 大原子計算出的體積比實際要小。 為解決此問題， 人們也提出 了各種方法。 Gerstein 等的方法是先計算出普通的 Voronoi 圖，然后在根據原子的大小對 Voronoi 多面體加以調整。 Will 引入了考慮原子半徑的加權 Voronoi 圖，即每個 Voronoi 區域 是距離原子表面最近的區域，并且給出了這種 Voronoi 圖的生成算法。( 3)把 Voronoi 圖作為提高某些幾何算法運算速度的重要手段。一般來說，二維的Voronoi圖可以在 0(nlogn)時間內獲得，三維的 Voronoi圖可以在 0(n2)時

20、間內獲得。Voronoi 圖的性質決定了它與許多其它幾何結構具有內在關系，通過Voronoi 圖，許多幾何算法可以得到快速運算。Fujita 等應用 Voronoi 圖求解約束非線性規劃問題。 Voronoi 圖在這里的作用是獲得目標 函數和約束函數的逼近函數， 然后用逼近函數去求最優解， 這樣可以使求梯度的解析過程得 到簡化。 求解過程是一個迭代過程， 首先在參數空間隨機地選取一些采樣點， 如果由這些點 確定的最優解可信度足夠大，則停止；否則，在可能產生最優解的Voronoi 區域內插入新的采樣點，繼續迭代，直到得到一個可信的最優解或迭代到指定次數為止3。總結Voronoi 圖是一種很基本的幾何數據結構， 在解決很多的實際問題中有許多應用。Voronoi圖是一個內容豐富龐雜的研究課題，對于這個問題，有著廣泛的應用背景。國外在Voronoi圖方面的研究開展的很廣泛、 很深入， 而國內專門從事這方面研究的人很少。 因此國內人士 應加強對 Voronoi 圖理論和應用的研究，充分認識 Voronoi 圖的重要性與實用性，吸引更多 的研究人員關注這個領域。參考文獻：1. 宗大偉 .Voronoi 圖及其應用研究 D ：南京：南京航空航天大學， 2006.Zong Dawei.Study on Voronoi diagram and