鲍耶 - 沃森算法：如何填写＆QUOT;孔＆QUOT;通过与超三角形顶点的三角形去除左 [英] Bowyer-Watson algorithm: how to fill "holes" left by removing triangles with super triangle vertices

问题描述

我实现了鲍耶 - 沃森算法psented在维基百科<$ P $ / A>。在我的实现，一切都按我所期望的，直到的伪code中的最后一部分：

I am implementing the Bowyer-Watson algorithm as presented at Wikipedia. In my implementation, everything works as I would expect up until the last part of the pseudocode:

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

如果我按照伪code在这里从字面上看，我可以结束了在我的Delaunay三角失踪的三角形。

If I follow the pseudocode here literally, I can end up with missing triangles in my Delaunay triangulation.

作为一个例子，请考虑以下的图像。我的三角部位呈现为蓝色圆圈。三角形与黑线（不包括图像边界）渲染和连接点或边界/超三角形顶点。外接圆呈现的灰色和他们的中心与红色圆圈呈现。的Voronoi单元分别涂有不同的颜色，以（希望）使问题更明显。

As an example, please consider the images below. The sites I am triangulating are rendered as blue circles. The triangles are rendered with black lines (excluding the image borders) and connect sites or bounding/super triangle vertices. The circumcircles are rendered with gray and their centers are rendered with red circles. The Voronoi cells are each painted with a different color to (hopefully) make the problem more apparent.

此图显示了执行中的伪code以上列出的步骤前右三角的状态。需要注意的是两个超级三角形的顶点都超出了权利和图象的底部。

This image shows the state of the triangulation right before performing the steps listed in the pseudocode above. Note that two of the super triangle's vertices are beyond the right and the bottom of the image.

此图显示的步骤删除包含超级三角形顶点的三角面，没有任何进一步的考虑后：

This image shows the step after removing any triangles that contain super triangle vertices without any further considerations:

前三个顶点应该有一个新的三角形外心一处的地步，绿/褐色细胞见面。的问题是，这是图像之前中所示的角顶点是此外接圆内，因此该算法的常规处理从未产生这个三角形

The top three vertices should have a new triangle with a circumcenter at the point where the greenish/brownish cells meet. The problem is that the corner vertex that was shown in the "before" image was inside this circumcircle, so the regular processing of the algorithm never generated this triangle.

我如何EX preSS伪code本的边缘情况，所以我可以检查并解决它？我想避免一些可怕的试网站的每一个组合，共享一个三角形超级三角形顶点有效外接圆循环。

How do I express this edge case in pseudocode so I can check for and solve it? I would like to avoid some horrific "try every combination of sites that shared a triangle with a super triangle vertex for valid circumcircle" loop.

我读了鲍耶和华生的论文一对夫妇几年前，如有必要，将再次读出他们对我的回答。我希望，（1）别人可能有答案可用，（2）我可以用堆栈溢出来查找答案，如果我曾经碰到这个问题了。

I read the Bowyer and Watson papers a couple years back and will read them again for my answer if necessary. I was hoping that (1) somebody else might have the answer available and (2) I could use Stack Overflow to look the answer up if I ever run into this question again.

修改

所以，我已经找到了相对便宜，但不完美的解决方法。我的超级三角形编程决心围绕网站的边框没有相交的两侧。这个想法是由各种令人沮丧的问题与Java考虑我的一些计算外心坐标或坐标之间的距离是无限的造成的。这种谨慎使我做我的超级三角如此之小，它的顶点，有时在下跌三角形有效circumcenters。增加超级三角形的尺寸作出了这个问题似乎消失。然而，可能的是在凸船体一个三角形可以如此钝角的顶点之一仍然可能会下降内有效的外接圆

So I have found a relatively cheap but imperfect work-around. My super triangle is programmatically determined to surround the sites' bounding box without intersecting its sides. This idea was caused by all sorts of frustrating problems with Java considering some of my calculated circumcenter coordinates or distances between coordinates to be infinite. This caution led me to make my super triangle so small that its vertices sometimes fell in valid triangles' circumcenters. Increasing the size of the super triangle has made the problem seem to disappear. However, it is possible that a triangle on the convex hull can be so obtuse that one of the vertices still could fall inside a valid circumcircle.

我想这意味着我最初的问题仍然是在浮点数限制脸上有效。有没有一种廉价的方式来保证鲍耶 - 沃森算法生成一个有效的三角测量？

I think this means that my initial question is still valid in the face of floating-point number limitations. Is there a cheap way to guarantee that the Bowyer-Watson algorithm generates a valid triangulation?

推荐答案

看来你有你的问题的解决方案，但它也可以检查三角形外心是supertriangle之外。您可以使用点在多边形的测试。也许它可以保证，有没有遗漏的三角形。

It seems you have a solution for your problem but it's also possible to check if the circumcenter of the triangle is outside the supertriangle. You can use a point-in-polygon test. Maybe it can guarantee that there are not missing triangles.

这篇关于鲍耶 - 沃森算法：如何填写＆QUOT;孔＆QUOT;通过与超三角形顶点的三角形去除左的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！