How to get Voronoi site points from a diagram

4
votes

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?

2
algorithmcomputational-geometryvoronoi
Welcome to StackOverflow. However, your question does not follow our guidelines on How to Ask a good question. First, the question is not clear. Exactly how is the diagram given? Show an example data structure that holds a Voronoi diagram. Second, you show no work of your own, so it looks like you are just dumping your homework on us. Please tell us some of the work you have done so far on this problem, preferably including code, and tell us where you are stuck. – Rory Daulton
mathoverflow.net/questions/257100/… – RaffleBuffle
Rory Daulton data structure doesn't really matter. The question was about algorithms but not an implementation etc. Second, who dumps what? That is problem not associated with school. And I did nothing before because I am not a mathematitian or something – Johnson
SirRaffleBuffle Thank you a looooooot! – Johnson

2 Answers

2
votes

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. enter image description here 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.

2
votes

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.)