Самая маленькая прямоугольная коробка, которая окружает многогранник

Question

Я ищу алгоритм, который находит наименьшее поле, содержащее многогранник.

Моя идея заключается в следующем: найти самую большую сторону и переместить тело так, чтобы сторона выровнялась с осью х. Найдите следующую наибольшую сторону, которая встречается с этой стороной, и выровняйте ее как можно ближе к оси z, оставив другую сторону по оси x. Затем рассчитайте наибольшие различия по x, y и z. Используйте эти размеры, чтобы создать окружающую форму, а затем переместите окно обратно в исходное местоположение объекта.

Есть ли более эффективная стратегия для этого? Моя идея не учитывает некоторые угловые случаи?

Изменить: сейчас предположим, что объект, который будет ограничен, является выпуклым. Хотя, ответ для общего случая также будет приветствоваться.

Answer 1

Проблема нахождения минимальных (объемных) ящиков для выпуклых многогранников была исследована О'Рурком, который предлагает O(n^3) алгоритм:

Дж. О-Рурк. Нахождение минимальных вмещающих коробок. Международный журнал компьютерных и информационных наук, 1985, 14(3), с.183.

Алгоритм О'Рурка находит минимальную ограничивающую рамку для набора точек в R^3 - но это явно эквивалентно нахождению вмещающей коробки для многогранника, сформированного как выпуклая оболочка лежащего в основе набора точек.

Вопреки тому, что можно ожидать (и подход, который вы описали, если я вас правильно понял), минимальный прямоугольник не обязательно ориентирован так, что грань многогранника копланарна грани бокса! Обратите внимание на анимацию, показанную здесь для простого тетраэдра.

Если вы довольны идеей простого нахождения относительно небольшого вмещающего бокса, а не самого маленького вмещающего бокса, то может быть применена другая (более быстрая) эвристика...