Где я могу найти реализацию алгоритма минимального ограниченного прямоугольника на ac / c ++?

Question

Я ищу бесплатную реализацию, которая находит минимальный ограничивающий прямоугольник ( MBB - прямоугольник вокруг облака трехмерных точек с наименьшим объемом).Он должен быть написан на C или C ++.

Алгоритм для этого был опубликован Джозефом О'Рурком и является кубическим по времени.Я также был бы доволен приблизительным MBB, сгенерированным, например, алгоритмами, предложенными Джиллом Бареке и Сариэлем Хар-Пеледом.Кто-нибудь может указать мне на реализацию, которая является свободным программным обеспечением?

Answer 1

См. http://valis.cs.uiuc.edu/~sariel/research/papers/00/diameter/diam_prog.html с полным кодом алгоритмов Бареке и Хар-Пеледа.

Answer 2

В C ++ появилась новая библиотека ApproxMVBB, которая вычисляет аппроксимацию для ограничивающей рамки минимального объема . Он выпущен по лицензии GPL версии 3.0 и написан мной.

Если у вас есть время, посмотрите на: http://gabyx.github.io/ApproxMVBB/

Библиотека совместима с C ++ 11 и требует только Eigen http://eigen.tuxfamily.org. Тесты показывают, что аппроксимация для 140 миллионов точек в 3D может быть вычислена за разумное время (около 0,5-2 секунд) в зависимости от настроек аппроксимации.

Answer 3

CGal делает почти то, что вы хотите, и это GLP / QPL. Проверьте эту страницу . Похоже, вам придется немного поиграть, чтобы использовать их нижние библиотечные функции для создания трехмерного прямоугольного случая, если ограничивающие сферы не то, что вам нужно, но в целях ускорения обнаружения столкновений ограничивающие сферы должны быть в порядке. .