geometry - 直接从 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

一旦您知道按逆时针顺序排列的 Voronoi 单元的顶点，您就可以使用鞋带公式。然而，这很简单，因为 Delaunay 三角剖分是Voronoi 图的对偶：Voronoi 顶点与 Delaunay 三角形是对偶的，并且顶点位于与三角形角等距的点处。

因此，如果您对点集中点 p 的 Voronoi 单元的面积感兴趣，那么 (i) 按逆时针顺序考虑所有入射的 Delaunay 三角形 T，(ii) 计算 Voronoi 节点的轨迹，以及 (iii)插入鞋带公式。