algorithm - 从 Delaunay 三角剖分计算 Voronoi 区域的大小？

Question

我想计算 2D 中一组 Voronoi 区域的面积的平均值和标准偏差（如果该区域延伸到无穷大，我将其剪裁到单位正方形）。

但是，如果可能的话，我想在不明确计算 Voronoi 区域的情况下从 Delaunay Triangulation 进行此计算？这甚至可能吗，还是直接计算 Voronoi 图更好？

Answer 1

为了计算顶点的 voronoi 区域，您需要围绕它迭代 1 环。那么该区域的面积定义为：

A = 1/8 * (sum for every adjacent vertex p_i) { (cot alpha_i + cot beta_i) * (p_i - c).Length² }

在图像中，您可以看到整个浅红色的 voronoi 区域。它的一部分显示为深红色。这是总和累积的部分之一。alpha并且beta是图像中可见的角度。c是中心顶点位置。p_i是相反的顶点位置。alpha,beta并p_i在迭代时改变。c保持它的价值。

如果你计算每个相邻顶点的这些部分，你会得到 voronoi 区域面积的 8 倍。