logo标签列表

实现 Bowyer-Watson 算法来进行 Delaunay 三角剖分

algorithmgeometrytime-complexitycomputational-geometry
3

我正在尝试实现以下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

如前所述，该算法声称三角化N个点需要O（NlogN）次操作。但是是否有任何方式可以从上述算法中计算它呢？我的意思是上述算法的哪一部分需要log N次，这导致n个点的结果为（N log N）？维基百科写道，存在特殊退化情况，其中这个时间复杂度会增加到O（N2）。那么这个退化案例的意义是什么？

5个回答
6
问题中的伪代码，即维基百科文章中描述的Bowyer / Watson算法是O(n^2)。 文章确实声明了这一点。 维基百科文章不够清晰 - 我认为实际上是错误的 - 关于如何使算法O(n log n)，这并不完全是微不足道的。
当前的维基百科文章如下所示：
效率可以通过多种方式进行改进。 例如，可以使用三角形连接来定位包含新点在其外接圆中的三角形，而无需检查所有三角形 - 这样做可以将时间复杂度降低到O(n log n)。
我争辩说仅靠“三角形连接”就可以实现O(n log n)的行为。
在算法的每个迭代中，需要做的是给定一个新点P，找到引入P到现有三角剖分中会创建的“坏三角形”，即包含P在其外接圆中的三角形。维基百科文章中提到的“三角形连通性”属性是这些坏三角形将是三角剖分邻接图中的一个连通组件，因此，如果您恰好知道其中一个坏三角形，则可以通过执行仅限于相邻坏三角形的图遍历轻松地找到其他坏三角形。但是，前提是您有一个起点的坏三角形。显然的选择是包含P的三角形。
O(n log n)时间复杂度声明的主要来源，“通过Delaunay三角剖分和Bowyer-Watson算法实现高效的非结构化网格生成”，S. Rebay, 1991，解释了以下情况：（重点强调）
算法效率取决于每次插入点时查找要删除的三角形的速度，而对每个三角形的相邻三角形的了解可以使这一过程更加容易。实际上，由于要删除的所有三角形总是连续的，因此可以使用在相邻三角形之间进行树搜索来查找所有其他要删除的三角形，第一个三角形之后。在典型情况下，每个点插入时要删除的三角形数量不取决于所有现有三角形的数量。因此，如果可用有关相邻三角形的信息并且使用O(log N)多维搜索来查找要删除的第一个三角形，则该算法可以在O(N log N)次操作中计算出一组N个点的Delaunay三角剖分。然而，在特殊情况下，每个点插入时要删除的三角形数量可能非常大。在最坏的情况下，即每个点插入时都必须删除所有现有三角形，Bowyer-Watson算法的操作次数会降至O(N^2)。
简言之，如果您维护三角形邻接图并且有一种方法可以在O（log n）时间内找到包含任意点的三角形，则Bowyer-Watson算法的时间复杂度为O（n log n），因为典型三角剖分中坏三角形组件中的三角形数量非常小，可以认为它比某个小常数更低。
维基百科，Rebay等没有讨论使算法O（n log n）的“多维搜索”，但我可以提供三个建议，来自文献和其他来源：

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

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

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

我认为这个主张始于[Green Sibson 1976]（即在Watson和Bowyer将其推广之前的2D情况）。他们猜测，通过类似于“Shell排序方法”的适应，“在两种情况下都可以期望将其降至O(log N)”。 - Lars Quentin
有趣。我会去看看的。 - jwezorek
2
也许现在回答有点晚了，但对其他人可能有用。
Delaunay三角剖分具有外接圆属性，因此任何一个三角形的外接圆内不可能存在任何一个点。Bowyer-Watson算法添加了一个不符合此属性的点。可以证明，所有外接圆包含新点的三角形是连续的。
为了获得理论上的NlogN，必须使用连续性这一事实。（我使用连接表）
=> 您需要在三角剖分中搜索第一个不满足外接圆属性的三角形（复杂度log(N)）
=> 一旦找到它，删除相邻的三角形（使用连接表）（与节点总数无关）
=> 构建新的三角形（并更新表）（与节点总数无关）
您需要这样做N次，对于每个节点。这导致理论上的Nlog(N)复杂度。
维基百科上给出的算法看起来像一个大小为N的循环嵌套。因此，它应该自动给出一个N^2复杂度。
这个复杂度应该是最坏情况，即所有元素都被删除且没有可用的连接，正如Ripi2所说。在这种情况下，你只能在所有三角形中搜索。更多信息请参见https://doi.org/10.1006/jcph.1993.1097。

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

您需要找到一个初始三角形，其中点P位于其中（因此它是要重新网格化的三角形）：
选择您三角剖分中的一个三角形T（如果可能靠近您的点。有关更多信息，请参见下文）。 计算G，T的重心。 我们将t1，t2，t3表示为三角形T的边缘。 L1，L2和L3是通过边缘t1，t2和t3与T相连的三角形（邻接性）
如果[GP]穿过t1，t2或t3，则定义T = L1，L2，L3 => 使用新的T循环 如果没有： => 您已经找到包含P的三角形
还可以选择一个“好的初始猜测”来选择T，使用初始粗略正则细分，并存储三角形的节点。 这类似于Jwezorek以下想法1，但成本可能较低：
因为您已经有一个很好的“盒子”围绕着所有的点，所以您可以创建一个多维盒子，将它分成 log(N) 次。我们假设您的 Delaunay 三角剖分的所有节点都在这个细分的盒子内。当您搜索一个接近新点 P 的 T 时，在您的细分盒子中插入 P，然后在其周围进行局部搜索。使用您找到的第一个节点之一，使用您的连通性表格来获取第一个好的三角形 T。
我推荐那本书，对于那些想要更多信息并有时间阅读的人： “Delaunay triangulation and meshing, Paul-Louis George, Houman Borouchaki。” 由于 Jwezorek 的问题编辑答案
“在三角剖分中搜索第一个不满足外接圆性质的三角形”如何是O(log n)的？当您向三角剖分中添加一个点时，该点将位于三角剖分中的某个现有三角形S内。一旦您拥有了该三角形S，事实上，坏三角形将成为邻接图中连续的连接组件，因此可以通过从S开始进行图遍历来轻松找到它们，但是如何有效地找到S呢？我看不出如何在不维护某种2D范围搜索数据结构的情况下高效地找到第一个三角形。 - jwezorek
0
0
这里描述的算法是一种天真的增量Delaunay三角剖分。复杂度显然为O(N^2)。"对于点列表中的每个点，都要将所有点逐个添加到三角剖分中"，这个主循环是O(N)，而"对于三角形剖分中的每个三角形，首先找到由于插入而不再有效的所有三角形"，这个内部循环是O(N)。
在所有情况下，这个算法的复杂度都是O(N^2)。然而，还有其他算法可以给出O(N * Log(N))或更好的复杂度。请参见这里的“分治法”：https://en.wikipedia.org/wiki/Delaunay_triangulation。
0

该算法有两个主要步骤：

  1. 对于三角剖分中的每个三角形，如果点在外接圆内，则...
  2. 对于badTriangles中的每个三角形，删除并添加新的三角形...

第一步是一种不好的方法。有更好的方法来定位新添加的点所在的三角形。搜索“从旧三角形向新点行走”。

第二步可能涉及到所有三角形，这是一个退化情况，其中所有点都位于一个共同的大圆上。

如果我在随机化后取输入点，复杂度会变成O(nlogn)吗？@Ripi2 - user7064921
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接