沃羅諾伊圖（Voronoi Diagram，也稱作Dirichlet tessellation，狄利克雷鑲嵌）是怎樣的？

01-22

最好有圖說明。

http://mathworld.wolfram.com/VoronoiDiagram.html

簡單的說，當看到空間中的一系列給定的點，例如x, y1, y2, y3,...，我們希望為每個點，例如點x，劃定一個包圍這個點的區域，例如區域Cx，這一包含了點x的區域 Cx 我們稱為Voronoi Cell。對於任意一個位於區域 Cx 內的點，例如 Px，我們總希望它距離點x的距離小於離其他所有的給定的點，例如 y1, y2, y3,... 的距離。

在實踐上，我們可以連接每個點和它近鄰的一些點，用一條又一條的線段連接它們，對於這條線段，我們可以做它的垂直平分線（如果是三維情況，則是垂直平分面），這些垂直平分線（垂直平分面）將包圍起一塊區域，這樣的一個區域即為一個一個才Voronoi Cell。當然這一概念還可以進行一些推廣，如果我們定義的距離不是歐式距離，那麼相應的Voronoi Cell也有各種形態上的變化。

PS：這裡的Cell，在物理學家眼中的cell就是晶胞，生物學家眼中的cell是細胞，也有的人喜歡把cell理解成監獄的牢房，不管怎樣，這也是夠形象的了。

沃羅諾伊圖（Voronoi diagram）又叫狄利克雷鑲嵌（Dirichlet tessellation）或者泰森多邊形（Thiessen polygon）。沃羅諾伊圖解決的問題實際上就是基於一組特定點將平面分割成不同區域，而每一區域又僅包含唯一的特定點，並且該區域內任意位置到該特定點的距離比到其它的特定點都要更近。

由於其獨特的幾何性質，沃羅諾伊圖
已經被應用於神經科學、氣象學、信息科學等諸多領域
關於沃羅諾伊圖的正式定義、性質和應用大家可以移步維基百科或者百度百科：

Voronoi diagram

泰森多邊形_百度百科

一些相關的書籍介紹的更加詳細：

Okabe, A., Boots, B., Sugihara, K.,
Chiu, S. N. (2009). Spatial tessellations: concepts and applications of Voronoi
diagrams.

很多軟體如matlab等都內嵌了平面沃羅諾伊圖的繪製演算法。本人只就平面沃羅諾伊圖的一般繪製思想，簡要圖示介紹其繪製的基本過程：

1.
假設有限的正方形平面區域中有若干個特定點（橙色點）。

2.
首先基於特定點集進行德勞內三角剖分(Delaunay triangulation)。德勞內三角剖分是沃羅諾伊圖的對偶圖，其介紹可以看看Delaunay triangulation。

這一過程是繪製沃羅諾伊圖的核心，也是整個繪圖過程計算量的關鍵。

3.
每一個特定點會與其它若干個特定點組成多個德勞內三角形，而我們需要的是這些三角形的外心（藍色點）。根據外心的性質，其到三角形的三點的距離相等，也是我們需要的的頂點。

4.
因為是有限正方形區域，所以我們用邊界直接截取得到邊界交點。同時我們將邊界交點和外心（黃色點）分別關聯到對應的特定點。

5.
某一特定點的關聯點順時針或者逆時針相連就得到沃羅諾伊小元胞，而將所有特定的關聯點分別相連就得到沃羅諾伊圖。

6.
沃羅諾伊圖。

7.
根據各個元胞的面積抹上顏色。

說道沃洛諾伊圖、泰森多邊形，前面的大神們已經講得很詳細了。我來弄一點奇技淫巧：

MATLAB有個函數voronoi就是畫這個圖的；

這個函數功能有限，MATLAB有個工具箱mpt toolbox，裡面專門有一個更為複雜的voronoi函數。（可以去官網下載這個工具箱）

前不久diy改造了一下MATLAB里原始的voronoi函數，給了邊界色屬性，現在來展(zhuang)示(bi)一下：

凸多邊形邊界：

凹多邊形邊界

帶孔邊界

編了一個GUI，安利一下。

我是勤勞的搬運工——[蜻蜓翅膀與沃羅諾伊圖]

「動態圖http://s10.sinaimg.cn/mw690/001mPhDAzy6RnRLK4iJb9690」
沃羅諾伊圖（Voronoi Diagram，也稱作Dirichlet tessellation，狄利克雷鑲嵌）是由俄國數學家Georgy Fedoseevich Voronoi建立的空間分割演算法。靈感來源於笛卡爾用凸域分割空間的思想。在幾何，晶體學建築學，地理學，氣象學，信息系統等許多領域有廣泛的應用。

用 displaystyle{X} 表示一個距離函數為 d 的空間（一個非空集合）。令 displaystyle{K} 為一個指數集合，(P_k)_{k in K}為空間displaystyle{X}的一個非空子集的有序元組。對應於displaystyle{P_k}的displaystyle{R_k},稱沃羅諾伊原胞，或稱沃羅諾伊區域，是空間displaystyle{X}中所有到displaystyle{P_k}的距離不大於到其他位置displaystyle{P_j}（j≠k）的點集。或者說，如果定義d(x,A)=inf{d(x,a) ,|, ain A}為點x和子集A的距離，則

R_k = {x in X,, | ,,d(x,P_k) leq d(x, P_j),, ext{for all},, j
eq k}。

沃羅諾伊圖即原胞(R_k)_{k in K} 的元組。理論上有些位點能夠交叉甚至重合，但事實上它們往往被設定為不相交的。另外，定義過程中允許位點數目無限（這在幾何數論和結晶學有著重要應用），然而通常情況下，只考慮有限位點數。

蜻蜓翅膀上那網狀的細脈有種精緻的美感，而這種美感裡面真的隱藏著巧妙的數學機制，那就是被稱作沃洛諾伊圖的幾何構造。

沃洛諾伊圖（Voronoi Diagram）解決了這樣一個問題：如何根據已知點劃分平面，使得格子與點一一對應，並使平面上任取一點都與最近的已知點圍在一起。做法也很簡單，把這些點連接成三角形網路，然後作每一條邊的中垂線，這些中垂線形成的劃分就是所求。

至於蜻蜓的翅膀，脈裡面是血管和神經，生長中越靠近脈的部分伸展越快，恰好就是沃洛伊圖的意義，抻拉中自然就長成了這樣。

對於某些特定情況，如有限維度的歐幾里得空間，每一位點對應於一個點。這些點是有限且各異的，則沃羅諾伊原胞表現為凸多胞形，由它們的頂點、邊、二維面等的組合方式加以描述。有時引入的組合結構被稱為沃羅諾伊圖。然而，沃羅諾伊原胞不一定是凸形，甚至不一定是連通的

繪製方法：在平面上，繪製沃羅諾伊圖的過程，只要將胞點連起來構成許多三角形，利用中垂線找外心，再將所有外心相連即可。

用什麼程序或者軟體生成能夠導入到ansys或者abaqus

中垂線，凸多邊形。666

那麼請問三維情況下的這種圖形如何求解呢？國內外有沒有一些c++的代碼呢？謝謝

謝謝

沃羅諾伊圖（Voronoi Diagram，也稱作Dirichlet tessellation，狄利克雷鑲嵌 ）是怎樣的？

沃羅諾伊圖（Voronoi Diagram，也稱作Dirichlet tessellation，狄利克雷鑲嵌）是怎樣的？