algorithm - Bowyer-Watson 算法 : how to fill "holes" left by removing triangles with super triangle vertices

Question

我正在实现 Wikipedia 中介绍的 Bowyer-Watson 算法.在我的实现中，一切都如我所料，直到伪代码的最后一部分:

for each triangle in triangulation // done inserting points, now clean up
     if triangle contains a vertex from original super-triangle
        remove triangle from triangulation

如果我按字面意思遵循这里的伪代码，我最终可能会在我的 Delaunay 三角剖分中缺少三角形。

例如，请考虑以下图片。我正在三角测量的站点呈现为蓝色圆圈。三角形用黑线渲染(不包括图像边界)并连接站点或边界/超三角形顶点。外接圆用灰色呈现，它们的中心用红色圆圈呈现。每个 Voronoi 单元都涂有不同的颜色，以(希望)使问题更加明显。

此图显示了在执行上述伪代码中列出的步骤之前三角测量的状态。请注意，超三角形的两个顶点超出了图像的右侧和底部。

此图显示了在没有任何进一步考虑的情况下删除任何包含超三角形顶点的三角形后的步骤:

顶部的三个顶点应该有一个新的三角形，外接圆心位于绿色/棕色单元格的交点处。问题在于“之前”图像中显示的角顶点位于该外接圆内，因此算法的常规处理从未生成该三角形。

我如何用伪代码表达这种边缘情况，以便我可以检查并解决它？我想避免一些可怕的“尝试所有共享三角形和 super 三角形顶点的站点组合”对于有效的外接圆"循环。

几年前我阅读了 Bowyer 和 Watson 的论文，如有必要，我会再次阅读它们以获得我的答案。我希望 (1) 其他人可能有可用的答案，并且 (2) 如果我再次遇到这个问题，我可以使用 Stack Overflow 查找答案。

---

编辑

所以我找到了一个相对便宜但不完美的解决方法。我的超三角形以编程方式确定，以围绕站点的边界框而不与其边相交。这个想法是由 Java 的各种令人沮丧的问题引起的，考虑到我计算的一些外心坐标或坐标之间的距离是无限的。这种谨慎导致我将 super 三角形做得非常小，以至于它的顶点有时会落在有效三角形的外心内。增加 super 三角形的大小使问题似乎消失了。然而，凸包上的三角形可能非常钝，以至于其中一个顶点仍可能落在有效的外接圆内。

我认为这意味着我最初的问题在面对 float 限制时仍然有效。有没有一种廉价的方法来保证 Bowyer-Watson 算法生成有效的三角剖分？

Answer 1

我在实现此处描述的 Bowyer-Watson 算法时遇到了同样的问题:http://paulbourke.net/papers/triangulate/ .我在互联网上找不到任何有用的东西，甚至在我的大学问过，但没有结果。过了一会儿，我想出了一个解决方案。我开始发现要使问题消失，理想情况下边界三角形的顶点应位于无穷远，这是不切实际的。那么如果三角形有一个或两个顶点在无穷远处，三角形的外接圆是什么样子的呢？它只是穿过其他点的线。因此，测试点是否位于三角形外接圆内变为测试点是否位于线的左侧或右侧。

算法看起来像这样:

1. 检查是否有任何三角形顶点位于无穷远。换句话说:检查三角形是否与边界三角形共享一些顶点。

2. 如果它共享所有三个顶点:微不足道。

3. 如果它共享零个顶点:经典方法 - 检查点到外接圆心的距离是否小于外接半径。

4. 如果它共享一个顶点:检查点是否位于由其他两个顶点定义的线的左侧/右侧。 one vertex in infinity

5. 如果它共享两个顶点:检查点是否位于由这两个顶点定义的线的左侧/右侧但移动到第三个点。换句话说:您仅从这些共享顶点之间的直线中获取斜率矢量并移动它，以便该直线穿过第三点。 two vertices in infinity

测试点是在线的左侧还是右侧取决于您的三角形缠绕顺序。