Алгоритм впихивания многоугольников в форму

0

1

У меня возникла задача, спрятать изображение наложив сверху несколько других. Т.е. есть список могоугольников и их нужно вписать в форму. Допускаются небольшие дырки или небольшой заступ за пределы формы. Вот как на рисунке фигуры с буквами впихиваются в большой пятиугольник Если кто-то сталкивался с подобным, подскажите алгоритм или хотя бы куда копать.

Ссылка

←	Сборка rpmbuild от non-root пользователя

GNU Assembler: Зачем нужна директива .type?

→

https://en.wikipedia.org/wiki/Bin_packing_problem например

SZT ★★★★★
(13.08.15 19:44:58 MSK)

Ссылка

Вообще можно тут так поступить. Ввести понятие оценочной функци для упаковки. Оценочную функцию определить на основе областей пересечения многогранников, количество незанятого и вылезания их за пределы вписываемого прямоугольника. Количество возможных всовываний конкретного прямоугольника в конкретное место можно «дискретизовать» т.е. задать фиксированные допустимые углы поворота (например 2, 4, 6, 8, 10 ... градусов) фигуры и допустимые координаты, т.е. чтобы фигуры были как бы выравнены по некоей сетке. После чего применить альфа-бета отсечение при поиске множества возможных способов втулить некое множество фигур. После того как найден более-менее приемлемый вариант, можно попробовать отвязать фигуры от сетки и сделать углы нефиксированными или просто уменьшить шаг сетки и шаг допустимых углов и опять альфа-бета отсечение. И так пока не надоест

SZT ★★★★★
(13.08.15 20:11:03 MSK)