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