直接从 Delaunay 三角剖分计算每个顶点（站点）Voronoi 单元区域
我希望计算与点集的 Delaunay 三角剖分相关的 Voronoi 单元的面积，而不需要显式地将 Delaunay 三角剖分转换为 Voronoi 图。 由于我只关心 Voronoi 单元的区域，因此我想避免显式构建 Voronoi 数据结构的成本。这可能吗？ Delaunay 三角剖分/圆和双 Voronoi 单元面积之间有任何关系吗？ 谢谢，
菲利普
I wish to compute the areas of Voronoi cells which relate to a Delaunay triangulation of a point set without explicitly converting the Delaunay triangulation to a Voronoi graph.
Since I only care about the areas of the Voronoi cells I wanted to avoid the cost of explicitly constructing the Voronoi data structure. Is this possible? Is there any relationship between the Delaunay triangulation/circles and the dual Voronoi cell areas?
Thanks,
Philip
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
使用 CGAL，这里为 3D 情况提供了一个解决方案：
https://lists-sop.inria.fr/sympa/arc/cgal-discuss/2011-01/msg00117.html
Using CGAL, a solution is provided here for the 3D case:
https://lists-sop.inria.fr/sympa/arc/cgal-discuss/2011-01/msg00117.html
一旦您知道了 Voronoi 单元的逆时针顺序的顶点，您就可以使用鞋带公式。然而，这很简单，因为 Delaunay 三角剖分是 Voronoi 图的对偶： Voronoi 顶点与 Delaunay 三角形是对偶的，并且该顶点位于与三角形的等距点处角落。
因此，如果您对点集中点 p 的 Voronoi 单元面积感兴趣，则 (i) 按逆时针顺序考虑所有关联 Delaunay 三角形 T，(ii) 计算 Voronoi 节点的轨迹，以及 (iii)代入鞋带公式。
You can use Shoelace formula once you know the vertices of the Voronoi cell in counter-clockwise order. This, however, is simple as the Delaunay triangulation is the dual of the Voronoi diagram: A Voronoi vertex is dual to a Delaunay triangle, and the vertex is located at the point equidistant to the triangle's corners.
So if you are interested in the area of the Voronoi cell of a point p in a pointset then (i) consider all incident Delaunay triangles T in counter-clockwise order, (ii) compute the loci of the Voronoi nodes, and (iii) plug in into Shoelace formula.