Упаковка полигонов 2D

Question

У меня проблема упаковки 2-х произвольных полигонов. То есть у нас есть 2 произвольных многоугольника. Мы должны найти такое размещение этих многоугольников (мы могли бы делать повороты и перемещения), когда прямоугольник, который описывает эти многоугольники, имеет минимальную площадь.

Я знаю, что это NP-полная проблема. Я хочу выбрать эффективный алгоритм для решения этой проблемы. Я ищу подход No-Fit-Polygon. Но я нигде не смог найти простой и понятный алгоритм для нахождения NFP двух произвольных многоугольников.

Answer 1

Пространство параметров не кажется слишком большим, и тестирование тоже не так уж плохо. Если вы исправите один многоугольник, другой плойгон может быть смещен вдоль оси x на X, смещен вдоль оси y на Y и повернут на r.

Интересную область для X и Y можно определить, найдя некоторую ограничивающую рамку для полигонов. р, конечно, между и 360 градусов.

Итак, как насчет того, чтобы вы попробовали набор из набора равных интервалов в интересном диапазоне для X, Y и r. Возможно, когда вы найдете интересные точки в этих измерениях, вы сможете выполнить более точный поиск.

Answer 2

Если его NP-полная, то вам нужна эвристика, а не алгоритмы. Я бы попытался соединить каждую возможную пару сторон, а затем сдвинуть одну против другой, чтобы минимизировать область, ограниченную возможным перекрытием, если они, конечно, вогнутые.