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

#1 楼

图中的中心点是Voronoi图的退化边缘。如果为不规则点云生成Voronoi图，则每个顶点将具有度3。只有两个（或多个）顶点重合时，度4（或更大）的顶点才能发生。这意味着它们之间存在零长度的边。但是该边缘在Delaunay三角剖分中仍应具有相应的边缘。问题在于，您可以随意选择两个可能的边缘中的哪一个，因为零长度的边缘没有相关的方向。点（因此我们仅从3度顶点开始）并将它们逐渐转换为它们的常规位置。

我们可以通过两种不同的方式来完成此操作，这两种方式都会导致图形中的简并情况。您将看到最终得到两个不同的Delaunay三角剖分，它们都是退化案例的有效限制：



我假设您的代码缺少此退化的出于某种原因或其他原因，但实际上并没有从Voronoi图中看到如何计算Delaunay三角剖分，就不可能再向您指出这一点。围绕一个圆以相等角度分布的四个点）可能需要格外注意：



这些动画还显示（即使在非退化的情况下），相应的Voronoi和Delaunay边缘也不一定在它们的有限范围内实际交叉。这可能使得更难于看到末端对规则多边形进行三角剖分的2条（或3条）边缘实际上对应于全部位于中心的几个退化边缘。另请注意，总共有五种不同的五边形三角剖分和14种六边形三角剖分（尽管我不知道是否可以通过变形非退化三角剖分获得全部14个三角剖分）。

编辑（由OP提供）

使用Boost.polygon计算的Voronoi图可以遍历每个Voronoi顶点以及与这些顶点链接的每个边（顺时针或逆时针）。这样，可以为每对边创建一个三角形（两个相连的边将链接到3个单元格）。