实施Bowyer-Watson算法进行Delaunay三角剖分 [英] Implementing Bowyer-Watson algorithm for delaunay triangulation

问题描述

我正在尝试实现以下Bowyer-Watson算法以实现Delaunay三角剖分。

I am trying to implement the following Bowyer-Watson algorithm to implement Delaunay Triangulation.

function BowyerWatson (pointList)
  // pointList is a set of coordinates defining the points to be triangulated
  triangulation := empty triangle mesh data structure
  add super-triangle to triangulation // must be large enough to completely contain all the points in pointList
  for each point in pointList do // add all the points one at a time to the triangulation
     badTriangles := empty set
     for each triangle in triangulation do // first find all the triangles that are no longer valid due to the insertion
        if point is inside circumcircle of triangle
           add triangle to badTriangles
     polygon := empty set
     for each triangle in badTriangles do // find the boundary of the polygonal hole
        for each edge in triangle do
           if edge is not shared by any other triangles in badTriangles
              add edge to polygon
     for each triangle in badTriangles do // remove them from the data structure
        remove triangle from triangulation
     for each edge in polygon do // re-triangulate the polygonal hole
        newTri := form a triangle from edge to point
        add newTri to triangulation
  for each triangle in triangulation // done inserting points, now clean up
     if triangle contains a vertex from original super-triangle
        remove triangle from triangulation
  return triangulation

算法采用O（N log N）个运算对所要求的N个点进行三角剖分。但是有什么方法可以根据上述算法进行计算吗？我的意思是上述算法的哪一部分需要对数N次，导致n点为（N log N）个？如Wikipedia所述，存在特殊的简并情况，其上升到O（N2）。这种退化的情况是什么意思？

The algorithm takes O(N log N) operations to triangulate N points as claimed. But is there any way to calculate it from the above algorithm? I mean which part of the above algorithm takes log N times, which results in (N log N) for n points? special degenerate cases exist where this goes up to O(N2) as written in wikipedia. What is the meaning of this degenerate case?

推荐答案

也许回答有点晚了，但对某人可能有用其他。

Maybe it is a bit late to answer, but it might be useful to someone else.

Delaunay三角剖分具有外接圆属性，因此Delaunay三角剖分的任何点都不能位于任何三角形的外接圆之内。 Bowyer-Watson算法添加了一个不验证此属性的点。可以证明，外接圆的所有包含新点的三角形都是连续的。

A Delaunay triangulation have a circumcircle property, hence no point of the Delaunay triangulation can lie within the circumscribed circle of any triangle. The Bowyer-Watson algorithm add a point that does not verify this property. It can be shown that all triangles which circumscribed circle contain the new point are contiguous.

要获得理论上的NlogN，必须使用连续的事实。 （我使用连通性表）

To obtain the theoretical NlogN you must use the contiguous fact. (I use a connectivity table)

=>您需要在三角测量中搜索不尊重circumcirle属性的第一个三角形（complex log（N））

=> You need to search for a first triangle in your triangulation where the circumcirle property is not respected( complexity log(N) )

=>拥有后，删除连续的三角形（使用连接表）（与节点总数无关）

=> Once you have it, delete contigued triangles (using connectivity table) (independent of total number of nodes)

=>建立新的三角形（并更新表）（与节点总数无关）

=> Build new triangles (and update the table) (independent of total number of nodes)

对于每个节点，您需要进行N次操作。这导致理论上的Nlog（N）复杂性。

And you need to do it N times, for each nodes. This result in a theoretical Nlog(N) complexity.

维基百科上给出的算法看起来像是一个N大小的循环。因此，它应该自动为您提供N ^ 2的复杂度。

The algorithm given on wikipedia looks like a loop of loop of N size. Hence, it should automatically gave you a N^2 complexity.

如Ripi2所说，这种复杂性应该是最坏的情况，因为所有元素都被删除并且没有可用的连通性。在这种情况下，您只能选择搜索所有三角形。有关更多信息，请参见 https://doi.org/10.1006/jcph.1993.1097

This complexity should be the worst case scenario were all elements are deleted and no connectivity is available, as said Ripi2. In such case, you would have no choice but to search in all triangles. See https://doi.org/10.1006/jcph.1993.1097 for more informations

======================================= ====================================

===========================================================================

您需要找到一个初始的三角形，其中的点P为（因此将要校正的三角形）：

You need to found a initial triangle where the point P is ( hence it is a triangle to be remeshed):

选择三角剖分的三角形T（如果可能）接近您的观点。有关详情，请参见下文。
计算G，T的重心。我们表示t1，t2，t3三角形T的边缘。L1 L2和L3是由t1，t2和t3边缘（邻接）链接到T的三角形

Choose a triangle T of your triangulation (if possible close to your point. See below for more). Compute G, barycenter of T. We denote t1,t2,t3 the edges of triangle T. L1 L2 and L3 are the triangles linked to T by edges t1, t2 and t3 (adjacency)

如果[GP]越过t1，t2或t3，分别定义T = L1，L2，L3
=>如果没有，则用新的T
循环：
=>您已经找到了包含P

if [GP] cross t1, t2 or t3, define T=L1,L2,L3 respectively => Loop with new T if not : => You have found the triangle containing P

的三角形，也可以使用初始的粗糙正则细分为T选择一个良好的初始猜测，并存储你的三角形。这类似于下面的Jwezorek的想法1，但成本可能更低：

It is also possible to choose a "good initial guess" for T, using a initial coarse regular subdivision, and storing nodes of your triangles. This is similar to the idea 1 of Jwezorek below, but probably cost less:

由于您已经在所有要点周围放置了一个好的框，因此可以创建多维框细分为对数（N）。我们假定您在该细分框中具有Delaunay三角剖分的所有节点。当您搜索靠近新点P的T时，请在细分框中插入P，然后在其周围进行本地搜索。

Because you already have a good "box" around all your points, you can create a multidimensional box subdivided log(N)-th time. We will supposed that you have all the nodes of your Delaunay triangulation inside that subdivided box. When you search for a T close to the new point P, insert P in your subdivided box, and then locally search around it. Using one of the first node you found, use your connectiviy table to get a first good triangle T.

对于确实需要更多信息的人，我确实建议这本书，并使用找到的第一个节点中的一个，获取第一个好三角形T。有时间阅读：
Delaunay三角剖分和网格，Paul-Louis George，Houman Borouchaki。
由于Jwezorek问题而编辑的答案

I do recommand that book, for those who wants more infos, and have time for reading: "Delaunay triangulation and meshing, Paul-Louis George, Houman Borouchaki." Edited answer due to Jwezorek questions

这篇关于实施Bowyer-Watson算法进行Delaunay三角剖分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！