CGAL users discussion list

[Olivier Devillers <>]

Le 2/4/14 6:41 PM, Michael Klatt a écrit :
> Dear Monique Teillaud,
>
> thank you for your help. Sorry, I still have a question: The
> function "dual (Vertex_handle v, OutputIterator pts)" returns in
> the output iterator the vertices of the Voronoi cell with center v.
> Is that right? For a cubic Voronoi cell I get 24 points.

24 is the right number, this is due of the simulation of simplicity 
method used to get rid of degeneracies in the Delaunay computation.


More precisely, if you have just one vertex in the periodic triangulation,
the Voronoi cell is a cube, and the Delaunay cell is a cube which is a 
very degenerate configuration
(much more than 5 cocircular points).
The Delaunay cell is then triangulated (in a way fixed by a perturbation 
scheme)
in 6 tetrahedron.
If you go to the dual, it means that the Voronoi vertex is splitted in 6 
different Voronoi vertices
at the same location, with zero length edges to link them, but all these 
6 different vertices
do not appear all in the 8 incident Voronoi cells (before perturb), 
actually each appear in only
four cells (that's exactly the purpose of the perturbation).
Finally, the Voronoi cell has 6 "main vertices" split in 4 in average -> 
24 vertices.

You can try to print the position of your vertices and check that you 
actually have only 6 different positions.