algorithm - 为 delaunay 三角剖分实现 Bowyer-Watson 算法

Question

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

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 个点进行三角测量，如所声称的。但是有没有办法从上面的算法中计算出来呢？我的意思是上述算法的哪一部分需要 log N 次，这会导致 (N log N) 获得 n 个点？存在特殊的退化情况，如维基百科中所写，这会达到 O(N2)。这种退化的情况是什么意思？

Answer 1

问题中的伪代码，the Wikipedia article 中描述的 Bowyer/Watson 算法, 是 O(n^2)。文章确实说明了这一点。维基百科的文章不太清楚 - 我认为实际上是错误的 - 关于需要做什么才能使算法 O(n log n)，这样做并非完全无关紧要。

当前的维基百科文章说如下

Efficiency can be improved in a number of ways. For example, the triangle connectivity can be used to locate the triangles which contain the new point in their circumcircle, without having to check all of the triangles - by doing so we can decrease time complexity to O(n log n).

我认为单独使用“三角形连接”可以实现 O(n log n) 行为。

在算法的每次迭代中需要做一个新点 P 找到将 P 引入现有三角剖分将创建的“坏三角形”，即在其外接圆中包含 P 的三角形。维基百科文章中提到的“三角形连通性”属性是，这些坏三角形将是三角剖分邻接图中的一个连通分量，因此如果您碰巧知道一个这样的坏三角形，您可以通过执行图遍历轻松找到其他三角形仅限于相邻的坏三角形。然而，如果你有一个坏的三角形开始。一个明显的选择是包含 P 的三角形。

O(n log n) 时间复杂度声明的主要来源，“Efficient Unstructured Mesh Generation by Means of Delaunay Triangulation and Bowyer-Watson Algorithm”，S. Rebay，1991，对这种情况进行了如下解释:(强调我的)

The algorithm efficiency depends on how quickly the search for triangles to be deleted at each point insertion is performed and this is made much easier by knowledge of the neighboring triangles to each triangle. In fact, since all the triangles to be deleted are always contiguous, a tree search among neighboring triangles can be used to find all the other triangles to be deleted after the first one. In the typical case, the number of triangles to be deleted at each point insertion does not depend on the number of all existing triangles. As a consequence, if the information pertaining to the the neighboring triangles is available and an O(log N) multidimensional search for the first triangle to be deleted is employed, the algorithm can compute the Delaunay triangulation of a set of N points in O(N log N) operations. In special cases, however, the number of triangles to be deleted at each point insertion can be very large. In the worst possible situation, when all existing triangles have to be deleted at each point insertion, the operation count of the Bowyer-Watson algorithm degrades to O(N^2).

换句话说，如果您维护三角形邻接图并且您有某种方法可以在 O(log n) 时间内找到包含任意点的三角形，那么 Bowyer-Watson 算法是 O(n log n) 因为对于典型的三角剖分来说，坏三角形组件中的三角形数量非常少，我们可以认为它低于某个小常数。

Wikipedia、Rebay 等不讨论制作算法 O(n log n) 所需的“多维搜索”，但我可以提供三个建议，来自文献和其他方面:

1. 存储二维范围内所有三角形的边界矩形您选择的搜索数据结构。例如，R 树或 R* 树。

2. 使用 Delaunay 三角剖分本身的层次结构。维护三角剖分的历史，三角形“级别”的树。我相信这就是 CGAL 的 Delaunay 实现所做的。

3. 随机采样k个三角形，找到离目标最近的三角形t样本中的点，对从 t 到的邻接图执行 A* 搜索包含目标点的三角形。这可能会表现良好但不是正式的 O(log n)。