Voronoi圖

喺數學當中，Voronoi圖（粵拼：Vaa3laa3neoi4tou4，俄文：Диаграмма Вороного，英文：Voronoi diagram）係幫一幅平面分區成啲區域、各自屬最接近自身嘅一組畀定對象嘅。喺最簡單嘅情況下，呢啲對象衹係平面當中啲有限粒點（又喊做種（seeds）、位點（sites）或者生成點（generators））。對於每粒種，都有一個相應嘅區域，叫做Voronoi胞，由平面所有啲點（譬如，啲像素點）組成，啲近粒種多過其他種嘅。一組點嘅Voronoi圖對偶（dual）於佢哋個Delaunay三角剖分。
Voronoi圖得名於Georgy Voronoy（俄文：Вороной, Георгий Феодосьевич），亦都喊做Voronoi鑲嵌、Voronoi分解、Voronoi分區或者Dirichlet鑲嵌（得名於Peter Gustav Lejeune Dirichlet（英文：Peter Gustav Lejeune Dirichlet））。Voronoi胞亦都喊做Thiessen多邊形。Voronoi圖喺好多領域都有實際同理論應用，主要係喺科學同技術領域，亦都有喺視覺藝術領域。
喺最簡單嘅情況下，似第一張圖片所示，畀有喺歐幾里得平面入便一組有限嘅點{p1,...,pn}。喺呢種情況下，每粒位點pk衹係一粒點，而且佢對應嘅Voronoi胞Rk由歐幾里得平面當中嘅每粒點組成，呢啲點戥pk嘅距離細過或者等於佢戥任何其他pk距離。每個噉嘅胞都係從半空間嘅交集獲得嘅，因此佢係一個凸多面體。Voronoii圖啲線段係指平面當中戥最近嘅兩粒位點等距嘅所有點。Voronoi頂點（節點）係戥三個（或者多啲）位點等距嘅點。
令X{\textstyle X}係一個度量空間，有距離函數d{\textstyle d}.令K{\textstyle K}係一組索引（indices），令(Pk)k∈K{\textstyle (P_{k})_{k\in K}}係喺空間X{\textstyle X}裏便嘅非空子集（位點）嘅元組（有序集合）。Voronoi胞或者Voronoi區域，Rk{\textstyle R_{k}},戥位點Pk{\textstyle P_{k}}相關聯嘅，係X{\textstyle X}所有點嘅集合、啲離Pk{\textstyle P_{k}}唔遠過佢哋到其他位點Pj{\textstyle P_{j}}嘅，其中j{\textstyle j}係任何唔同於k{\textstyle k}嘅索引。即係話，若果d(x,A)=inf{d(x,a)∣a∈A}{\textstyle d(x,\,A)=\inf\{d(x,\,a)\mid a\in A\}}表示點x{\textstyle x}同子集A{\textstyle A}之間嘅距離，即有Rk={x∈X∣d(x,Pk)≤d(x,Pj)for allj≠k}{\displaystyle R_{k}=\{x\in X\mid d(x,P_{k})\leq d(x,P_{j})\;{\text{for all}}\;j\neq k\}}Voronoi圖衹係啲胞嘅元組(Rk)k∈K{\textstyle (R_{k})_{k\in K}}。原則上，一啲位點可以相交甚至重合（下低嘅應用場合有描述到一啲代表商店嘅位點），但通常假設佢哋係唔相交嘅。另外，定義當中允許無限多個位點（呢種設置喺幾何數論同晶體學當中有應用），但同樣喺好多情況下僅衹考慮有限多個位點。
喺空間係有限維歐幾里得空間嘅特殊情況下，每粒位點都係一粒點，總共有有限咁多粒點而且啲點互相之間都唔同，係噉啲Voronoi胞係凸多面體，佢哋嘅頂點、邊、二維面等可以用組合方式表示。有時，誘導組合結構（induced combinatorial structure ）都着喊做Voronoi圖。之不過，普遍情況下，啲Voronoi胞可能唔係凸嘅，甚至可能唔係連通（connected）嘅。
喺通常嘅歐幾里得空間當中，可以用通常嘅術語寫過個形式定義。每個Voronoi多邊形Rk{\textstyle R_{k}}戥生成點Pk{\textstyle P_{k}}相關聯.令X{\textstyle X}係歐幾里得空間當中所有點嘅集合。令P1{\textstyle P_{1}}成為生成佢Voronoi區域R1{\textstyle R_{1}}嘅點,P2{\textstyle P_{2}}產生R2{\textstyle R_{2}}，同P3{\textstyle P_{3}}產生R3{\textstyle R_{3}}等等。然之後似Tran等人表達嘅，「歐幾里得平面上嘅Voronoi圖入邊，Voronoi多邊形裏便嘅所有位置都靠近個多邊形嘅生成點，近過任何其他生成點」。
作為一個簡單嘅例，試惗一座城市裏便嘅一組商店，假設要估計畀定商店嘅顧客數量。喺所有啲其他條件（價格、產品、服務質量等）都相同嘅情況下，可以合理噉假設客戶僅衹根據距離嚟考慮選擇佢哋喜歡嘅商店：佢哋會去離佢哋最近嘅商店。喺呢種情況下，Voronoi胞Rk{\displaystyle R_{k}}針對畀定商店Pk{\displaystyle P_{k}}嘅可以攞嚟粗略估計前往間商店嘅潛在客戶數量（以城市嘅一粒點為模型）。
對於大多數城市，可以使用熟悉嘅歐幾里德距離嚟度啲點之間嘅距離：
或者曼哈頓距離：
對於唔同嘅距離度量，相應嘅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鑲嵌產生有好多熟悉嘅鑲嵌。
對於點集(x,y)，x喺離散集合X當中，y喺離散集合Y當中，得到啲矩形塊，啲點唔一定喺佢哋嘅中心嘅。
正常嘅Voronoi胞着定義成最接近S當中單粒點嘅點集，但「n階Voronoi胞」着定義成個點集、以S裏頭特定n粒點作為啲n粒最近鄰點嘅。高階Voronoi圖亦都細分唨空間。
高階Voronoi圖可以攞遞歸來生成。要生成集合S當中嘅第n階Voronoi圖，可以從第(n- 1)階圖落手並替換啲由X= {x1,x2, ...,xn−1}生成嘅每個胞，替換成喺集合S - X上生成嘅Voronoi圖。
對於一組n粒點，第(n- 1)階Voronoi圖喊做至遠點（farthest-point）Voronoi圖。
對於畀定嘅一組點S= {p1，p2，...,pn}，至遠點Voronoi圖將平面劃分為多個胞，喺其中P嘅同樣點即係粒至遠點。喺至遠點Voronoi圖當中嘅一粒點P要有一個胞嘅話，若且唯若佢係P嘅凸殼（convex hull）嘅一個頂點。令H= {h1,h2，...,hk}係P嘅凸殼；係噉至遠點Voronoi圖係將平面細分為k個胞，每個胞對應於H當中嘅每粒點，啲點具有屬性係：對於一粒點q，每個pj∈S而且唔同於hi（即hi≠pj），若且唯若d(q,hi)>d(q,pj)，即話嗰粒點q處於個對應位點hi嘅胞入便；其中d(p, q)係p戥q兩粒點嘅歐幾里得距離。
至遠點Voronoi圖當中啲胞嘅邊界具有拓撲樹嘅結構，以無限射線為佢啲葉。每蔸有限樹同構（isomorphic）於嗰蔸噉樣由至遠點Voronoi圖形成嘅樹。
正如定義所暗示嘅噉，可以為除歐幾里得以外嘅度量定義Voronoi胞，例如馬哈拉諾比斯距離或者曼哈頓距離。之不過，喺呢啲情況下，Voronoi胞嘅邊界可能複雜過歐幾里得距離嘅情況，因為即使喺二維情況下，兩點嘅等距軌跡亦都可能冇辦法成為餘維1（codimension 1）嘅子空間。
加權Voronoi圖係噉嘅一種圖，佢當中定義啲Voronoi胞嘅一對點嘅函數係一種模改過嘅距離函數，通過乘或者加啲權重、啲分配畀生成器點嘅嚟改到出嚟。戥使用度量（metric）嘅距離定義嘅Voronoi胞格情況相反，喺呢種情況下，一啲Voronoi胞格可能係空嘅。冪圖係一種使用圓冪距離（power distance）從一組圓定義出來嘅Voronoi圖；佢亦都可以着認為係一個加權嘅Voronoi圖，佢當中根據每個圓嘅半徑定義嘅權重着添加到距圓心嘅平方歐幾里德距離上。
喺d{\displaystyle d}維空間n{\displaystyle n}粒點嘅Voronoi圖可以有O(n⌈d/2⌉){\textstyle O(n^{\lceil d/2\rceil })}笪頂點，需要到戥存儲佢嘅顯式描述所需嘅內存量相同嘅界限。因此，Voronoi圖對於中等或者高維通常唔可行得。節省多啲空間嘅替代方法係使用近似嘅Voronoi圖。
Voronoi圖仲戥其他幾何結構有關，例如中軸（已應用喺圖像分柵、OCR同其他計算應用當中）、直骨架（straight skeleton）與及區域圖（zone diagram）。除唨點之外，此類圖仲使用線同多邊形作為種。通過使用連接到種上最近點嘅線段嚟擴充圖表，可以獲得環境嘅平面細分。呢種結構可以用作導航網格，用於穿過好大空間進行搵路。導航網格已得到推廣以支持3D多層環境，例如機場或者多層建築。
已知有幾種有效嘅演算法可用於直接（作為圖本身）或者通過從Delaunay三角剖分開始然之後獲得佢對偶嚟間接構造Voronoi圖。直接演算法包括Fortune演算法，一種O(nlog(n))演算法，用於從平面當中嘅一組點生成Voronoi圖。Bowyer-Watson演算法係一種O(nlog(n))到O(n)演算法，用於生成任意維數嘅Delaunay三角剖分，可用於Voronoi圖嘅間接演算法。JumpFlooding演算法可以喺恆定時間內生成近似嘅Voronoi圖，適用於商品圖形硬件。
Lloyd演算法及佢通過Linde-Buzo-Gray演算法（又名k均值聚類）嘅泛化，使用Voronoi圖嘅構建作為子程序。呢啲方法喺為一組種點構建Voronoi圖嘅步驟同將種點移動到佢胞內中心多啲嘅新位置嘅步驟之間交替。呢啲方法可用於任意維度嘅空間，以迭代收斂於Voronoi圖嘅特殊形式，喊做CentroidalVoronoitessellation，佢當中位點已移動到亦都係佢胞幾何中心嘅點。
Voronoi圖喺顯示結果之前需要一個計算步驟。因此，一個有效嘅工具將實時處理計算以向用戶顯示直接結果。存喺好多商業同免費應用程序。一種特別實用嘅工具係基於網絡嘅工具。基於Web嘅工具易啲訪問同參考。此外，SVG係網絡本機支持嘅格式，同時允許高效（GPU加速）渲染，而且係多種CAD工具（例如AutodeskFusion360）。
即管voronoi係一個非常古老嘅概念，但當前可用嘅工具確實缺乏可以為呢啲程序增加價值嘅多種數學函數。示例可能係使用戥歐幾里得唔同嘅成本距離，主要係3DVoronoi演算法。雖然唔係軟件工具本身，但第一個參考解釋唨3DVoronoi嘅概念，第二個係3DVoronoi庫。