喺數學 當中,Voronoi圖 (粵拼 : Vaa3 laa3 neoi4 tou4 ,俄文 : Диаграмма Вороного ,英文 : Voronoi diagram )係幫一幅平面 分區 成啲區域、各自屬最接近自身嘅一組畀定對象嘅。喺最簡單嘅情況下,呢啲對象衹係平面當中啲有限粒點(又喊做種(seeds)、位點(sites)或者生成點(generators))。對於每粒種,都有一個相應嘅區域 ,喊做Voronoi胞 ,由平面所有啲點(譬如,啲像素點)組成,啲近粒種多過其他種嘅。一組點嘅Voronoi圖對偶 (dual)於佢哋個Delaunay三角剖分 。
20粒點戥啲點各自嘅嘅Voronoi胞(下低有大圖)
Voronoi圖得名於Georgy Voronoy ,亦都喊做Voronoi鑲嵌 、Voronoi分解 、Voronoi分區 或者Dirichlet鑲嵌 (得名於Peter Gustav Lejeune Dirichlet )。Voronoi胞亦都喊做Thiessen多邊形 。[1] [2] [3] Voronoi圖喺好多領域都有實際同理論應用,主要係喺科學 同技術 領域,亦都有喺視覺藝術領域 。[4] [5]
喺最簡單嘅情況下,似第一張圖片所示,畀有喺歐幾里得平面 入便一組有限嘅點{p 1 ,...,p n }。喺呢種情況下,每粒位點p k 衹係一粒點,而且佢對應嘅Voronoi胞R k 由歐幾里得平面當中嘅每粒點組成,呢啲點戥p k 嘅距離細過或者等於佢戥任何其他p k 距離。每個噉嘅胞都係從半空間 嘅交集獲得嘅,因此佢係一個凸多面體 。[6] Voronoii圖啲線段 係指平面當中戥最近嘅兩粒位點等距嘅所有點。Voronoi頂點(節點 )係戥三個(或者多啲)位點等距嘅點。
令
X
{\textstyle X}
係一個度量空間 ,有距離函數
d
{\textstyle d}
.令
K
{\textstyle K}
係一組索引(indices),令
(
P
k
)
k
∈
K
{\textstyle (P_{k})_{k\in K}}
係喺空間
X
{\textstyle X}
裏便嘅非空子集 (位點)嘅元組 (有序集合)。Voronoi胞或者Voronoi區域,
R
k
{\textstyle R_{k}}
,戥位點
P
k
{\textstyle P_{k}}
相關聯嘅,係
X
{\textstyle X}
所有點嘅集合、啲離
P
k
{\textstyle P_{k}}
唔遠過佢哋到其他位點
P
j
{\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}
之間嘅距離,即有
R
k
=
{
x
∈
X
∣
d
(
x
,
P
k
)
≤
d
(
x
,
P
j
)
for all
j
≠
k
}
{\displaystyle 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
∈
K
{\textstyle (R_{k})_{k\in K}}
。原則上,一啲位點可以相交甚至重合(下低嘅應用場合有描述到一啲代表商店嘅位點),但通常假設佢哋係唔相交嘅。另外,定義當中允許無限多個位點(呢種設置喺幾何數論 同晶體學 當中有應用),但同樣喺好多情況下僅衹考慮有限多個位點。
喺空間係有限維歐幾里得空間 嘅特殊情況下,每粒位點都係一粒點,總共有有限咁多粒點而且啲點互相之間都唔同,係噉啲Voronoi胞係凸多面體,佢哋嘅頂點、邊、二維面等可以用組合方式表示。有時,誘導組合結構(induced combinatorial structure )都着喊做Voronoi圖。之不過,普遍情況下,啲Voronoi胞可能唔係凸嘅,甚至可能唔係連通(connected)嘅。
喺通常嘅歐幾里得空間當中,可以用通常嘅術語寫過個形式定義。每個Voronoi多邊形
R
k
{\textstyle R_{k}}
戥生成點
P
k
{\textstyle P_{k}}
相關聯.令
X
{\textstyle X}
係歐幾里得空間當中所有點嘅集合。令
P
1
{\textstyle P_{1}}
成為生成佢Voronoi區域
R
1
{\textstyle R_{1}}
嘅點,
P
2
{\textstyle P_{2}}
產生
R
2
{\textstyle R_{2}}
,同
P
3
{\textstyle P_{3}}
產生
R
3
{\textstyle R_{3}}
等等。然之後似Tran等人 表達嘅,[7] 「歐幾里得平面上嘅Voronoi圖入邊,Voronoi多邊形裏便嘅所有位置都靠近個多邊形嘅生成點,近過任何其他生成點」。
作為一個簡單嘅例,試惗一座城市裏便嘅一組商店,假設要估計畀定商店嘅顧客數量。喺所有啲其他條件(價格、產品、服務質量等)都相同嘅情況下,可以合理噉假設客戶僅衹根據距離嚟考慮選擇佢哋喜歡嘅商店:佢哋會去離佢哋最近嘅商店。喺呢種情況下,Voronoi胞
R
k
{\displaystyle R_{k}}
針對畀定商店
P
k
{\displaystyle P_{k}}
嘅可以攞嚟粗略估計前往間商店嘅潛在客戶數量(以城市嘅一粒點為模型)。
對於大多數城市,可以使用熟悉嘅歐幾里德距離 嚟度啲點之間嘅距離:
ℓ
2
=
d
[
(
a
1
,
a
2
)
,
(
b
1
,
b
2
)
]
=
(
a
1
−
b
1
)
2
+
(
a
2
−
b
2
)
2
{\displaystyle \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
[
(
a
1
,
a
2
)
,
(
b
1
,
b
2
)
]
=
|
a
1
−
b
1
|
+
|
a
2
−
b
2
|
{\displaystyle 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胞可以表示為從位點發出嘅線段嘅聯合。[8] 如圖所示,當未達到距離時,此屬性唔一定成立。
喺相對一般嘅條件下(空間可能係無限維均勻凸空間,可以有無限多個一般形式嘅位點,等等。)Voronoi胞具有一定嘅穩定性:位點形狀嘅微細變化,例如由某啲平移或者扭曲引起嘅變化,會產生Voronoi胞形狀嘅微細變化。呢就係Voronoi圖嘅幾何穩定性。[9] 如圖所示,即使空間係二維嘅(但非均勻凸嘅,特別係非歐幾里得嘅)而且位置係點,呢個屬性通常亦都唔成立。
Voronoi圖嘅非正式使用可以追溯到1644年嘅笛卡兒 。Peter Gustav Lejeune Dirichlet於1850年喺佢對二次型 (quadratic forms)嘅研究當中用咗二維同三維嘅Voronoi圖。英國醫生John Snow喺1854年使用類似Voronoi嘅圖表嚟講明喺Broad Street霍亂爆發 當中死亡嘅大多數人係點樣住喺啲埞係離受感染嘅Broad Street水泵近過任何其他水泵嘅。
Voronoi圖以Georgy Feodosievych Voronoy嘅名字命名,佢喺1908年定義並研究咗一般嘅n 維情況。[10] 喺地球物理學 同氣象學 當中用嘅Voronoi圖,即係Thiessen多邊形,攞嚟分析空間分佈數據(例如降雨量測量)嘅,得名來自美國氣象學家Alfred H. Thiessen。呢個概念嘅其他等效名稱(對應啲特別重要嘅case)有:Voronoi多面體、Voronoi多邊形、影響域、Voronoi分解、Voronoi鑲嵌、Dirichlet鑲嵌。
呢個係3D框當中一組隨機點嘅Voronoi圖嘅切片。通常,3DVoronoi鑲嵌嘅橫截面唔係2DVoronoi鑲嵌本身。(啲胞都係凸 多面體 。)
二維或者三維點嘅規則格 (lattice)嘅Voronoi鑲嵌產生有好多熟悉嘅鑲嵌。
二維晶格提供唔規則嘅蜂窩狀鑲嵌,具有點對稱嘅相等六邊形;喺規則三角形格子嘅情況下,佢係規則嘅;喺矩形格嘅情況下,六邊形減少為行同列嘅矩形;正方形 格子畀出正方形嘅規則鑲嵌;請注意,矩形同正方形亦都可以由其他格子生成(例如,由向量(1,0)同(1/2,1/2)定義嘅格子畀出正方形)。
一個簡單立方晶格 畀出立方蜂窩 。
六邊形密堆積晶格 提供梯形菱形十二面體 嘅空間鑲嵌。
面心立方晶格 提供菱形十二面體 嘅空間鑲嵌。
體心立方晶格 畀出切角八面體 嘅空間鑲嵌。
平行平面,具有彼此中心對齊嘅規則三角形晶格嘅,形成六邊形棱柱蜂窩 。
某啲以體心為中心嘅四邊形晶格,畀出菱形六角化十二面體 嘅空間鑲嵌。
對於點集(x , y ),x 喺離散集合X 當中,y 喺離散集合Y 當中,得到啲矩形塊,啲點唔一定喺佢哋嘅中心嘅。
正常嘅Voronoi胞着定義成最接近S 當中單粒點嘅點集,但「n 階Voronoi胞」着定義成個點集、以S 裏頭特定n 粒點作為啲n 粒最近鄰點嘅。高階Voronoi圖亦都細分唨空間。
高階Voronoi圖可以攞遞歸來生成。要生成集合 S 當中嘅第n 階Voronoi圖,可以從第(n - 1)階圖落手並替換啲由X = {x 1 , x 2 , ..., x n −1 }生成嘅每個胞,替換成喺集合 S - X 上生成嘅Voronoi圖。
至遠點Voronoi圖
對於一組n 粒點,第(n - 1)階Voronoi圖喊做至遠點(farthest-point)Voronoi圖。
對於畀定嘅一組點S = {p 1, p 2, ..., p n },至遠點Voronoi圖將平面劃分為多個胞,喺其中P 嘅同樣點即係粒至遠點。喺至遠點Voronoi圖當中嘅一粒點P 要有一個胞嘅話,若且唯若佢係P 嘅凸殼(convex hull)嘅一個頂點。令H = {h 1 , h 2, ..., h k }係P 嘅凸殼;係噉至遠點Voronoi圖係將平面細分為k 個胞,每個胞對應於H 當中嘅每粒點,啲點具有屬性係:對於一粒點q ,每個p j ∈ S 而且唔同於hi (即hi ≠ pj ),若且唯若d(q ,h i )>d(q ,p j ),即話嗰粒點q 處於個對應位點h i 嘅胞入便;其中d(p, q )係p 戥 q 兩粒點嘅歐幾里得距離 。[11] [12]
至遠點Voronoi圖當中啲胞嘅邊界具有拓撲樹 嘅結構,以無限射線 為佢啲葉。每蔸有限樹同構(isomorphic)於嗰蔸噉樣由至遠點Voronoi圖形成嘅樹。
正如定義所暗示嘅噉,可以為除歐幾里得以外嘅度量定義Voronoi胞,例如馬哈拉諾比斯距離 或者曼哈頓距離 。之不過,喺呢啲情況下,Voronoi胞嘅邊界可能複雜過歐幾里得距離嘅情況,因為即使喺二維情況下,兩點嘅等距軌跡亦都可能冇辦法成為餘維1(codimension 1)嘅子空間。
一組點嘅近似Voronoi圖。注意Voronoi胞模糊邊界當中啲溝混顏色。
加權Voronoi圖 係噉嘅一種圖,佢當中定義啲Voronoi胞嘅一對點嘅函數係一種模改過嘅距離函數,通過乘或者加啲權重、啲分配畀生成器點嘅嚟改到出嚟。戥使用度量(metric)嘅距離定義嘅Voronoi胞格情況相反,喺呢種情況下,一啲Voronoi胞格可能係空嘅。冪圖 係一種使用圓冪距離 (power distance)從一組圓定義出來嘅Voronoi圖;佢亦都可以着認為係一個加權嘅Voronoi圖,佢當中根據每個圓嘅半徑定義嘅權重着添加到距圓心嘅平方歐幾里德距離 上。[13]
喺
d
{\displaystyle d}
維空間
n
{\displaystyle n}
粒點嘅Voronoi圖可以有
O
(
n
⌈
d
/
2
⌉
)
{\textstyle O(n^{\lceil d/2\rceil })}
笪頂點,需要到戥存儲佢嘅顯式描述所需嘅內存量相同嘅界限。因此,Voronoi圖對於中等或者高維通常唔可行得。節省多啲空間嘅替代方法係使用近似嘅Voronoi圖。[14]
Voronoi圖仲戥其他幾何結構有關,例如中軸 (已應用喺圖像分柵 、OCR 同其他計算應用當中)、直骨架(straight skeleton)與及區域圖(zone diagram)。除唨點之外,此類圖仲使用線同多邊形作為種。通過使用連接到種上最近點嘅線段嚟擴充圖表,可以獲得環境嘅平面細分。[15] 呢種結構可以用作導航網格, 用於穿過好大空間進行搵路。導航網格已得到推廣以支持3D多層環境,例如機場或者多層建築。[16]
人文學科
喺古典考古學,特別係藝術史 當中,分析雕像 頭部嘅對稱性以確定着切斷嘅頭部可能屬於嘅雕像類型。使用Vornoi胞嘅一個例子係Sabouroff頭部嘅識別,佢使用唨高分辨率多邊形網格 。[17] [18]
自然科學
Voronoi鑲嵌通過從種向外嘅徑向生長而出現。
喺生物學 當中,Voronoi圖用於模擬好多唔同嘅生物結構,包括胞 [19] 同骨骼微結構。 [20] 事實上,Voronoi鑲嵌作為一種幾何工具嚟理解驅動生物組織組織嘅物理約束。[21]
喺水文學 當中,Voronoi圖用於根據一系列點測量計算一個區域嘅降雨量。喺呢種用法當中,佢哋通常着喊做Thiessen多邊形。
喺生態學 當中,Voronoi圖用於研究森林同森林冠層嘅生長模式,亦都可能有助於開發森林火災嘅預測模型。
喺計算化學 當中,配體結合位點着轉化為用於機器學習 應用嘅Voronoi圖(例如,對蛋白質當中嘅結合口袋進行分類)。[22] 喺其他應用當中,由分子當中原子核嘅位置定義嘅Voronoi胞用於計算原子電荷。呢個係使用Voronoi變形密度方法完成嘅。
喺天體物理學 當中,Voronoi圖用於喺圖像上生成自適應平滑區域,喺每個區域上添加信號通量。呢啲程序嘅主要目標係喺所有圖像上保持相對恆定嘅信噪比。
喺計算流體動力學 當中,一組點嘅Voronoi細分可用於定義有限體積方法當中使用嘅計算域,例如喺移動網格宇宙學代碼AREPO當中。[23]
喺運算物理學 當中,Voronoi圖用於喺高能量密度物理學當中使用陰影圖同質子射線照相計算物體嘅輪廓。[24]
健康
喺醫學診斷 當中,基於Voronoi圖嘅肌肉組織模型可用於檢測神經肌肉疾病。[21]
喺傳染病學 當中,Voronoi圖可用於關聯流行病當中嘅感染源。約翰·斯諾(JohnSnow)實施唨Voronoi圖嘅早期應用之一,以研究1854年喺英格蘭蘇荷區爆發嘅寬街霍亂。他展示唨倫敦市中心地圖上居民一直喺使用特定水泵嘅居民區戥因疫情而死亡人數最多嘅地區之間嘅相關性。[25]
工程
喺聚合物物理學當中,Voronoi圖可用於表示聚合物嘅自由體積。
喺材料科學 當中,金屬合金當中嘅多晶微觀結構通常使用Voronoi鑲嵌嚟表示。喺島嶼增長當中,Voronoi圖用於估計單個島嶼嘅增長率。[26] [27] [28] [29] 喺固態物理學當中,Wigner-Seitz胞 係固體嘅Voronoi鑲嵌,布里淵區 係具有空間群對稱性嘅晶體倒數(波數)空間嘅Voronoi鑲嵌。
喺航空 領域,隨著飛機執行佢飛行計劃,Voronoi圖疊加喺海洋繪圖圖上以識別最近嘅飛行當中改道機場(參見ETOPS)。
喺建築學 ,Voronoi圖案係重新開發黃金海岸藝術中心嘅獲獎作品嘅基礎。[30]
喺城市規劃 當中,Voronoi圖可用於評估貨運裝載區系統。[31]
喺礦業 當中,Voronoi多邊形用於估計有價值嘅材料、礦物或者其他資源嘅儲量。勘探鑽孔用作Voronoi多邊形當中嘅一組點。
喺表面計量學當中,Voronoi曲面細分可用於表面粗糙度 建模。[32]
喺機械人學 當中,多機器人系統嘅一啲控制策略係基於環境嘅Voronoi分區。[33] [34]
幾何學
可以喺Voronoi圖嘅頂部構建點位置數據結構,以回答最近鄰查詢,佢當中人們想要找到最接近畀定查詢點嘅對象。最近鄰查詢有很多應用。例如,人們可能想喺數據庫 當中找到最近嘅醫院或者最相似嘅對象。一個大型應用係矢量量化,通常用於數據壓縮 。
喺幾何學 當中,Voronoi圖可用於喺一組點同封閉多邊形當中找到最大嘅空圓;例如,喺某個城市,盡可能遠離現有嘅所有超市,建造一個新嘅超市。
Voronoi圖戥至遠點Voronoi圖一起用於計算一組點嘅圓度嘅有效演算法。[11] Voronoi方法仲用於評估圓度/圓度,同時評估嚟自坐標測量機嘅數據集。
訊息學
喺網絡 領域,Voronoi圖可以攞嚟推導無線網絡嘅容量。
喺電腦圖形學 領域,Voronoi圖用於計算3D破碎/破裂幾何圖案。佢仲用於程序生成 有機或者岩漿外觀嘅紋理。
喺自主機器人導航當中,Voronoi圖用嚟尋找清楚嘅路線。若果啲點係障礙物,係噉圖嘅邊線即係所需嘅路線,距離啲障礙物最遠嘅(理論上嚟避免到啲碰撞)。
喺機械學習 當中,Voronoi圖用於進行1-NN分類。[35]
喺用家介面 開發當中,Voronoi模式可用於計算畀位點嘅最佳懸停狀態。[36]
日常生活
喺墨爾本 ,公立學校嘅學生總係有資格就讀啲小學或者高中距離佢哋居住地最近嘅,直線距離衡量。因此,啲學區地圖係Voronoi圖。[37]
烏克蘭糕點廚師DinaraKasko使用Voronoi圖嘅數學原理,用3D打印機製作矽膠模具嚟塑造佢啲原創蛋糕。
已知有幾種有效嘅演算法可用於直接(作為圖本身)或者通過從Delaunay三角剖分開始然之後獲得佢對偶嚟間接構造Voronoi圖。直接演算法包括Fortune演算法,一種O (n log(n ))演算法,用於從平面當中嘅一組點生成Voronoi圖。Bowyer-Watson演算法係一種O (n log(n ))到O (n 2 )演算法,用於生成任意維數嘅Delaunay三角剖分,可用於Voronoi圖嘅間接演算法。JumpFlooding演算法可以喺恆定時間內生成近似嘅Voronoi圖,適用於商品圖形硬件。[38] [39]
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
Tran, Q. T.; Tainar, D.; Safar, M. (2009). Transactions on Large-Scale Data- and Knowledge-Centered Systems . p. 357. ISBN 9783642037214 .
7.4 Farthest-Point Voronoi Diagrams. Includes a description of the algorithm.
Edelsbrunner, Herbert (2012) [1987]. "13.6 Power Diagrams". Algorithms in Combinatorial Geometry . EATCS Monographs on Theoretical Computer Science.第10卷. Springer-Verlag. pp. 327–328. ISBN 9783642615689 . .
Hölscher, Tonio; Krömker, Susanne; Mara, Hubert (2020), "Der Kopf Sabouroff in Berlin: Zwischen archäologischer Beobachtung und geometrischer Vermessung", Gedenkschrift für Georgios Despinis (德文), Athens, Greece: Benaki Museum
Hui Li (2012). Baskurt, Atilla M; Sitnik, Robert (編). "Spatial Modeling of Bone Microarchitecture". Three-Dimensional Image Processing (3Dip) and Applications Ii . 8290 : 82900P. Bibcode :2012SPIE.8290E..0PL . doi :10.1117/12.907371 .
Feinstein, Joseph; Shi, Wentao; Ramanujam, J.; Brylinski, Michal (2021), Ballante, Flavio (編), "Bionoi: A Voronoi Diagram-Based Representation of Ligand-Binding Sites in Proteins for Machine Learning Applications" , Protein-Ligand Interactions and Drug Design , Methods in Molecular Biology (英文), New York, NY: Springer US, 2266 : 299–312, doi :10.1007/978-1-0716-1209-5_17 , ISBN 978-1-0716-1209-5 , PMID 33759134 , 喺2021-04-23 搵到
"School zones" . Victorian Government Department of Education and Training (英文). 原著 喺2020-08-11歸檔. 喺2020-08-24 搵到 .
Aurenhammer, Franz ; Klein, Rolf; Lee, Der-Tsai (2013). Voronoi Diagrams and Delaunay Triangulations . World Scientific. ISBN 978-9814447638 .
Bowyer, Adrian (1981). "Computing Dirichlet tessellations" . Comput. J. 24 (2): 162–166. doi :10.1093/comjnl/24.2.162 .
Includes a description of Fortune's algorithm.
Klein, Rolf (1989). "Abstract Voronoi diagrams and their applications". Computational Geometry and its Applications . Lecture Notes in Computer Science .第333卷. Springer. pp. 148–157. doi :10.1007/3-540-50335-8_31 . ISBN 978-3-540-52055-9 .
Lejeune Dirichlet, G. (1850). "Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen". Journal für die Reine und Angewandte Mathematik . 1850 (40): 209–227. doi :10.1515/crll.1850.40.209 .
Okabe, Atsuyuki; Boots, Barry; Sugihara, Kokichi ; Chiu, Sung Nok (2000). Spatial Tessellations — Concepts and Applications of Voronoi Diagrams (第2版). Wiley. ISBN 0-471-98635-6 .
Reem, Daniel (2009). "An algorithm for computing Voronoi diagrams of general generators in general normed spaces". Proceedings of the Sixth International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2009) . pp. 144–152. doi :10.1109/ISVD.2009.23 .
Reem, Daniel (2011). "The geometric stability of Voronoi diagrams with respect to small changes of the sites". Proceedings of the 27th Annual ACM Symposium on Computational Geometry (SoCG) : 254–263. arXiv :1103.4125 . Bibcode :2011arXiv1103.4125R . doi :10.1145/1998196.1998234 . ISBN 9781450306829 . S2CID 14639512 .
Voronoï, Georges (1908a). "Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Premier mémoire. Sur quelques propriétés des formes quadratiques positives parfaites" (PDF) . Journal für die Reine und Angewandte Mathematik . 1908 (133): 97–178. doi :10.1515/crll.1908.133.97 . S2CID 116775758 .
Voronoï, Georges (1908b). "Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire. Recherches sur les parallélloèdres primitifs" (PDF) . Journal für die Reine und Angewandte Mathematik . 1908 (134): 198–287. doi :10.1515/crll.1908.134.198 . S2CID 118441072 .
Watson, David F. (1981). "Computing the n -dimensional Delaunay tessellation with application to Voronoi polytopes" . Comput. J. 24 (2): 167–172. doi :10.1093/comjnl/24.2.167 .
軟件
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庫。