CODEWITHSUNDEEP
cgeometryimplementation
con-f-use
con-f-use

Reputation: 4028

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 with 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?

Upvotes: 3

Views: 3386

Answers (3)

Nicholas Wilson
Nicholas Wilson

Reputation: 9685

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.

Upvotes: 0

Gabriel
Gabriel

Reputation: 9432

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.

Upvotes: 1

Gill Barequet
Gill Barequet

Reputation: 11

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.

Upvotes: 1

Related Questions