Как найти минимальный ограничивающий параллелепипед?

Question

[Tranzi]

Есть некоторое количество произвольных точек (от 8 до 800). Необходимо найти минимальный прямоугольный параллелепипед ограничивающий данные точки. Он естественно может быть повернут относительно глобальных осей координат.
Операция выполняется при клике мышкой и поэтому ожидание 1-2с неприятно,но тоже не критично.

Был бы очень признателен если посоветуете библиотеку для С++ (и ,если вас не затруднит конечно, сразу еще и пример :) или алгоритм как это сделать.

Comments

[Rsa97]

Минимальный по какому параметру? Что меньше, (3, 3, 3) или (4, 3, 2)?

[Tranzi]

По объёму, 4*3*2 меньше,чем 3*3*3.

Answer 1

[mayton2019]

Я не уверен что стоит вообще искать идеальное решение. Особенно для 800 точек. Задача
пахнет комбинаторной со всеми вытекающими.

Я-бы предложил дать программе время (секунд) или количество итераций через которые
она должна выдать почти-минимальный параллелепипед. Но мы при этом понимаем что это не самый идеальный.

Для малого числа точек (8) можно построить выпуклую оболочку. И попробовать прикладывать
первую грань параллелепипеда к каждой грани выпуклой оболочки. А оставшиеся грани мы можем
получить вращением параллелепипеда до тех пор пока bounding volume не будет минимален.
Учитывая дискретность выпуклой оболочки, поворот тоже может быть дискретным. Например там
проверить штук 20 углов. Вот как-то так.

Comments

[U235U235]

Выпуклую оболочку по-любому придется строить, тем более для 800 точек.
Для этого есть библиотека (open source) qhull

[mayton2019]

U235U235, ну да. Ее можно строить просто для того чтобы не работать со всеми 800
точками а взять хотя-бы 100 которые реально влияют на Bounding Box. Внутренние точки - в игнор.

И для большого числа точек я-бы брал генетический алгоритм. Где хромосома - это вектор
типа { α, β, γ } с эйлеровмы углами ну фитнес - это объем параллелепипеда.

Answer 2

[Wataru]

Вам же минимальный по объему паралеллипипед нужен? Это довольно сложная задача. Даже на плоскости искать прямоугольник не очень приятно.

Кажется, есть эффективное решение через численную оптимизацию и троичный поиск.

Введем функцию f(a,b) - минимальный объем параллелипипеда, повернутого на угол a вдоль оси oz и потом угол b вдоль ox. Ну или это эйлеровы углы, если хотите.

Вам надо найти минимум этой функции. Утверждение: если зафиксировать a, то двигая b функция будет переодическая с двумя экстремумами. Ну, потому что поворот на 90 градусов взвращает все как было, только оси местами меняются. Значит, на ней можно что-то вроде тернарного поиска запускать (об этом дальше).

Если же ввести функцию g(a) =Min_b(f(a,b)), то она, похоже будет такая же. По ней тоже можно такой же поиск запустить.

Итого, 2 вложенных тернарных поиска, в внутри легче все точки повернуть на -b и -a градусов и потом взять обрамляющий параллелипипед, параллельный осям координат (min/max по трем координатам за 1 проход).

В тернарном поиске делим отрезок всех углов на 3 части, считаем значение функции в двух промежуточных и крайних точках. Дальше придется повозиться со случаями, их много (12), Функция может сначала иметь максимум, потом минимум, или наоборот. И 6 вариантов, как 2 промежуточные точки лягут на 3 отрезка (возрастание,убываниние, возрастание или убывание, возрастание, убывание). Тут надо их все аккуратно нарисовать, подумать, какие соотношения четырех точек позволяют выкинуть один из трех отрезков между точками.

Возможно, придется вообще считать производные (изменять чуть-чуть угол, считать функцию и смотреть, как она поменялась). Тогда будет сильно проще решить, какой из отрезков выкинуть. Ну или тогда можно метод Ньютона применять (считая вторую производную функции численно).

Это будет что-то вроде O(n log^2 n).

Или можно просто случайным образом или с малым шагом перебирать разные углы поворота. Поворачивать все точки и искать параллельный осям координат параллелипипед (просто беря min/max по трем координатам). Для 800 точек можно 10000 углов перебрать и это займет лишь 100мс на современном железе.

Это сильно проще в реализации и, хоть и не найдет самый оптимальный параллелипипед, на глаз будет сложно это заметить.

Edit: вообще, кажется, там 3 угла, а не 2. Ну появляется еще третья функция t(a,b,c). и лишний Log n в сложности. Перебирать углы становится еще хуже, но все еще возмоно.