Voronoi圖

喺數學當中**，Voronoi圖**（，，）係幫一幅平面分區成啲區域、各自屬最接近自身嘅一組畀定對象嘅。喺最簡單嘅情況下，呢啲對象衹係平面當中啲有限粒點（又喊做種（seeds）、位點（sites）或者生成點（generators））。對於每粒種，都有一個相應嘅區域，叫做**Voronoi胞**，由平面所有啲點（譬如，啲像素點）組成，啲近粒種多過其他種嘅。一組點嘅Voronoi圖對偶（dual）於佢哋個Delaunay三角剖分。

Voronoi圖得名於，亦都喊做**Voronoi鑲嵌**、**Voronoi分解**、**Voronoi分區**或者**Dirichlet鑲嵌**（得名於）。Voronoi胞亦都喊做**Thiessen多邊形**。Voronoi圖喺好多領域都有實際同理論應用，主要係喺科學同技術領域，亦都有喺視覺藝術領域。

## 最簡單嘅情況
喺最簡單嘅情況下，似第一張圖片所示，畀有喺歐幾里得平面入便一組有限嘅點{*p*1,...,*p**n*}。喺呢種情況下，每粒位點*p**k*衹係一粒點，而且佢對應嘅Voronoi胞*R**k*由歐幾里得平面當中嘅每粒點組成，呢啲點戥*p**k*嘅距離細過或者等於佢戥任何其他*p**k*距離。每個噉嘅胞都係從半空間嘅交集獲得嘅，因此佢係一個凸多面體。Voronoii圖啲線段係指平面當中戥最近嘅兩粒位點等距嘅所有點。Voronoi頂點（節點）係戥三個（或者多啲）位點等距嘅點。

## 正式定義
令 X 係一個度量空間，有距離函數d.令K係一組索引（indices），令(P_k)_{k \in K}係喺空間 X裏便嘅非空子集（位點）嘅元組（有序集合）。Voronoi胞或者Voronoi區域， R_k,戥位點P_k相關聯嘅，係X所有點嘅集合、啲離 P_k唔遠過佢哋到其他位點P_j嘅，其中j係任何唔同於k嘅索引。即係話，若果 d(x,\, A) = \inf\{d(x,\, a) \mid a \in A\}表示點x同子集A之間嘅距離，即有 R_k = \{x \in X \mid d(x, P_k) \leq d(x, P_j)\; \text{for all}\; j \neq k\}Voronoi圖衹係啲胞嘅元組(R_k)_{k \in K} 。原則上，一啲位點可以相交甚至重合（下低嘅應用場合有描述到一啲代表商店嘅位點），但通常假設佢哋係唔相交嘅。另外，定義當中允許無限多個位點（呢種設置喺幾何數論同晶體學當中有應用），但同樣喺好多情況下僅衹考慮有限多個位點。

喺空間係有限維歐幾里得空間嘅特殊情況下，每粒位點都係一粒點，總共有有限咁多粒點而且啲點互相之間都唔同，係噉啲Voronoi胞係凸多面體，佢哋嘅頂點、邊、二維面等可以用組合方式表示。有時，誘導組合結構（induced combinatorial structure ）都着喊做Voronoi圖。之不過，普遍情況下，啲Voronoi胞可能唔係凸嘅，甚至可能唔係連通（connected）嘅。

喺通常嘅歐幾里得空間當中，可以用通常嘅術語寫過個形式定義。每個Voronoi多邊形R_k戥生成點P_k相關聯.令X係歐幾里得空間當中所有點嘅集合。令P_1成為生成佢Voronoi區域R_1嘅點,P_2產生R_2，同P_3產生R_3等等。然之後似Tran*等人*表達嘅，「歐幾里得平面上嘅Voronoi圖入邊，Voronoi多邊形裏便嘅所有位置都靠近個多邊形嘅生成點，近過任何其他生成點」。

## 例證
作為一個簡單嘅例，試惗一座城市裏便嘅一組商店，假設要估計畀定商店嘅顧客數量。喺所有啲其他條件（價格、產品、服務質量等）都相同嘅情況下，可以合理噉假設客戶僅衹根據距離嚟考慮選擇佢哋喜歡嘅商店：佢哋會去離佢哋最近嘅商店。喺呢種情況下，Voronoi胞R_k針對畀定商店P_k嘅可以攞嚟粗略估計前往間商店嘅潛在客戶數量（以城市嘅一粒點為模型）。

對於大多數城市，可以使用熟悉嘅歐幾里德距離嚟度啲點之間嘅距離：

: \ell_2 = d\left[\left(a_1, a_2\right), \left(b_1, b_2\right)\right] = \sqrt{\left(a_1 - b_1\right)^2 + \left(a_2 - b_2\right)^2}

或者曼哈頓距離：

: d\left[\left(a_1, a_2\right), \left(b_1, b_2\right)\right] = \left|a_1 - b_1\right| + \left|a_2 - b_2\right|.

對於唔同嘅距離度量，相應嘅Voronoi圖睇起身都唔同。

## 特性

* Voronoi圖嘅對偶圖（喺帶有點位點嘅歐幾里得空間嘅情況下）對應於同一組點嘅Delaunay三角剖分。
* 最近嘅一對點對應於Voronoi圖當中嘅兩個相鄰胞。
* 假設設置係歐幾里得平面，並畀出一組唔同嘅點。係噉當且僅衹當佢哋嘅Voronoi胞共享無限長嘅邊時，兩粒點喺凸殼上相鄰。
* 若果空間係賦範空間而且獲得唨到每粒位點嘅距離（例如，當位點係緊集或者封閉球時），則每個Voronoi胞可以表示為從位點發出嘅線段嘅聯合。如圖所示，當未達到距離時，此屬性唔一定成立。
* 喺相對一般嘅條件下（空間可能係無限維均勻凸空間，可以有無限多個一般形式嘅位點，等等。)Voronoi胞具有一定嘅穩定性：位點形狀嘅微細變化，例如由某啲平移或者扭曲引起嘅變化，會產生Voronoi胞形狀嘅微細變化。呢就係Voronoi圖嘅幾何穩定性。如圖所示，即使空間係二維嘅（但非均勻凸嘅，特別係非歐幾里得嘅）而且位置係點，呢個屬性通常亦都唔成立。

## 歷史戥研究
Voronoi圖嘅非正式使用可以追溯到1644年嘅笛卡兒。Peter Gustav Lejeune Dirichlet於1850年喺佢對二次型（quadratic forms）嘅研究當中用咗二維同三維嘅Voronoi圖。英國醫生John Snow喺1854年使用類似Voronoi嘅圖表嚟講明喺Broad Street霍亂爆發當中死亡嘅大多數人係點樣住喺啲埞係離受感染嘅Broad Street水泵近過任何其他水泵嘅。

Voronoi圖以Georgy Feodosievych Voronoy嘅名字命名，佢喺1908年定義並研究咗一般嘅*n*維情況。 喺地球物理學同氣象學當中用嘅Voronoi圖，即係Thiessen多邊形，攞嚟分析空間分佈數據（例如降雨量測量）嘅，得名來自美國氣象學家Alfred H. Thiessen。呢個概念嘅其他等效名稱（對應啲特別重要嘅case）有：Voronoi多面體、Voronoi多邊形、影響域、Voronoi分解、Voronoi鑲嵌、Dirichlet鑲嵌。

## 例

二維或者三維點嘅規則格（lattice）嘅Voronoi鑲嵌產生有好多熟悉嘅鑲嵌。

* 二維晶格提供唔規則嘅蜂窩狀鑲嵌，具有點對稱嘅相等六邊形；喺規則三角形格子嘅情況下，佢係規則嘅；喺矩形格嘅情況下，六邊形減少為行同列嘅矩形；正方形格子畀出正方形嘅規則鑲嵌；請注意，矩形同正方形亦都可以由其他格子生成（例如，由向量(1,0)同(1/2,1/2)定義嘅格子畀出正方形）。
* 一個簡單立方晶格畀出立方蜂窩。
* 六邊形密堆積晶格提供梯形菱形十二面體嘅空間鑲嵌。
* 面心立方晶格提供菱形十二面體嘅空間鑲嵌。
* 體心立方晶格畀出切角八面體嘅空間鑲嵌。
* 平行平面，具有彼此中心對齊嘅規則三角形晶格嘅，形成六邊形棱柱蜂窩。
* 某啲以體心為中心嘅四邊形晶格，畀出菱形六角化十二面體嘅空間鑲嵌。

對於點集(*x*,&nbsp;*y*)，*x*喺離散集合*X*當中，*y*喺離散集合*Y*當中，得到啲矩形塊，啲點唔一定喺佢哋嘅中心嘅。

## 高階Voronoi圖
正常嘅Voronoi胞着定義成最接近*S*當中單粒點嘅點集，但「*n*階Voronoi胞」着定義成個點集、以*S*裏頭特定*n*粒點作為啲*n*粒最近鄰點嘅。高階Voronoi圖亦都細分唨空間。

高階Voronoi圖可以攞遞歸來生成。要生成集合&nbsp;*S*當中嘅第*n*階Voronoi圖，可以從第(*n*&nbsp;-&nbsp;1)階圖落手並替換啲由*X*&nbsp;=&nbsp;{*x*1,&nbsp;*x*2,&nbsp;...,&nbsp;*x**n*−1}生成嘅每個胞，替換成喺集合&nbsp;*S&nbsp;-&nbsp;X*上生成嘅Voronoi圖。

### 至遠點Voronoi圖
對於一組*n*粒點，第(*n*&nbsp;-&nbsp;1)階Voronoi圖喊做至遠點（farthest-point）Voronoi圖。

對於畀定嘅一組點*S*&nbsp;=&nbsp;{*p*1，&nbsp;*p*2，&nbsp;...,&nbsp;*p**n*}，至遠點Voronoi圖將平面劃分為多個胞，喺其中*P*嘅同樣點即係粒至遠點。喺至遠點Voronoi圖當中嘅一粒點*P*要有一個胞嘅話，若且唯若佢係*P*嘅凸殼（convex hull）嘅一個頂點。令*H*&nbsp;=&nbsp;{*h*1,&nbsp;*h*2，&nbsp;...,&nbsp;*h**k*}係*P*嘅凸殼；係噉至遠點Voronoi圖係將平面細分為*k*個胞，每個胞對應於*H*當中嘅每粒點，啲點具有屬性係：對於一粒點*q*，每個*p**j*&nbsp;∈&nbsp;*S*而且唔同於*h<sub>i</sub>*（即*h<sub>i</sub>* ≠ *p<sub>j</sub>*），若且唯若d(*q*,*h**i*)>d(*q*,*p**j*)，即話嗰粒點*q*處於個對應位點*h**i*嘅胞入便；其中d(*p, q*)係*p*戥&nbsp;*q*兩粒點嘅歐幾里得距離。

至遠點Voronoi圖當中啲胞嘅邊界具有拓撲樹嘅結構，以無限射線為佢啲葉。每蔸有限樹同構（isomorphic）於嗰蔸噉樣由至遠點Voronoi圖形成嘅樹。 

## 普遍化同變體
正如定義所暗示嘅噉，可以為除歐幾里得以外嘅度量定義Voronoi胞，例如馬哈拉諾比斯距離或者曼哈頓距離。之不過，喺呢啲情況下，Voronoi胞嘅邊界可能複雜過歐幾里得距離嘅情況，因為即使喺二維情況下，兩點嘅等距軌跡亦都可能冇辦法成為餘維1（codimension 1）嘅子空間。

加權Voronoi圖係噉嘅一種圖，佢當中定義啲Voronoi胞嘅一對點嘅函數係一種模改過嘅距離函數，通過乘或者加啲權重、啲分配畀生成器點嘅嚟改到出嚟。戥使用度量（metric）嘅距離定義嘅Voronoi胞格情況相反，喺呢種情況下，一啲Voronoi胞格可能係空嘅。冪圖係一種使用圓冪距離（power distance）從一組圓定義出來嘅Voronoi圖；佢亦都可以着認為係一個加權嘅Voronoi圖，佢當中根據每個圓嘅半徑定義嘅權重着添加到距圓心嘅平方歐幾里德距離上。

喺d維空間n粒點嘅Voronoi圖可以有O(n^{\lceil d/2 \rceil})笪頂點，需要到戥存儲佢嘅顯式描述所需嘅內存量相同嘅界限。因此，Voronoi圖對於中等或者高維通常唔可行得。節省多啲空間嘅替代方法係使用近似嘅Voronoi圖。

Voronoi圖仲戥其他幾何結構有關，例如中軸（已應用喺圖像分柵、OCR同其他計算應用當中）、直骨架（straight skeleton）與及區域圖（zone diagram）。除唨點之外，此類圖仲使用線同多邊形作為種。通過使用連接到種上最近點嘅線段嚟擴充圖表，可以獲得環境嘅平面細分。呢種結構可以用作導航網格，用於穿過好大空間進行搵路。導航網格已得到推廣以支持3D多層環境，例如機場或者多層建築。

## 應用

### 人文學科

* 喺古典考古學，特別係藝術史當中，分析雕像頭部嘅對稱性以確定着切斷嘅頭部可能屬於嘅雕像類型。使用Vornoi胞嘅一個例子係Sabouroff頭部嘅識別，佢使用唨高分辨率多邊形網格。

### 自然科學

* 喺生物學當中，Voronoi圖用於模擬好多唔同嘅生物結構，包括胞同骨骼微結構。事實上，Voronoi鑲嵌作為一種幾何工具嚟理解驅動生物組織組織嘅物理約束。
* 喺水文學當中，Voronoi圖用於根據一系列點測量計算一個區域嘅降雨量。喺呢種用法當中，佢哋通常着喊做Thiessen多邊形。
* 喺生態學當中，Voronoi圖用於研究森林同森林冠層嘅生長模式，亦都可能有助於開發森林火災嘅預測模型。
* 喺計算化學當中，配體結合位點着轉化為用於機器學習應用嘅Voronoi圖（例如，對蛋白質當中嘅結合口袋進行分類）。喺其他應用當中，由分子當中原子核嘅位置定義嘅Voronoi胞用於計算原子電荷。呢個係使用Voronoi變形密度方法完成嘅。
* 喺天體物理學當中，Voronoi圖用於喺圖像上生成自適應平滑區域，喺每個區域上添加信號通量。呢啲程序嘅主要目標係喺所有圖像上保持相對恆定嘅信噪比。
* 喺計算流體動力學當中，一組點嘅Voronoi細分可用於定義有限體積方法當中使用嘅計算域，例如喺移動網格宇宙學代碼AREPO當中。
* 喺運算物理學當中，Voronoi圖用於喺高能量密度物理學當中使用陰影圖同質子射線照相計算物體嘅輪廓。

### 健康

* 喺醫學診斷當中，基於Voronoi圖嘅肌肉組織模型可用於檢測神經肌肉疾病。
* 喺傳染病學當中，Voronoi圖可用於關聯流行病當中嘅感染源。約翰·斯諾(JohnSnow)實施唨Voronoi圖嘅早期應用之一，以研究1854年喺英格蘭蘇荷區爆發嘅寬街霍亂。他展示唨倫敦市中心地圖上居民一直喺使用特定水泵嘅居民區戥因疫情而死亡人數最多嘅地區之間嘅相關性。

### 工程

* 喺聚合物物理學當中，Voronoi圖可用於表示聚合物嘅自由體積。
* 喺材料科學當中，金屬合金當中嘅多晶微觀結構通常使用Voronoi鑲嵌嚟表示。喺島嶼增長當中，Voronoi圖用於估計單個島嶼嘅增長率。喺固態物理學當中，Wigner-Seitz胞係固體嘅Voronoi鑲嵌，布里淵區係具有空間群對稱性嘅晶體倒數（波數）空間嘅Voronoi鑲嵌。
* 喺航空領域，隨著飛機執行佢飛行計劃，Voronoi圖疊加喺海洋繪圖圖上以識別最近嘅飛行當中改道機場（參見ETOPS）。
* 喺建築學，Voronoi圖案係重新開發黃金海岸藝術中心嘅獲獎作品嘅基礎。
* 喺城市規劃當中，Voronoi圖可用於評估貨運裝載區系統。
* 喺礦業當中，Voronoi多邊形用於估計有價值嘅材料、礦物或者其他資源嘅儲量。勘探鑽孔用作Voronoi多邊形當中嘅一組點。
* 喺表面計量學當中，Voronoi曲面細分可用於表面粗糙度建模。
* 喺機械人學當中，多機器人系統嘅一啲控制策略係基於環境嘅Voronoi分區。

### 幾何學

* 可以喺Voronoi圖嘅頂部構建點位置數據結構，以回答最近鄰查詢，佢當中人們想要找到最接近畀定查詢點嘅對象。最近鄰查詢有很多應用。例如，人們可能想喺數據庫當中找到最近嘅醫院或者最相似嘅對象。一個大型應用係矢量量化，通常用於數據壓縮。
* 喺幾何學當中，Voronoi圖可用於喺一組點同封閉多邊形當中找到最大嘅空圓；例如，喺某個城市，盡可能遠離現有嘅所有超市，建造一個新嘅超市。
* Voronoi圖戥至遠點Voronoi圖一起用於計算一組點嘅圓度嘅有效演算法。Voronoi方法仲用於評估圓度/圓度，同時評估嚟自坐標測量機嘅數據集。

### 訊息學
* 喺網絡領域，Voronoi圖可以攞嚟推導無線網絡嘅容量。
* 喺電腦圖形學領域，Voronoi圖用於計算3D破碎/破裂幾何圖案。佢仲用於程序生成有機或者岩漿外觀嘅紋理。
* 喺自主機器人導航當中，Voronoi圖用嚟尋找清楚嘅路線。若果啲點係障礙物，係噉圖嘅邊線即係所需嘅路線，距離啲障礙物最遠嘅（理論上嚟避免到啲碰撞）。
* 喺機械學習當中，Voronoi圖用於進行1-NN分類。
* 喺用家介面開發當中，Voronoi模式可用於計算畀位點嘅最佳懸停狀態。

### 日常生活
* 喺墨爾本，公立學校嘅學生總係有資格就讀啲小學或者高中距離佢哋居住地最近嘅，直線距離衡量。因此，啲學區地圖係Voronoi圖。

* 烏克蘭糕點廚師DinaraKasko使用Voronoi圖嘅數學原理，用3D打印機製作矽膠模具嚟塑造佢啲原創蛋糕。

## 演算法
已知有幾種有效嘅演算法可用於直接（作為圖本身）或者通過從Delaunay三角剖分開始然之後獲得佢對偶嚟間接構造Voronoi圖。直接演算法包括Fortune演算法，一種O(*n*log(*n*))演算法，用於從平面當中嘅一組點生成Voronoi圖。Bowyer-Watson演算法係一種O(*n*log(*n*))到O(*n*2)演算法，用於生成任意維數嘅Delaunay三角剖分，可用於Voronoi圖嘅間接演算法。JumpFlooding演算法可以喺恆定時間內生成近似嘅Voronoi圖，適用於商品圖形硬件。

Lloyd演算法及佢通過Linde-Buzo-Gray演算法（又名k均值聚類）嘅泛化，使用Voronoi圖嘅構建作為子程序。呢啲方法喺為一組種點構建Voronoi圖嘅步驟同將種點移動到佢胞內中心多啲嘅新位置嘅步驟之間交替。呢啲方法可用於任意維度嘅空間，以迭代收斂於Voronoi圖嘅特殊形式，喊做CentroidalVoronoitessellation，佢當中位點已移動到亦都係佢胞幾何中心嘅點。

## 睇埋
*Delaunay triangulation
*Map segmentation
*Natural element method
*Natural neighbor interpolation
*Nearest-neighbor interpolation
*Power diagram
*Voronoi pole
## 內註

## 考

*
*
* *Includes a description of Fortune's algorithm.*
*
*
*
*
*
*
*
*

## 出面網頁
* 帶有源代碼嘅實時交互式Voronoi同Delaunay圖
* 各種指標嘅演示
* Voronoi圖上嘅Mathworld
* Voronoi圖：從考古學到動物學嘅應用
* CGAL當中嘅Voronoi圖，計算幾何演算法庫
* 關於質心Voronoi鑲嵌嘅更多討論同圖片庫
* VoronoiDiagramsbyEdPegg,Jr.、JeffBryant同TheodoreGray，WolframDemonstrationsProject。
* 球體上嘅Voronoi圖，3d等
* 使用Mathematica繪製Voronoi圖
* Voronoi鑲嵌-使用D3.js進行交互式Voronoi鑲嵌
* 交互式Voronoi圖同自然鄰域插值可視化(WebGL)

### 軟件
Voronoi圖喺顯示結果之前需要一個計算步驟。因此，一個有效嘅工具將實時處理計算以向用戶顯示直接結果。存喺好多商業同免費應用程序。一種特別實用嘅工具係基於網絡嘅工具。基於Web嘅工具易啲訪問同參考。此外，SVG係網絡本機支持嘅格式，同時允許高效（GPU加速）渲染，而且係多種CAD工具（例如AutodeskFusion360）。

* Voronator係一個免費嘅（基於廣告嘅）工具，作用於3D對象網格以喺佢表面應用Voronoi。即管呢個工具作用於3d，但voronoi處理基於佢2d表面。
* rhillvoronoi係一個用於2dvoronoi生成嘅開源JavaScript庫。
* stgvoronoi係一個github項目，具有簡單嘅Web應用程序，但喺移動鼠標時提供對voronoi胞嘅交互式查睇。佢仲提供埋SVG導出。
* websvgvoronoi係一個響應式web應用程序，用於喺SVG當中進行voronoi編輯同導出。佢仲允許埋導出同導入種坐標。佢係基於2d嘅，佢戥前面提到嘅工具嘅唔同之處喺於提供唨一個胞收回操作，呢個操作唔係基於比例，而係基於邊緣平移。若果一條邊俾佢相鄰邊消耗，則可以將佢移除。
* A.Beutelvoronoi正喺使用WebGL，除唨靜態查睇之外，仲提供埋voronoi胞嘅動畫運動。

即管voronoi係一個非常古老嘅概念，但當前可用嘅工具確實缺乏可以為呢啲程序增加價值嘅多種數學函數。示例可能係使用戥歐幾里得唔同嘅成本距離，主要係3DVoronoi演算法。雖然唔係軟件工具本身，但第一個參考解釋唨3DVoronoi嘅概念，第二個係3DVoronoi庫。

* 3DVoronoi圖同當中軸
* Voro++用於3dvoronoi計算嘅C++庫