jeffe at cs.uiuc.edu
Tue Sep 30 11:18:51 PDT 2003
Nash Aragam wrote:
> Can somebody send me a link for a quick and easy code sample/algorithm
> for computing OBB on a cloud of 3D points? Thanks much,
I assume by "OBB" you mean "oriented bounding box", ie, the
minimum-volume box, in any orientation, that contains all the points.
For the fastest known exact algorithm, which runs in O(n^3) time, see
Joe O'Rourke's paper "Finding Minimal Enclosing Boxes" (International
Journal of Computer and Information Sciences 14:183-199, 1985). Sorry,
it's not online, but it's worth the trip to the library.
Here's code to quickly compute a provably-good approximation:
For a description of the algorithm, see
Sariel and Gill's paper also includes a description of several
commonly-used heuristics, none of which is guaranteed to be very good,
although most of them are decent in practice.
The compgeom mailing lists: see
or send mail to compgeom-request at research.bell-labs.com with the line:
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.
More information about the Compgeom-announce