我在哪裏可以找到最小邊界框算法的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百萬點的近似值。