Bowyer-Watson算法:如何通过删除具有超三角形顶点的三角形来填充"孔"

Question

我正在实现维基百科上提供的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细胞每个都涂有不同的颜色(希望)使问题更加明显.

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

此图像显示删除任何包含超级三角形顶点的三角形后的步骤,无需进一步考虑:

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

如何在伪代码中表达这个边缘情况,以便检查并解决它？我想避免一些可怕的"尝试与超级三角形顶点共享一个三角形的网站的每个组合以获得有效的外接圆"循环.

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

---

编辑

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

我认为这意味着我的初始问题在浮点数限制面前仍然有效.有没有一种廉价的方法来保证Bowyer-Watson算法产生有效的三角测量？

Answer 1

在实现此处描述的Bowyer-Watson算法时，我遇到了相同的问题：http : //paulbourke.net/papers/triangulate/。我在互联网上找不到任何有帮助的东西，甚至在我的大学问过，但都没有结果。一段时间后，我想出了一个解决方案。我首先发现，要使问题消失，包围三角形的顶点在理想情况下应位于无穷大处，这是不切实际的。那么，如果三角形在无限远处有一个或两个顶点，那么三角形外接圆的外观如何？它只是穿过其他点的线。因此，测试点是否位于三角形外接圆上会更改为测试点是否位于直线的左侧或右侧。

然后，算法如下所示：

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

2. 如果要共享所有三个顶点：琐碎的。

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

4. 如果共享一个顶点：检查点是否位于其他两个顶点定义的线的左侧/右侧。一个顶点无限

5. 如果共享两个顶点：检查点是否位于这两个顶点定义的线的左/右，但是否移至第三个点。换句话说：您仅从这些共享顶点之间的直线中获取斜率矢量，然后对其进行移位，以使该直线穿过第三点。无穷大的两个顶点

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

Answer 2

看来您有解决问题的方法，但也可以检查三角形的外心是否在超三角形之外。您可以使用多边形内的点测试。或许可以保证不存在缺失的三角形。