Compute the size of Voronoi regions from Delaunay

问题:

I would like to compute the mean and standard deviation of the areas of a set of Voronoi regions in 2D (if the region extends to infinity, I'll just clip it to the unit square).

However if possible I would like to do this computation from the Delaunay Triangulation without explicitly computing the Voronoi regions? Is this even possible, or is it better to just compute the Voronoi diagram explicitly?

回答1:

In order to calculate the voronoi region of a vertex you need to iterate the 1-ring around it. Then the area of the region is defined as:

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

In the image you can see the whole voronoi region in light red. A part of it is shown in dark red. This is one of the parts accumulated by the sum. alpha and beta are the angles as visible in the image. c is the center vertex position. p_i is the opposite vertex_position. alpha, beta and p_i change while iterating. c keeps its value.

If you calculate those parts for every adjacent vertex, you get 8 times the area of the voronoi region.