一、Voronoi Noise

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

??Voronoi圖作一種空間劃分算法，由于其特性，在很多領域都有應用，例如用來規劃電信信號塔選址以達到更好的覆蓋和經濟性；用來規劃航線達到充分利用空間但又防范避免空中撞擊風險；用來規劃路線達到避開障礙物的目的。另外其在地理學、氣象學、結晶學、航天、核物理學、機器人等領域具有廣泛的應用。

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

二、Delaunay Triangulation

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

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

1、在Delaunay三角形網中任一三角形的外接圓范圍內不會有其它點存在并與其通視，即空圓特性；
2、在構網時，總是選擇最鄰近的點形成三角形并且不與約束線段相交；
3、形成的三角形網總是具有最優的形狀特征，任意兩個相鄰三角形形成的凸四邊形的對角線如果可以互換的話，那么兩個三角形6個內角中最小的角度不會變大；
4、不論從區域何處開始構網，最終都將得到一致的結果，即構網具有唯一性。

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

三、算法步驟

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

１、正方形平面區域中有若干個特征點

２、基于特征點進行德勞內三角剖分

３、求取德勞內三角形處接圓圓心（藍色點）

４、連接相鄰外心（邊界處則是發射一條射線）

５、得到Voronoi圖

四、算法實現

??根據第三小節中的算法步驟，我們第一步生成了若干特征點:

??第二步進行了德勞內三角剖分：

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


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

五、代碼下載

??在算法實現中，Ｃ#代碼參考了參考文獻１的實現，Cg代碼參考了參考文獻７的實現。

??１、VS2015平臺用C#實現的2D_VoronoiNoise　Voronoi noise

??２、Unity2017.1.1f1平臺用Cg實現的２D,3D　Voronoise　　Voronoise

參考文獻

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

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。