Find minimum number of triangles enclosing all points in the point cloud

Question

Input

You have a points list which represents a 2D point cloud.

---

Output

You have to generate a list of triangles (should be as less as possible triangles) so the following restrictions are fulfilled:

1. Each point from the cloud should be a vertex of a triangle or be inside a triangle.

2. Triangles can be build only on the points from the original point cloud.

3. Triangles should not intersect with each other.
4. One point of the cloud can be a vertex for several triangles.
5. If triangle vertex lies on the side of another triangle we assume such triangles do not intersect.
6. If point lies on the side of triangle we assume the point is inside a triangle.

---

For example

---

Investigation

I invented the way to find a convex hull of given set of points and divide that convex hull into triangles but it is not right solution.

Any guesses how to solve it?

Answer 1

Here is my opinion.

1. Create a Delaunay Triangulation of the point cloud.
2. Do a Mesh Simplification by Half Edge Collapse.

For step 1, the boundary of the triangulation will be the convex hull. You can also use a Constrained Delaunay Triangulation (CDT) if you need to honor a non-convex boundary.

For step 2 half-edge collapse operation is going to preserve existing vertices, so no new vertices will be added. Note that in your case the collapses are not removing vertices, they are only removing edges. Before applying an edge collapse you should check that you are not introducing triangle inversions (which produce self intersection) and that no point is outside a triangle. The order of collapses matter but you can follow the usual rule that measures the "cost" of collapses in terms of introducing poor quality triangles (i.e. triangles with acute angles). So you should choose collapses that produce the most isometric triangles as possible.

Edit:

The order of collapses guide the simplification to different results. It can be guided by other criteria than minimize acute angles. I think the most empty triangles can be minimized by choosing collapses that produce triangles most filled vs triangles most empty. Still all criteria are euristics.

Answer 2

Some musings about triangles and convex hulls

Ignoring any set with 2 or less points and 3 points gives always gives 1 triangle.

• Make a convex hull.
• Select any random internal point.
  • unless all points are in hull ...

• All point in the hull must be part of an triangle as they per definition of convex hull can't be internal.

• Now we have an upper bound of triangles, namely the number of points in the hull.

• An upper bound is also number of points / 3 rounded up as you can make that many independent triangles.
• so the upper bound is the minimum of the two above
• We can also guess at the lower bound roundup(hull points / 3) as each 3 neighboring points can make a triangle and any surplus can reuse 1-2.

Now the difficult part reducing the upper bound

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.

Is this prof that no better result exist? no. If there exist a triangle that envelop all remaining points that would this be better.

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

So ... total runtime ...

Candidate O(N) AddTriangle O(N^3) recursion is limited to the current best solution U

O((N N^3)^U) -> O((N^4)^U) space is O(U N)

So reducing U before we go to brute force is essential. - Reducing R quickly should reduce recursion - so starting with bigger and hopefully more enclosing triangles would be good - any 3 points in the hull should make some good candidates - these split the remaining points in 3 parts which can be investigated independently - treat each part as a hull where its 2 base points are part of a triangle but the 3rd is not in the set. - if possible make this a BFS so we can select the most enclosing first - space migth be a problem - O(H U N) - else start with points that are a 1/3 around the hull relative to each other first.

AddTriangle really sucks performance so how many triangles can we really make

Selecting 3 out of N is

N!/(N-3)!

And we don't care about order so

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

Which is still O(N^3) for the loops, but it makes us feel better. The loops might still be faster if the permutation takes too long.

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