Finding Optimal Bouding Boxes for Objects?

[Please feel free to ignore this post, actual useful information is in the next post]

This is just off the top of my head.

Take the convex hull of the point set. Then the optimal bounding box will have an edge parallel to one of the edges on the hull. Try each edge, and build the box using the convex hull (you can build the bounding box using a convex hull very quickly, given your first edge direction, you just need to find the extents of the projections of all of the points onto that line, and that defines your edges) and take the minimum one.

This is n^2 log n, so it's not super quick, but it should be relatively efficient. There are probably more efficient algorithms out there though.

[edited by - premandrake on May 2, 2004 9:35:12 PM]

And wow.. I''ve just actually thought about this for two seconds and realized it doesn''t even come close to working.

Anyhow, there is a relatively quick method that uses matrices and eigenvectors here.

And a good link to a discussion on this is here (at gamedev.net).