如何从Voronoï图进行三角测量？

Question

我从一组点（用Boost.polygon）计算出一个Voronoï图。

我尝试找到一个Delaunay三角剖分，连接每个Voronoï边缘的每个单元中心，但我错过了一些边缘。

在下图中，红点是我的初始点，蓝线是沃罗诺伊边缘（我忽略了无限边缘），绿线是三角形边缘（在每个蓝色边缘的绿色边缘上，将两个细胞起源）。

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

Answer 1

4个德洛奈顶点位于一个共同的圆圈，这是一个简并情况。稍稍移动点，你会发现问题。