Bowyer-Watson算法：如何填补通过删除具有超级三角形顶点的三角形而留下的“空洞”

Question

Bowyer-Watson算法：如何填补通过删除具有超级三角形顶点的三角形而留下的“空洞”

11

我正在实现Bowyer-Watson算法，该算法的介绍在Wikipedia上。在我的实现中，一切都按照我的预期工作，直到伪代码的最后一部分：

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单元格都涂有不同的颜色，以便更容易发现问题。

此图显示了在执行上述伪代码步骤之前三角剖分的状态。请注意，两个超级三角形的顶点位于图像的右侧和底部之外。

before super triangle removal

这张图片展示了在没有进一步考虑的情况下，移除包含超级三角形顶点的任何三角形之后的步骤：

after super triangle removal

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

如何用伪代码表达这种边缘情况，以便我可以检查并解决它？我希望避免一些可怕的“尝试每个与超级三角形顶点共享三角形的站点组合以获得有效外接圆”的循环。

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

编辑

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

我认为这意味着在浮点数限制的情况下，我的初始问题仍然存在。有没有一种便宜的方法来保证Bowyer-Watson算法生成有效的三角剖分？

- sadakatsu

你能详细说明为什么应该有一个三角形，但是缺少了一个蓝色的站点吗？我错过了什么吗？ - Micromega

1

我遇到了完全相同的问题。我很惊讶在BW算法中存在如此大的缺陷。我唯一看到的解决方案是在最后运行凸包算法，但这有点违背初衷... - Axel

你找到解决方案了吗？我也有同样的问题。 - Somnium

1

@Axel 凸包并不总是有用的。可能存在未填充区域，其中不仅包含三角形，还包括需要三角剖分的更大的多边形。我们可以尝试对它们进行递归地运行 BW，但我担心它会永远运行下去。 - Somnium

1

@Somnium 我已经好几个月没接触这个问题了。我唯一能想到的保证你的超级圆完美的方法是做一个类似O(N^3)的遍历，收集每一个可能圆心的外接圆，然后建立你的超级三角形来确保它包含这些点。这些结果将是完全独立的，因此可以并行计算它们。这会破坏O(N^2)的运行时间，并增加存储要求（至少对于这部分）为O(N^3)。所以...如果你有实时限制，请尝试一个更大的超级三角形 : / - sadakatsu

2个回答

-1

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

- Micromega

2

-1. 这并没有解决问题。如果您查看我的第一张图片，您会发现算法生成的最上面的外心在超级三角形之外。无论超级三角形/顶点集合组合是否会产生此错误，都可能出现这种情况。 - sadakatsu

我花了一些时间才理解你的问题。很抱歉，我从未遇到过这样复杂的点集。 - Micromega

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Macinho · Accepted Answer

当我在实现Bowyer-Watson算法时，遇到了同样的问题，该算法在此处描述：http://paulbourke.net/papers/triangulate/。我在互联网上找不到任何有用的信息，甚至向我的大学提出了问题，但没有结果。过了一段时间，我想出了一个解决方案。

我发现为了消除这个问题，边界三角形的顶点理论上应该位于无限远处，但这是不切实际的。那么如果三角形有一个或两个顶点在无穷远处，三角形的外接圆会是什么样子呢？它只是通过其他点的直线。因此，测试点是否位于三角形外接圆中变成了测试点是否在直线的左侧或右侧。

算法如下：

1. 检查三角形的任意一个顶点是否在无穷远处。换句话说：检查三角形是否与边界三角形共享某些顶点。 2. 如果三角形共享所有三个顶点，则显而易见。 3. 如果它们没有共享任何顶点，则采用传统方法-检查点到外接圆心的距离是否小于外接圆半径。 4. 如果它们共享一个顶点，则检查该点是否在由其他两个顶点定义的直线的左侧/右侧。一个顶点在无限远处 5. 如果它们共享两个顶点，则检查该点是否在由这两个顶点定义的直线的左侧/右侧，但是要移动到第三个点。换句话说：您只需要取共享顶点之间的线段的斜率向量，并将其移位，以使该线通过第三个点。两个顶点在无限远处测试点是否位于直线的左侧或右侧取决于您的三角形绕序。