直接從Delaunay三角測量計算每個頂點（站點）Voronoi單元區域

Question

我希望計算與點集合的Delaunay三角剖分相關的Voronoi單元的面積，而無需將Delaunay三角剖分顯式轉換爲Voronoi圖形。 因爲我只關心Voronoi單元的區域，所以我想避免明確構造Voronoi數據結構的代價。這可能嗎？ Delaunay三角剖分/圓和雙Voronoi單元區之間是否有任何關係？ 謝謝，

菲利普

Answer 1

使用CGAL，解決這裏提供3D情況：

https://lists-sop.inria.fr/sympa/arc/cgal-discuss/2011-01/msg00117.html

Answer 2

您可以使用Shoelace formula一旦你知道在反的Voronoi單元的頂點順時針順序。然而，這很簡單，因爲Delaunay三角剖分是dual of the Voronoi diagram：Voronoi頂點與Delaunay三角形是雙重對應的，並且頂點位於與三角形拐角等距的點。 （i）以逆時針順序考慮所有事件Delaunay三角形T，（ii）計算Voronoi節點的軌跡，（ii）計算Voronoi節點的軌跡，和（iii）插入鞋帶配方。