Bowyer-Watson算法：如何用超三角形顶点去除三角形来填充“孔”

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单元每个都涂上不同的颜色（希望）会使问题更加明显。

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

此图像显示去除包含超级三角形顶点不经任何进一步的考虑任何三角形之后的步骤：

顶部三个顶点应该有一个外心在一个新的三角形绿色/褐色细胞相遇的地方。问题在于，“之前”图像中显示的角点在该外接圆内，因此算法的常规处理从未生成该三角形。

如何以伪代码表示此边缘案例，以便我可以检查并解决它？我想避免一些可怕的“尝试每个组合的网站共享一个三角形的超级三角形顶点有效circumcircle”循环。

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

---

编辑

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

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

Answer 1

看来你有解决你的问题的方法，但是也可以检查三角形的外接中心是否在超级角之外。您可以使用多边形测试。也许它可以保证没有缺失的三角形。

Answer 2

我在实现这里描述的Bowyer-Watson算法时遇到了同样的问题：http://paulbourke.net/papers/triangulate/。我在互联网上找不到任何有用的东西，甚至在我的大学里询问，但没有结果。过了一段时间，我想出了一个解决方案。 我从发现问题消失开始，边界三角形的顶点应该理想地位于无穷远处，这是不实际的。那么如果三角形在无穷远处有一个或两个顶点，那么三角形外接圆的外观是什么？这只是通过其他要点。因此，如果点位于三角形的外接环上，则测试点位于左边还是右边。

算法则是这样的：

1. 检查是否有三角形的顶点位于在无穷远处。换句话说：检查三角形是否与边界三角形共享某些顶点。

2. 如果它共享所有三个顶点：平凡。

3. 如果它共享零顶点：经典方法 - 检查点与外部中心的距离是否短于环形半径。

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

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

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