沃羅諾伊圖

二十個點和沃羅諾伊單元格

沃羅諾伊圖（Voronoi Diagram，也稱作Dirichlet tessellation，狄利克雷鑲嵌）是由烏克蘭數學家格奧爾吉·沃羅諾伊建立的空間分割算法。靈感來源於笛卡爾用凸域分割空間的思想。在幾何、晶體學、建築學、地理學、氣象學、信息系統等許多領域有廣泛的應用。

沃洛諾伊圖的單元被稱為泰森多邊形。

建立步驟

建立泰森多邊形算法的關鍵是對離散數據點合理地連成三角網，即構建Delaunay三角網。建立泰森多邊形的步驟為：

1、離散點自動構建三角網，即構建Delaunay三角網。對離散點和形成的三角形編號，記錄每個三角形是由哪三個離散點構成的。

2、找出與每個離散點相鄰的所有三角形的編號，並記錄下來。這只要在已構建的三角網中找出具有一個相同頂點的所有三角形即可。

3、對與每個離散點相鄰的三角形按順時針或逆時針方向排序，以便下一步連接生成泰森多邊形。設離散點為o。找出以o為頂點的一個三角形，設為A；取三角形A除o以外的另一頂點，設為a，則另一個頂點也可找出，即為f；則下一個三角形必然是以of為邊的，即為三角形F；三角形F的另一頂點為e，則下一三角形是以oe為邊的；如此重複進行，直到回到oa邊。

4、計算每個三角形的外接圓圓心，並記錄之。

5、根據每個離散點的相鄰三角形，連接這些相鄰三角形的外接圓圓心，即得到泰森多邊形。對於三角網邊緣的泰森多邊形，可作垂直平分線與圖廓相交，與圖廓一起構成泰森多邊形。

定義

用$\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)\,|\,a\in A\}$為點$x$和子集$A$的距離，則

$R_{k}=\{x\in X\,\,|\,\,d(x,P_{k})\leq d(x,P_{j})\,\,{\text{for all}}\,\,j\neq k\}$。

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

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

平面繪製

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

相關條目

• 王氏磚
• 雙體模型
• 德勞內三角化
• 最近鄰插值
• Power圖

參考資料

• MathWorld的介紹 （頁面存檔備份，存於網際網路檔案館）（英文）
• 用Mathematica畫沃羅諾伊圖 （頁面存檔備份，存於網際網路檔案館）（英文）