<p>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.</p>

<p>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.</p>

<p>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:</p>

<p><a href="https://i.sstatic.net/eu33Z.gif" rel="noreferrer"><img src="https://i.sstatic.net/eu33Z.gif" alt="enter image description here"></a><a href="https://i.sstatic.net/6S6oX.gif" rel="noreferrer"><img src="https://i.sstatic.net/6S6oX.gif" alt="enter image description here"></a></p>

<p>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.</p>

<p>Also note that having even higher degeneracies (by more than four points distributed at equal angles around a circle) would probably require additional attention:</p>

<p><a href="https://i.sstatic.net/5DgNy.gif" rel="noreferrer"><img src="https://i.sstatic.net/5DgNy.gif" alt="enter image description here"></a><a href="https://i.sstatic.net/AddyS.gif" rel="noreferrer"><img src="https://i.sstatic.net/AddyS.gif" alt="enter image description here"></a></p>

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

<p><strong>Edit</strong> (by OP)</p>

<p>Voronoi diagrams computed with <a href="http://www.boost.org/doc/libs/1_60_0/libs/polygon/doc/index.htm" rel="noreferrer">Boost.polygon</a> 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).</p>

CC BY-SA 3.0
2015-12-18T20:48:24.100Z
You can answer [here](http://stackoverflow.com/questions/34357110/how-to-triangulate-from-a-vorono%C3%AF-diagram) as well or I will delete my other question.
arthur.sw
CC BY-SA 3.0
2015-12-18T20:49:20.453Z
@arthur.sw Cross-posting is generally discouraged on SE, so I suppose deleting it there would be the better option.
Martin Ender
CC BY-SA 3.0
2015-12-19T00:47:21.030Z
an interactive voronoï diagram creator: http://alexbeutel.com/webgl/voronoi.html
arthur.sw
CC BY-SA 3.0
2016-11-30T15:54:23.753Z
See also http://stackoverflow.com/questions/34342038/how-to-triangulate-polygons-in-boost/40892650#40892650 for code
Giovanni Funchal
CC BY-SA 3.0
2015-12-18T20:44:40.927Z
2016-11-30T16:02:01.873Z
2016-11-30T16:02:01.873Z
Martin Ender
<p>I computed a Voronoï diagram from a set of points (with <a href="http://www.boost.org/doc/libs/1_60_0/libs/polygon/doc/voronoi_diagram.htm" rel="noreferrer">Boost.polygon</a>). </p>

<p>I try to find a Delaunay triangulation, connecting each cell center for each Voronoï edge, but I miss some edges.</p>

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

<p>We can see that diagonal edges are missing. What am I missing?</p>

<p><a href="https://i.sstatic.net/JXNcc.png" rel="noreferrer"><img src="https://i.sstatic.net/JXNcc.png" alt="voronoi diagram"></a></p>

<triangulation><polygon>
How to triangulate from a Voronoï diagram?
arthur.sw
# How to triangulate from a Voronoï diagram?

(Asked by: username_0 on 2015-12-18)

I computed a Voronoï diagram from a set of points (with [Boost.polygon](http://www.boost.org/doc/libs/1_60_0/libs/polygon/doc/voronoi_diagram.htm)).

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?

[![voronoi diagram](https://i.sstatic.net/JXNcc.png)](https://i.sstatic.net/JXNcc.png)

**Tags:** triangulation, polygon


---

## 1 answers

### Answer by username_1 on 2015-12-18. Score: 19 | Accepted answer

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:

[![enter image description here](https://i.sstatic.net/eu33Z.gif)](https://i.sstatic.net/eu33Z.gif)[![enter image description here](https://i.sstatic.net/6S6oX.gif)](https://i.sstatic.net/6S6oX.gif)

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:

[![enter image description here](https://i.sstatic.net/5DgNy.gif)](https://i.sstatic.net/5DgNy.gif)[![enter image description here](https://i.sstatic.net/AddyS.gif)](https://i.sstatic.net/AddyS.gif)

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](http://www.boost.org/doc/libs/1_60_0/libs/polygon/doc/index.htm) 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).

> **Comments:**
> **username_0**: You can answer [here](http://stackoverflow.com/questions/34357110/how-to-triangulate-from-a-vorono%C3%AF-diagram) as well or I will delete my other question.  
> **username_1**: @username_0 Cross-posting is generally discouraged on SE, so I suppose deleting it there would be the better option.  
> **username_0**: an interactive voronoï diagram creator: http://alexbeutel.com/webgl/voronoi.html  
> **username_2**: See also http://stackoverflow.com/questions/34342038/how-to-triangulate-polygons-in-boost/40892650#40892650 for code  

---

