我正在实现Bowyer-Watson算法,该算法的介绍在Wikipedia上。在我的实现中,一切都按照我的预期工作,直到伪代码的最后一部分:
如果我按照这里的伪代码字面意思执行,我的Delaunay三角剖分可能会缺少一些三角形。
例如,请看下面的图片。 我正在三角化的站点以蓝色圆圈呈现。 三角形用黑线呈现(不包括图像边框),连接站点或边界/超级三角形顶点。 用灰色渲染外接圆,其中心用红色圆圈呈现。 Voronoi单元格都涂有不同的颜色,以便更容易发现问题。
此图显示了在执行上述伪代码步骤之前三角剖分的状态。 请注意,两个超级三角形的顶点位于图像的右侧和底部之外。
如何用伪代码表达这种边缘情况,以便我可以检查并解决它?我希望避免一些可怕的“尝试每个与超级三角形顶点共享三角形的站点组合以获得有效外接圆”的循环。
我几年前读了Bowyer和Watson的论文,如果必要的话,我会再次阅读它们以获得答案。我希望(1)其他人可能已经得到了答案,(2)如果我再次遇到这个问题,我可以使用Stack Overflow查找答案。
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算法生成有效的三角剖分?