Where can I find a c/c++ implementation of the minimum bound box algorithm?

I'm looking for a free implementation that finds the minimum bounding box (MBB - the box around a cloud of 3D points with the smallest volume). It should be written in either C or C++.

An algorithm to do this was published by Joseph O'Rourke and is cubic in time. I'd also be content wi开发者_如何学JAVAth an approximate MBB genered for instance by the algorithms proposed by Gill Barequet, and Sariel Har-Peled. Can anyone point me to an implementation that is free software?

See http://valis.cs.uiuc.edu/~sariel/research/papers/00/diameter/diam_prog.html which has full code of the Barequet and Har-Peled algorithms.

There is a new library ApproxMVBB in C++ online which computes an approximation for the minimum volume bounding box. It released under GPL Version 3.0 Licences, and written by me.

If you have time look at: http://gabyx.github.io/ApproxMVBB/

The library is C++11 compatible and only needs Eigen http://eigen.tuxfamily.org. Tests show that an approximation for 140Million points in 3D can be computed in reasonable time (arround 0.5-2seconds) depending on your settings for the approximation.

CGal does nearly what you want, and is GLP/QPL. Check out this page. It looks like you'll have to do a bit of fiddling to use their lower library functions to make a 3D rectangular case if bounding spheres aren't what you want, but for the purposes of speeding up collision detection, bounding spheres should be fine.