从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是相反的vertex_position.alpha,beta并p_i在迭代时更改.c保持其价值.

如果为每个相邻顶点计算这些零件,则得到voronoi区域面积的8倍.