一、Voronoi Noise

??沃羅諾伊圖（Voronoi Diagram，也稱作Dirichlet tessellation，狄利克雷鑲嵌）是由俄國(guó)數(shù)學(xué)家Georgy Fedoseevich Voronoi建立的空間分割算法，其空間劃分思想來源于笛卡爾用凸域分割空間理論，也就是說，Voronoi圖實(shí)際是一種空間劃分方法，這種劃分方法解決了這樣一個(gè)問題：如何根據(jù)已知點(diǎn)劃分空間，使得晶胞與點(diǎn)一一對(duì)應(yīng)，并使晶胞內(nèi)任取一點(diǎn)都與最近的已知點(diǎn)圍在一起，或者換一種說法就是沃羅諾伊圖基于一組特征點(diǎn)將空間分割成不同區(qū)域，而每一區(qū)域又僅包含唯一的特征點(diǎn)，并且該區(qū)域內(nèi)任意位置到該特征點(diǎn)的距離比到其它的特征點(diǎn)都要更近。所以Voronoi圖有以下特性（以二維平面為例）：
（1）每個(gè)V多邊形內(nèi)有一個(gè)特征點(diǎn)；
（2）每個(gè)V多邊形內(nèi)點(diǎn)到該特征點(diǎn)距離短于到其它特征點(diǎn)的距離；
（3）多邊形邊界上的點(diǎn)到生成此邊界的特征點(diǎn)距離相等；
（4）鄰接圖形的Voronoi多邊形界線以原鄰接界線作為子集。

??Voronoi圖作一種空間劃分算法，由于其特性，在很多領(lǐng)域都有應(yīng)用，例如用來規(guī)劃電信信號(hào)塔選址以達(dá)到更好的覆蓋和經(jīng)濟(jì)性；用來規(guī)劃航線達(dá)到充分利用空間但又防范避免空中撞擊風(fēng)險(xiǎn)；用來規(guī)劃路線達(dá)到避開障礙物的目的。另外其在地理學(xué)、氣象學(xué)、結(jié)晶學(xué)、航天、核物理學(xué)、機(jī)器人等領(lǐng)域具有廣泛的應(yīng)用。

??對(duì)圖形學(xué)來講，Voronoi圖的空間劃分特性可以用來模擬物體破碎效果：
　　
??Voronoi圖能形成獨(dú)特的圖案紋理，也常用在程序紋理生成中。

二、Delaunay Triangulation

??Voronoi圖定義簡(jiǎn)單，我們甚至可以使用手工做鉛垂線的方式來作出給定特征點(diǎn)的Voronoi圖，但理論上解決這個(gè)問題卻比較難，直到Voronoi圖提出來后25年，Delaunay才提出了解決該剖分完整而實(shí)用的方法，這就是著名的德勞內(nèi)三角剖分（Delaunay Triangulation）。

??Delaunay三角剖分具有以下特性：

1、在Delaunay三角形網(wǎng)中任一三角形的外接圓范圍內(nèi)不會(huì)有其它點(diǎn)存在并與其通視，即空?qǐng)A特性；
2、在構(gòu)網(wǎng)時(shí)，總是選擇最鄰近的點(diǎn)形成三角形并且不與約束線段相交；
3、形成的三角形網(wǎng)總是具有最優(yōu)的形狀特征，任意兩個(gè)相鄰三角形形成的凸四邊形的對(duì)角線如果可以互換的話，那么兩個(gè)三角形6個(gè)內(nèi)角中最小的角度不會(huì)變大；
4、不論從區(qū)域何處開始構(gòu)網(wǎng)，最終都將得到一致的結(jié)果，即構(gòu)網(wǎng)具有唯一性。

??Delaunay三角剖分也有很多算法，網(wǎng)上相關(guān)資料很多，不再詳述，本文參考文獻(xiàn)部分也列出了部分Delaunay三角剖分方面的文章。
??Delaunay三角剖分是Voronoi圖的對(duì)偶圖，因此得到Delaunay三角剖分后就可以得到Voronoi圖。

三、算法步驟

??通過上述論述，我們將生成Voronoi圖的算法概要步驟描述如下：

１、正方形平面區(qū)域中有若干個(gè)特征點(diǎn)

２、基于特征點(diǎn)進(jìn)行德勞內(nèi)三角剖分

３、求取德勞內(nèi)三角形處接圓圓心（藍(lán)色點(diǎn)）

４、連接相鄰?fù)庑?#xff08;邊界處則是發(fā)射一條射線）

５、得到Voronoi圖

四、算法實(shí)現(xiàn)

??根據(jù)第三小節(jié)中的算法步驟，我們第一步生成了若干特征點(diǎn):

??第二步進(jìn)行了德勞內(nèi)三角剖分：

??第三步，求取德勞內(nèi)三角形外心，并連接外心得到Voronoi圖：


??Voronoi是一種空間劃分算法，因其劃分后特殊的圖案，我們也可以將其作為噪聲來使用，其實(shí)上，Voronoi算法是可以生成噪聲圖形的，下圖是我們使用cg實(shí)現(xiàn)的voronoi噪聲圖形。

五、代碼下載

??在算法實(shí)現(xiàn)中，Ｃ#代碼參考了參考文獻(xiàn)１的實(shí)現(xiàn)，Cg代碼參考了參考文獻(xiàn)７的實(shí)現(xiàn)。

??１、VS2015平臺(tái)用C#實(shí)現(xiàn)的2D_VoronoiNoise　Voronoi noise

??２、Unity2017.1.1f1平臺(tái)用Cg實(shí)現(xiàn)的２D,3D　Voronoise　　Voronoise

參考文獻(xiàn)

１、維諾圖（Voronoi Diagram）分析與實(shí)現(xiàn)　維諾圖（Voronoi Diagram）分析與實(shí)現(xiàn)
２、三角剖分詳解　三角剖分詳解
３、Delaunay三角剖分算法　Delaunay三角剖分算法
４、三角剖分算法(delaunay)　三角剖分算法(delaunay)
５、To Voronoi and Beyond　To Voronoi and Beyond
6、沃羅諾伊圖　沃羅諾伊圖
7、voronoise　voronoise

總結(jié)

以上是生活随笔為你收集整理的Voronoi Noise的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。