How to compute a bounding tetrahedron

Question

I'm wondering how to compute a bounding tetrahedron from a set of points so i can initialize a delaunay triangulation

My first approach was to find the bounding box to my set of points and then compute a tetrahedron going from the bounding box .

I'm searching for a robust method for doing it .

Answer 1

While it's an old question, someone may find the following approach useful nonetheless.

1. Calculate the (axis aligned) bounding box for your input point cloud.
2. From that, calculate the (axis aligned) bounding cube centered around the centroid of the bounding box (so the two are either identical or the bounding box is fully enclosed in the bounding cube).
3. Scale the bounding cube up by a factor of three about its centroid (so the scaling will not implicitly transform it in worldspace).
4. Derrive any of the regular tetrahedra embedded in the cube. That is, take the diagonals of two opposing faces of the cube, more precisely the top- and bottom-face, but such that both diagonals are orthogonal rather than colinear. The four cube vertices connected to those two diagonals are the vertices of your bounding (regular) tetrahedron.

---

The yellow cube's vertices touch the red octahedron's faces on their centroids.

The red octahedron's vertices are the centroids of the blue cube. The blue cube's edge length is three times that of the yellow cube. The red octahedron is identical in both images.

The orange octahedron's vertices are the midpoints of the yellow regular tetrahedron. The yellow tetrahedron's bounding box is the blue cube shown above.

---

---

Explanation: A cube's dual is a regular octahedron. So if we take the centroid of each cube face, we get the embedded (dual) octahedron.

This octahedron's volume equals one third of the cube's volume. As the duality works both ways, we can, for a given minimum bounding cube, imagine a regular octahedron inside which our cube is embedded itself. This bounding octahedron naturally has to be three times the size of the bounding cube.

A regular octahedron on the other hand can be neatly embedded in a regular tetrahedron, where the octahedron's vertices are the midpoints of the tetrahedron's edges.

A regular tetrahedron can be embedded in a cube such that four vertices of the cube make up for the tetrahedron's vertices and the tetrahedron's edges are all diagonals of the cube's face.

It follows we can imagine a regular octahedron which embeds our original bounding cube while itself being embedded in a regular tetrahedron (which we need), itself embedded in a larger cube. The volume of the tetrahedron is exactly one third of that of the large cube, which is where the above-mentioned scaling factor comes from.