How to get Voronoi site points from a diagram

Question

Say we have got a Voronoi diagram from somewhere but there are no points.

Like this but without red points:

We have only borders.

Is there any algorithm that can help to retrieve the points?

---

And what if we have unlimited Voronoi diagram that is stretching long way. Can we have at least one point calculated or are there any heuristic algorithms?

Answer 1

For a single intersection of the Voronoi diagram, you will generally have 3 edges, and 3 sectors between the edges. Call the sectors (and their angles) A, B, and C. Also, call the edge between sectors A and B the edge ab, and likewise for edges bc and ca.

There should be an original site point within each of these sectors; let site a be the site in sector A, site b in sector B, and site c in sector C. Note that the angles to the sites on either side of a sector boundary must be equal, because the distance from the Voronoi edge to each site must be equal. For example, the angle from site a to edge ab must be the same as the angle from edge ab to site b; call this angle X. Likewise let angle Y be the angle from site b to edge bc and from bc to site c; and Z the angle from c to ca and from ca to a.

This gives you the equations:

A = Z + X
B = X + Y
C = Y + Z

With the solution (simplified because A + B + C == 2 * pi):

X = (A + B - C)/2 = pi - C
Y = (B + C - A)/2 = pi - A
Z = (C + A - B)/2 = pi - B

This gives you a ray from any Voronoi intersection to each of its 3 sites. And the intersection of the rays from neighboring Voronoi intersections to the same cell site will give you a location for that site.

---

And, to answer your second question: if you only have 3 sites, then you can only have one Voronoi intersection. In that case, you won't be able to determine your sites -- just their angles from the intersection.

In all other general cases, you can find at least one site as described above; reflection across Voronoi edges should then determine the location of all other sites, including extremal cells that have only one Voronoi intersection.

Answer 2

This question was investigated and half-solved by Ash and Bolker in 1985. For a more modern version that completes that early work, see this:

Biedl, Therese, Martin Held, and Stefan Huber. "Recognizing straight skeletons and Voronoi diagrams and reconstructing their input." In Voronoi Diagrams in Science and Engineering (ISVD), 2013 10th International Symposium on, pp. 37-46. IEEE, 2013. (IEEE link.)

---

         
          ^{(Image from Stefan Huber.)}

---