Voronoi圖的構(gòu)建和應(yīng)用

1、Voronoi圖的構(gòu)建和應(yīng)用侯玉昭（南京航空航天大學(xué)機(jī)電學(xué)院，南京市，210016）摘要：Voronoi圖是計(jì)算幾何中常用而又重要的幾何結(jié)構(gòu)，它有很強(qiáng)的實(shí)用價(jià)值。本文介紹了平面點(diǎn)集上的Voronoi圖的一些生成方法，主要是矢量法和柵格法的原理與生成過程。其次就是V圖在各個(gè)領(lǐng)域中的應(yīng)用和分析了 V圖的一些優(yōu)勢(shì)特點(diǎn)。以此希望我國科研人員關(guān)注V圖的研發(fā)工作。關(guān)鍵詞：Voronoi圖；矢量法；柵格法；V圖應(yīng)用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圖的歷史是相當(dāng)古老的。許多不同的自然結(jié)構(gòu)都與Voronoi圖十分接近，并且這些結(jié)構(gòu)曾經(jīng)被很多早期的科學(xué)家甚至普通人注意過。早在1908年，俄國數(shù)學(xué)家G.Voronoi在對(duì)二次型的研究中首先使用了這種圖，后被計(jì)算機(jī)研究者稱之為Voronoi圖。1944年，笛卡爾使用了一種圖來顯示太陽系內(nèi)部和外部物質(zhì)的性質(zhì)。盡管沒有特殊的注解來解釋那些圖的結(jié)構(gòu)，但實(shí)際上這些圖已經(jīng)十分接近今天我們所說的加權(quán)Voronoi圖。Voronoi圖在許多領(lǐng)域都在嘗試它的應(yīng)用，并取得了成功。如天文學(xué)家用來研究宇宙結(jié)構(gòu)；考古學(xué)家用來識(shí)別新石器時(shí)代不同部落影響下的地區(qū)；氣象學(xué)家在儀器分布不足

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

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

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

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

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

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

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

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

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

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

15、樣。復(fù)雜的連續(xù)函數(shù)內(nèi)插 要在鄰近點(diǎn)間進(jìn)行， V 圖給出了主影響元、鄰近影響元，提供了優(yōu)良內(nèi)插方法的優(yōu)秀環(huán)境。V 圖、障礙 V 圖、廣義 V 圖的多邊形邊界提供了點(diǎn)、線、面全形態(tài)，障礙、非障礙完 備空間，廣義加權(quán)距離的等距線、等比線、等勢(shì)線等，是具有嚴(yán)密數(shù)學(xué)意義且極廣泛使用價(jià) 值的軌跡線。2.2 V 圖的應(yīng)用Voronoi 圖的在計(jì)算幾何學(xué)科中的重要地位，是由于 Voronoi 圖在求解點(diǎn)集或其它幾何 對(duì)象與距離有關(guān)的問題時(shí)起的重要作用而決定的。 這種根據(jù) Voronoi 圖的性質(zhì)對(duì)區(qū)域的合理 劃分，廣泛應(yīng)用在地理學(xué)、氣象學(xué)、結(jié)晶學(xué)、航天、核物理學(xué)、機(jī)器人等領(lǐng)域。例如，它可 以應(yīng)用于運(yùn)動(dòng)規(guī)劃問題

16、， 即在充滿障礙物的環(huán)境中為機(jī)器人尋找一條無碰撞的路徑 解決的 方法，可以利用障礙物的 Voronoi 圖，因?yàn)樗枋龀隽司嚯x障礙物最遠(yuǎn)，也就是最安全的路 徑。隨著 Voronoi 圖的定義和算法被廣泛傳播， Voronoi 圖的應(yīng)用領(lǐng)域也在不斷擴(kuò)展。這些 應(yīng)用實(shí)例盡管從專業(yè)角度千差萬別，但從 Voronoi 圖所發(fā)揮的作用角度，可以歸結(jié)為如下 3 個(gè)方面：（ 1）把 Voronoi 圖作為表示各種元素之間關(guān)系的一個(gè)結(jié)構(gòu)，通過這個(gè)結(jié)構(gòu)可以提取出 重要信息。這樣的實(shí)例多見于用 Voronoi 圖研究自然界物質(zhì)結(jié)構(gòu)的性質(zhì)。例如 Nullans 等將 Voronoi 圖用在了地質(zhì)結(jié)構(gòu)的幾何模型重構(gòu)中

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

18、算任務(wù)。例如，近年來， Voronoi 圖被廣泛地用在分析蛋白質(zhì)等生物大分子的結(jié)構(gòu)。在此領(lǐng)域， 人們一般首先用 X 射線衍射測量的方法或分子動(dòng)力計(jì)算的方法得到蛋白質(zhì)表面上原子的位 置和溶劑分子的位置。然后以蛋白質(zhì)原子和溶劑分子為站點(diǎn)生成三維 Voronoi 圖，把蛋白質(zhì) 原子的 Voronoi 多面體加在一起就可以得到蛋白質(zhì)分子的體積， 進(jìn)一步還可以得到可接觸表 面積和包裝密度等參數(shù)。在這里之所以采用 Voronoi 圖進(jìn)行計(jì)算，而不是把原子看成球體來 計(jì)算，是因?yàn)槿藗儾槐仃P(guān)心蛋白質(zhì)內(nèi)部的原子類型和位置。 在此領(lǐng)域， 在一個(gè)分子中原子之 間的距離比較近，如果不區(qū)分原子的大小而一概以原子的中心為

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

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