找到包含点云中所有点的最小三角形数量

Question

找到包含点云中所有点的最小三角形数量

algorithmmathgeometry

7

输入

你有一个点列表，表示2D点云。

输出

你需要生成一个三角形列表（应该是尽可能少的三角形），以满足以下限制：

云中的每个点都应该是三角形的一个顶点或在三角形内部。
只能在原始点云上构建三角形。
三角形不应相互交叉。
云的一个点可以是多个三角形的顶点。
如果三角形的顶点位于另一个三角形的边缘上，我们认为这些三角形不相交。
如果点位于三角形的边缘上，我们认为该点在三角形内部。

例如

原始点云和包围三角形

调查

我发明了一种方法来找到给定点集的凸包并将其分成三角形，但这不是正确的解决方案。

有什么猜测如何解决它吗？

- Mykola Kotsabiuk

3

为什么将凸包分解为三角形不是正确的解决方案？应该满足所有的标准。 - juvian

@RoryDaulton：这个例子回答了你的问题，不是吗？ - user1196549

显然，凸包的所有顶点都必须是某个三角形的顶点，因此三角形数量的一个简单下限是Ceil(H/3)。你的例子表明这个下限并不紧密。由于凸包的大小可以达到N，可能需要Ceil(N/3)个三角形。 - user1196549

2

@juvian 凸包的覆盖可能会在中间留下空隙。例如，在这个图示中，凸包可以用两个三角形的方式进行覆盖，但是所有这些方式都会错过中间的点。 - btilly

@juvian 因为有些情况下，你可以用更少的三角形覆盖所有点，或者你应该发明正确的分解方法。 - Mykola Kotsabiuk

@RoryDaulton，谢谢。我已经编辑过了。应该是最小三角形数量。 - Mykola Kotsabiuk

2个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Surt · Answer 1

关于三角形和凸包的一些思考

忽略任何只有2个或更少点的集合，3个点总是会形成1个三角形。

构建凸包。
选择任意一个内部点。
- 除非所有点都在凸包中...
凸包中的所有点必须作为三角形的一部分，因为根据凸包的定义，它们不能是内部点。
现在我们有了三角形的上限，即凸包中的点数。
上限也可以是点数/3向上取整，因为你可以制作这么多独立的三角形。
所以上限是上述两者中的最小值。
我们还可以猜测下限为凸包点数/3向上取整，因为每3个相邻点可以组成一个三角形，任何剩余的点可以重复使用1-2次。

现在困难的部分是降低上限。

walk through the inner points using them as center for all triangles.
  If any triangle is empty we can save a triangle by removing the hull edge.
  if two or more adjacent triangles are empty we will have to keep every other triangle or join the 3 points to a new triangle, as the middle point can be left out.
  note the best result.

这证明没有更好的结果吗？不是的。如果存在一个三角形，能够包含所有剩余的点，那么这将是更好的。

N = number of points
U = upper bound
L = lower bound
T = set of triangles
R = set of remaining points
A = set of all points
B = best solution

BestSolution(A)
  if A < 3 return NoSolution
  if A == 3 return A

  if not Sorted(A) // O(N)
    SortByX(A)     // O(n lg n) or radex if possible O(N)

  H = ConvexHull(A)
  noneHull = A - H
  B = HullTriangles(H, noneHull) // removing empty triangles
  U = size B

  if noneHull == 0
    return U // make triangles of 3 successive points in H and add the remaining to the last 

  if U > Roundup(N/3)
    U = Roundup(N/3)
    B = MakeIndepenTriangles(A)

  AddTriangle(empty, A)

  return // B is best solution, size B is number of triangles.

AddTriangle(T, R)
  if size T+1 >= U return // no reason to test if we just end up with another U solution
  ForEach r in R // O(N)
    ForEach p2 in A-r // O(N)
      ForEach p3 in A-r-p2 // O(N)
        t = Triangle(r, p2, p3)
        c = Candidate(t, T, R)
        if c < 0 
          return c+1 // found better solution
  return 0

Candidate(t, T, R)
  if not Overlap(t, T) // pt. 3, O(T), T < U
    left = R-t
    left -= ContainedPoints(t) // O(R) -> O(N)

    if left is empty
      u = U
      U = size T + 1
      B = T+t
      return U-u // found better solution

    return AddTriangle(T+t, left)
  return 0

所以...总运行时间...

候选O(N) AddTriangle O(N^3) 递归限制在当前最佳解U

O((N N^3)^U) -> O((N^4)^U) 空间为O(U N)

因此，在我们进行暴力搜索之前，减少U是必要的。 - 快速减少R应该会减少递归 - 因此，从更大且希望更包围三角形开始可能是好的 - 外壳中的任何3个点都应该产生一些好的候选项 - 这些将剩余的点分成3部分，可以独立地进行调查 - 将每个部分视为外壳，其中其2个基本点是三角形的一部分，但第3个不在集合中。 - 如果可能，使其成为BFS，以便我们可以首先选择最具包容性的 - 空间可能是一个问题 - O(H U N) - 否则，首先从相对于彼此的外壳周围1/3的点开始。

AddTriangle真的很影响性能，所以我们到底能做多少个三角形

从N中选择3个是

N!/(N-3)!

我们不关心顺序

N!/(3!(N-3)!)
N!/(6(N-3)!)
N (N-1) (n-2) / 6

对于循环而言，这仍然是O（N ^ 3），但这让我们感觉更好。如果排列时间太长，循环可能仍然更快。

AddTriangle(T, R)
  if size T+1 >= U return // no reason to test if we just end up with another U solution
  while t = LazySelectUnordered(3, R, A) // always select one from R first O(R (N-1)(N-2) / 6) aka O(N^3)
    c = Candidate(t, T, R)
    if c < 0 
      return c+1 // found better solution
  return 0

- Mauricio Cele Lopez Belon · Answer 2

这是我的观点。

创建点云的 Delaunay 三角剖分。
通过半边折叠进行网格简化。

对于步骤1，三角剖分的边界将是凸包。如果需要遵守非凸边界，则还可以使用约束 Delaunay 三角剖分（CDT）。

对于步骤2，半边折叠操作将保留现有顶点，因此不会添加新顶点。请注意，在您的情况下，折叠不会删除顶点，而只会删除边缘。在应用边缘折叠之前，应检查是否引入了三角形反转（产生自交）以及没有点在三角形外部。折叠的顺序很重要，但是您可以遵循通常的规则，根据引入质量差的三角形（即锐角三角形）的程度来衡量折叠的“成本”。因此，您应该选择尽可能产生等距三角形的折叠。

编辑：

折叠的顺序会将简化引导到不同的结果。它可以由其他标准指导，而不是最小化锐角。我认为可以通过选择产生最多填充三角形的折叠来最小化最空三角形。但是所有标准都是启发式的。