跳去內容

Voronoi圖

出自維基百科,自由嘅百科全書
20粒點戥啲點各自嘅嘅Voronoi胞(下低有大圖)

數學當中,Voronoi圖粵拼Vaa3 laa3 neoi4 tou4俄文Диаграмма Вороного英文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多邊形[1][2][3]Voronoi圖喺好多領域都有實際同理論應用,主要係喺科學技術領域,亦都有喺視覺藝術領域[4][5]

最簡單嘅情況

[編輯]

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

正式定義

[編輯]

係一個度量空間,有距離函數.令係一組索引(indices),令係喺空間裏便嘅非空子集(位點)嘅元組(有序集合)。Voronoi胞或者Voronoi區域,,戥位點相關聯嘅,係所有點嘅集合、啲離唔遠過佢哋到其他位點嘅,其中係任何唔同於嘅索引。即係話,若果表示點同子集之間嘅距離,即有Voronoi圖衹係啲胞嘅元組。原則上,一啲位點可以相交甚至重合(下低嘅應用場合有描述到一啲代表商店嘅位點),但通常假設佢哋係唔相交嘅。另外,定義當中允許無限多個位點(呢種設置喺幾何數論晶體學當中有應用),但同樣喺好多情況下僅衹考慮有限多個位點。

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

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

例證

[編輯]

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

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

或者曼哈頓距離

.

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

20粒點嘅Voronoi圖,喺兩種唔同度量(metrics)下

特性

[編輯]
  • 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鑲嵌產生有好多熟悉嘅鑲嵌。

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

高階Voronoi圖

[編輯]

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

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

至遠點Voronoi圖

[編輯]

對於一組n粒點,第(n - 1)階Voronoi圖喊做至遠點(farthest-point)Voronoi圖。

對於畀定嘅一組點S = {p1, p2, ..., pn},至遠點Voronoi圖將平面劃分為多個胞,喺其中P嘅同樣點即係粒至遠點。喺至遠點Voronoi圖當中嘅一粒點P要有一個胞嘅話,若且唯若佢係P嘅凸殼(convex hull)嘅一個頂點。令H = {h1h2, ..., hk}係P嘅凸殼;係噉至遠點Voronoi圖係將平面細分為k個胞,每個胞對應於H當中嘅每粒點,啲點具有屬性係:對於一粒點q,每個pj ∈ S而且唔同於hi(即hipj),若且唯若d(q,hi)>d(q,pj),即話嗰粒點q處於個對應位點hi嘅胞入便;其中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]

維空間粒點嘅Voronoi圖可以有笪頂點,需要到戥存儲佢嘅顯式描述所需嘅內存量相同嘅界限。因此,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(nlog(n))演算法,用於從平面當中嘅一組點生成Voronoi圖。Bowyer-Watson演算法係一種O(nlog(n))到O(n2)演算法,用於生成任意維數嘅Delaunay三角剖分,可用於Voronoi圖嘅間接演算法。JumpFlooding演算法可以喺恆定時間內生成近似嘅Voronoi圖,適用於商品圖形硬件。[38][39]

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

睇埋

[編輯]

內註

[編輯]
  1. Burrough, Peter A.; McDonnell, Rachael; McDonnell, Rachael A.; Lloyd, Christopher D. (2015). "8.11 Nearest neighbours: Thiessen (Dirichlet/Voroni) polygons". Principles of Geographical Information Systems. Oxford University Press. pp. 160–. ISBN 978-0-19-874284-5.
  2. Longley, Paul A.; Goodchild, Michael F.; Maguire, David J.; Rhind, David W. (2005). "14.4.4.1 Thiessen polygons". Geographic Information Systems and Science. Wiley. pp. 333–. ISBN 978-0-470-87001-3.
  3. Sen, Zekai (2016). "2.8.1 Delaney, Varoni, and Thiessen Polygons". Spatial Modeling Principles in Earth Sciences. Springer. pp. 57–. ISBN 978-3-319-41758-5.
  4. Aurenhammer, Franz (1991). "Voronoi Diagrams – A Survey of a Fundamental Geometric Data Structure". ACM Computing Surveys. 23 (3): 345–405. doi:10.1145/116873.116880.
  5. Okabe, Atsuyuki; Boots, Barry; Sugihara, Kokichi; Chiu, Sung Nok (2000). Spatial Tessellations – Concepts and Applications of Voronoi Diagrams (第2版). John Wiley. ISBN 978-0-471-98635-5.
  6. Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization. Exercise 2.9: Cambridge University Press. p. 60.{{cite book}}: CS1 maint: location (link)
  7. Tran, Q. T.; Tainar, D.; Safar, M. (2009). Transactions on Large-Scale Data- and Knowledge-Centered Systems. p. 357. ISBN 9783642037214.
  8. Reem 2009.
  9. Reem 2011.
  10. Voronoï 1908a and Voronoï 1908b.
  11. 11.0 11.1 de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2008). Computational Geometry (第Third版). Springer-Verlag. ISBN 978-3-540-77974-2. 7.4 Farthest-Point Voronoi Diagrams. Includes a description of the algorithm.
  12. Skyum, Sven (18 February 1991). "A simple algorithm for computing the smallest enclosing circle". Information Processing Letters. 37 (3): 121–125. doi:10.1016/0020-0190(91)90030-L., contains a simple algorithm to compute the farthest-point Voronoi diagram.
  13. 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..
  14. Sunil Arya, Sunil; Malamatos, Theocharis; Mount, David M. (2002). "Space-efficient approximate Voronoi diagrams". Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. pp. 721–730. doi:10.1145/509907.510011. ISBN 1581134959.
  15. Geraerts, Roland (2010), Planning Short Paths with Clearance using Explicit Corridors (PDF), International Conference on Robotics and Automation, IEEE, pp. 1997–2004.
  16. van Toll, Wouter G.; Cook IV, Atlas F.; van Kreveld, Marc J.; Geraerts, Roland (2018), The Medial Axis of a Multi-Layered Environment and its Application as a Navigation Mesh (PDF), ACM Transactions on Spatial Algorithms and Systems, pp. 2:1–2:34.
  17. 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
  18. YouTube上面嘅Voronoi Cells & Geodesic Distances - Sabouroff head. Analysis using the GigaMesh Software Framework as described by Hölscher et al. cf. doi:10.11588/heidok.00027985.
  19. Bock, Martin; Tyagi, Amit Kumar; Kreft, Jan-Ulrich; Alt, Wolfgang (2009). "Generalized Voronoi Tessellation as a Model of Two-dimensional Cell Tissue Dynamics". Bulletin of Mathematical Biology. 72 (7): 1696–1731. arXiv:0901.4469v1. Bibcode:2009arXiv0901.4469B. doi:10.1007/s11538-009-9498-3. PMID 20082148.
  20. 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.
  21. 21.0 21.1 Sanchez-Gutierrez, D.; Tozluoglu, M.; Barry, J. D.; Pascual, A.; Mao, Y.; Escudero, L. M. (2016-01-04). "Fundamental physical cellular constraints drive self-organization of tissues". The EMBO Journal. 35 (1): 77–88. doi:10.15252/embj.201592374. PMC 4718000. PMID 26598531.
  22. 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搵到
  23. Springel, Volker (2010). "E pur si muove: Galilean-invariant cosmological hydrodynamical simulations on a moving mesh". MNRAS. 401 (2): 791–851. arXiv:0901.4107. Bibcode:2010MNRAS.401..791S. doi:10.1111/j.1365-2966.2009.15715.x.
  24. Kasim, Muhammad Firmansyah (2017-01-01). "Quantitative shadowgraphy and proton radiography for large intensity modulations". Physical Review E. 95 (2): 023306. arXiv:1607.04179. Bibcode:2017PhRvE..95b3306K. doi:10.1103/PhysRevE.95.023306. PMID 28297858.
  25. Steven Johnson (19 October 2006). The Ghost Map: The Story of London's Most Terrifying Epidemic — and How It Changed Science, Cities, and the Modern World. Penguin Publishing Group. p. 187. ISBN 978-1-101-15853-1. 喺16 October 2017搵到.
  26. Mulheran, P. A.; Blackman, J. A. (1996). "Capture zones and scaling in homogeneous thin-film growth". Physical Review B. 53 (15): 10261–7. Bibcode:1996PhRvB..5310261M. doi:10.1103/PhysRevB.53.10261. PMID 9982595.
  27. Pimpinelli, Alberto; Tumbek, Levent; Winkler, Adolf (2014). "Scaling and Exponent Equalities in Island Nucleation: Novel Results and Application to Organic Films". The Journal of Physical Chemistry Letters. 5 (6): 995–8. doi:10.1021/jz500282t. PMC 3962253. PMID 24660052.
  28. Fanfoni, M.; Placidi, E.; Arciprete, F.; Orsini, E.; Patella, F.; Balzarotti, A. (2007). "Sudden nucleation versus scale invariance of InAs quantum dots on GaAs". Physical Review B. 75 (24): 245312. Bibcode:2007PhRvB..75x5312F. doi:10.1103/PhysRevB.75.245312. ISSN 1098-0121.
  29. Miyamoto, Satoru; Moutanabbir, Oussama; Haller, Eugene E.; Itoh, Kohei M. (2009). "Spatial correlation of self-assembled isotopically pure Ge/Si(001) nanoislands". Physical Review B. 79 (165415): 165415. Bibcode:2009PhRvB..79p5415M. doi:10.1103/PhysRevB.79.165415. ISSN 1098-0121.
  30. "GOLD COAST CULTURAL PRECINCT". ARM Architecture. 原著喺2016年7月7號歸檔. 喺2021年6月8號搵到.
  31. Lopez, C.; Zhao, C.-L.; Magniol, S; Chiabaut, N; Leclercq, L (28 February 2019). "Microscopic Simulation of Cruising for Parking of Trucks as a Measure to Manage Freight Loading Zone". Sustainability. 11 (5), 1276.
  32. Singh, K.; Sadeghi, F.; Correns, M.; Blass, T. (December 2019). "A microstructure based approach to model effects of surface roughness on tensile fatigue". International Journal of Fatigue. 129: 105229. doi:10.1016/j.ijfatigue.2019.105229.
  33. Cortes, J.; Martinez, S.; Karatas, T.; Bullo, F. (April 2004). "Coverage control for mobile sensing networks". IEEE Transactions on Robotics and Automation. 20 (2): 243–255. doi:10.1109/TRA.2004.824698. ISSN 2374-958X.
  34. Teruel, Enrique; Aragues, Rosario; López-Nicolás, Gonzalo (April 2021). "A Practical Method to Cover Evenly a Dynamic Region With a Swarm". IEEE Robotics and Automation Letters. 6 (2): 1359–1366. doi:10.1109/LRA.2021.3057568. ISSN 2377-3766.
  35. Mitchell, Tom M. (1997). Machine Learning (第International版). McGraw-Hill. p. 233. ISBN 978-0-07-042807-2.
  36. "User Interface Algorithms".
  37. "School zones". Victorian Government Department of Education and Training (英文). 原著喺2020-08-11歸檔. 喺2020-08-24搵到.
  38. https://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf
  39. https://www.shadertoy.com/view/4syGWK

[編輯]

出面網頁

[編輯]

軟件

[編輯]

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庫。