我在哪里可以找到最小边界框算法的c/C++实现？

Question

我在寻找一个免费的实现方式，它可以找到围绕着具有最小音量的三维点云的盒子minimum bounding box（MBB）。它应该用C或C++编写。

这样做的算法由Joseph O'Rourke发布，并且时间上是三次方。我也会满足于由Gill Barequet和Sariel Har-Peled提出的算法产生的近似MBB。任何人都可以指出我是一个自由软件的实现吗？

Answer 1

CGal几乎是你想要的，并且是GLP/QPL。检出this page。它看起来像你必须做一些摆弄，如果边界球体不是你想要的，使用他们较低的库函数来制作一个三维矩形的情况，但为了加速碰撞检测的目的，边界球体应该没问题。

Answer 2

请参阅http://valis.cs.uiuc.edu/~sariel/research/papers/00/diameter/diam_prog.html 其中有完整的Barequet和Har-Peled算法代码。

Answer 3

有一个新的库在C++在线ApproxMVBB其计算的近似体积最小边界框。它在GPL 3.0版许可下发布，并由我撰写。

如果你有时间看一下：http://gabyx.github.io/ApproxMVBB/

库是C++ 11兼容，只需要征http://eigen.tuxfamily.org。 测试表明，根据您对近似值的设置，可以在合理的时间（大约0.5-2秒）内计算3D中的140百万点的近似值。