5

I'm looking for an algorithm that finds the smallest box enclosing a polyhedron.

My idea is as follows: find the largest side, and move the solid so that side aligns with the x axis. Find the next largest side that meets this side, and align it as close as possible to the z axis, while leaving the other side on x. Then, calculate the greatest differences in x, y and z. Use those dimensions to create the surrounding shape and then shift the box back to the object's original location.

Is there a more efficient strategy for this? Does my idea overlook some corner cases?

Edit: For now assume the object to be bounded is convex. Though, an answer for the general case would also be welcome.

Charles Taylor
  • 686
  • 6
  • 23
  • 1
    Don't think there's enough information here. For example, are the polyhedra restricted to convex figures, or can they be arbitrarily complex and twisty? Does the bounding box need to be axis-aligned, or can it be rotated? I'm not entirely convinced that, in the general case, a minimal bounding box will have one face coplanar with a face of the polyhedron, although it does seem likely... – twalberg Jun 11 '15 at 18:38
  • Let's assume for now that the object to be bounded is convex. – Charles Taylor Jun 11 '15 at 18:50
  • what is "smallest"? least voluminous? – Steve Cox Jun 11 '15 at 19:05

1 Answers1

1

The problem of finding minimal (volume) boxes for convex polyhedrons has been studied by O'Rourke, who proposes an O(n^3) algorithm:

J. O-Rourke. Finding minimal enclosing boxes. International Journal of Computer & Information Sciences, 1985, 14(3), p.183.

O'Rourke's algorithm finds the minimal enclosing box for a set of points in R^3 -- but this is clearly equivalent to finding the enclosing box for the polyhedron formed as the convex hull of the underlying point-set.

Contrary to what one might expect (and the approach you've described, if I've understood you correctly), the minimal box is not necessarily oriented such that a face of the polyhedron is coplanar with a face of the box! Note the animation shown here for a simple tetrahedron.

If you're happy with the idea of simply find an enclosing box that's relatively small, rather than the smallest enclosing box, there may be other (faster) heuristics that can be applied...

Darren Engwirda
  • 6,915
  • 4
  • 26
  • 42