如何从 Voronoï 图进行三角剖分？

Question

我根据一组点（Boost.polygon）计算了一个 Voronoï 图。

我尝试找到 Delaunay 三角剖分，连接每个 Voronoï 边的每个像元中心，但我遗漏了一些边。

在下图中，红点是我的初始点，蓝线是 Voronoï 边（我忽略了无限边），绿线是三角剖分边（每个蓝色边在绿色边上，连接两个细胞起源）。

我们可以看到缺少对角线边缘。我错过了什么？

Answer 1

4个Delaunay顶点位于一个公共圆上，这是退化的情况。稍微移动一下点，您就会发现问题所在。