泰森多邊形畫法步驟，Voronoi圖 | 泰森多邊形

概念

Voronoi圖，又叫泰森多邊形、沃羅諾伊圖或Dirichlet圖，是一個關于空間劃分的基礎數據結構。
它是由一組由連接兩鄰點直線的垂直平分線組成的連續多邊形組成。
N個在平面上有區別的點，按照最鄰近原則劃分平面；每個點與它的最近鄰區域相關聯。Delaunay三角形是由與相鄰Voronoi多邊形共享一條邊的相關點連接而成的三角形。Delaunay三角形的外接圓圓心是與三角形相關的Voronoi多邊形的一個頂點。

應用

泰森多邊形畫法步驟？Voronoi圖的應用非常廣泛。在計算幾何中，重心Voronoi圖(CVT)方法被用來優化網格，可以使種子點變得更加均勻。在網絡通訊中，利用加權Voronoi圖設計中繼站的位置可以提高利用率，降低成本。

在幾何形體重構中的應用

• Anton等應用Voronoi圖來實現數字地貌模型(DTM)的生成,已知數據可以包括采樣點。

在計算機圖形學、圖像處理與模式識別中的應用

• Voronoi 圖還被用來獲得圖像中形體的邊界輪廓線。

在物理、化學和分子生物學中的應用

• Defabritiis 等[37]應用Voronoi圖來模擬包含聚合物大分子的復雜流體的動力學行為。

在機器人運動規劃中的應用。

• 如果障礙物可以近似成質點，那么機器人沿著障礙物的Voronoi圖的邊行走是最安全的。

其他應用

• 數學規劃、天體動力學等

總結

• 把 Voronoi 圖作為表示各種元素之間關系的一個結構，通過這個結構可以提取出重要信息。這樣的實例多見于用Voronoi 圖研究自然界物質結構的性質
• 把Voronoi 圖作為一個輔助數據結構，通過這個數據結構可以完成許多關于物體形態或鄰近關系的計算任務。
• 把 Voronoi 圖作為提高某些幾何算法運算速度的重要手段。一般來說，二維的Voronoi圖可以在O(nlogn)時間內獲得，三維的Voronoi圖可以在O(n2)時間內獲得。Voronoi 圖的性質決定了它與許多其他幾何結構具有內在關系，通過Voronoi 圖許多幾何算法可以得到快速運算。

[1]劉金義, 劉爽. Voronoi圖應用綜述[J]. 圖學學報, 2004(02):131-138.