具有四个或更多共圆点的数据集的 Delaunay 三角剖分

计算科学 计算几何 delaunay三角剖分
2021-12-21 04:44:35

我正在开发一个需要将多边形细分为三角形的库。多边形被（或多或少）其中的随机点分成三角形。通常，该方法是对一组这些点执行 Delaunay 三角剖分。这非常有效，但是有时我的结果中会出现相交的三角形。当我有三个以上的共圆点时，就会发生这种情况。对于 Delaunay 三角剖分，我使用了简单的 Watson 算法。我的问题是：

  1. 如果有四个或更多的共圆点怎么办。我读过的所有 CG 书籍都没有提到处理它。只是它是一些特殊情况。

  2. 是否有其他三角测量（类似于 Delaunay - 我不能插入任何额外的点）我可能会使用。

1个回答

您可以使用精确谓词来检测共圆点，并使用符号扰动来一致地决定要生成哪些三角形。

关于精确谓词：

  • 如果您的点坐标是整数，则更容易，您可以使用 Hadamar 不等式来确定谓词计算的值不会溢出的有效坐标范围。
  • 如果使用浮点坐标，那么实现起来会比较棘手。您可以使用任意精度库（例如 MPFR）或算术扩展（如 Shewchuk [1] 所建议的，另请参见他的“三角形”软件）

关于符号扰动：

每当谓词回答“就在圆圈上”时，您需要始终如一地消除歧义。在“SOS”文章 [2] 中解释了一种方法。基本上，在某种意义上，这个想法是将 Voronoi 图视为具有不同权重的功率图的极限，这些点在不同速度下趋于 0，并考虑泰勒展开中的第一个非零系数如此参数化的谓词。

效率注意事项：

要检测可以轻松/快速确定答案的情况，您可以使用 [3] 中建议的算术过滤器（这对性能有巨大影响）。

更多参考资料（我自己的东西）

所有这些算法都在我的地理库 [4] 中实现，请参阅我的相关出版物 [5]。

其它你可能感兴趣的问题
上一篇计算奇异矩阵的零空间的任何元素 下一篇Fortran 中的半精度