I computed a Voronoï diagram from a set of points (with Boost.polygon).
I try to find a Delaunay triangulation, connecting each cell center for each Voronoï edge, but I miss some edges.
In the following image, the red dots are my initial points, the blue lines are the Voronoï edges (I ignored infinite edges), and the green lines are the triangulation edges (one green edge for each blue edge, connecting two cell origins).
We can see that diagonal edges are missing. What am I missing?
The centre point in your diagram is a degenerate edge of the Voronoi diagram. If you generate a Voronoi diagram for an irregular point cloud, every vertex will have degree 3. A vertex with degree 4 (or more) can only happen when two (or more) vertices coincide. That means there is a zero-length edge between them. But that edge should still have a corresponding edge in the Delaunay triangulation. The issue is that it's arbitrary which of the two possible edges you pick, because the zero-length edge has no associated direction.
To visualise what I'm talking about, consider starting with four less regularly spaced points (such that we start off with only degree-3 vertices) and gradually translating them into their regular positions.
We can do this in two different ways, which both lead to the degenerate case in your diagram. You will see that you end up with two different Delaunay triangulations, which are both valid limits for the degenerate case:
I assume that your code is missing this degenerate case for one reason or another, but without actually seeing how you compute the Delaunay triangulation from the Voronoi diagram it's impossible to point you any further than this.
Also note that having even higher degeneracies (by more than four points distributed at equal angles around a circle) would probably require additional attention:
These animations also show that (even in a non-degenerate case), the corresponding Voronoi and Delaunay edges do not necessarily actually cross within their finite extent. That might make it harder to see that the 2 (or 3) edges that triangulate the regular polygon at the end actually correspond to several degenerate edges which are all at the centre. Also note that in total there are 5 different triangulations of the pentagon and 14 triangulations of the hexagon (although I don't know whether all 14 can be obtained by deforming a non-degenerate triangulation).
Edit (by OP)
Voronoi diagrams computed with Boost.polygon enable to walk through each Voronoi vertex, and each edge linked to those vertices (clockwise or counter-clockwise). In this way, it is possible to create one triangle for each pair of edges (two connected edges will link to 3 cells).
