Какой алгоритм может использоваться для упаковки прямоугольников различных размеров в наименьший прямоугольник, возможный довольно оптимальным способом?
Другой, потенциально более чистая опция состоит в том, чтобы использовать управление TableLayout. Создайте одну строку желаемой высоты для Вашего главного прикрепления и другую строку для заполнения 100% для нижней части. Набор обе панели внутри для Заполнения, и Вы сделаны.
(TableLayout действительно берет некоторых привыкающих к, все же.)
5 ответов
Быстрое и грязное решение для первого прохода всегда является отличным вариантом для начала, как минимум для сравнения.
Жадное размещение от большого к меньшему.
Поместите самый большой прямоугольник. оставаясь в вашем упакованном районе. Если он никуда не помещается, поместите его в такое место, которое как можно меньше расширяет область упаковки. Повторяйте, пока не закончите с самым маленьким прямоугольником.
Это совсем не идеально, но это просто и хорошая базовая линия. Он все равно идеально упакует ваш исходный пример и даст эквивалентный ответ и для второго.
Посмотрите на проблемы с упаковкой . Я думаю, ваша подпадает под «2D-упаковка для мусорных контейнеров». Вы сможете многому научиться из решений этой и других проблем с упаковкой.
См. Также: Упаковка данных прямоугольного изображения в квадратную текстуру.
Я почти уверен, что это NP-трудная проблема , поэтому для оптимального решения вам придется реализовать алгоритм обратного отслеживания, который пробует всевозможные комбинации.
Хорошая новость заключается в том, что из-за необходимости упаковать 2D-прямоугольники в ограниченное 2D-пространство, вы можете сократить множество возможностей на раннем этапе, так что это может быть не ТАК плохо.
Общее решение нетривиально (математика говорит, что совершенно невозможно)
Обычно люди используют генетический алгоритм, чтобы попробовать возможные комбинации, но вы можете сделать достаточно хорошо, просто поместив сначала самую большую форму, а затем пробуя разные места для следующей по величине и так далее.
По этой проблеме существует обширная литература. Хорошая жадная эвристика - разместить прямоугольники от наибольшей области к наименьшей в первой доступной позиции в нижней и левой части контейнера. Представьте, что сила тяжести притягивает все предметы в нижний левый угол. Для описания этого гугл "упаковка Chazelle слева внизу".
Для получения оптимальных решений современные методы позволяют упаковать более 20 прямоугольников за несколько секунд. У Хуанга есть алгоритм , который отделяет проблему поиска наименьшего ограничивающего прямоугольника от проблемы принятия решения о том, может ли набор прямоугольников поместиться в ограничивающий прямоугольник определенного размера. Вы даете его программе набор прямоугольников, и она сообщает вам наименьшую ограничивающую рамку, необходимую для их упаковки.
В вашем случае внешний цикл должен повторяться от минимально возможного ограничивающего прямоугольника вверх (при этом ширина и высота последовательно увеличиваются в степени двойки). Для каждой из этих ограничивающих рамок проверьте, сможете ли вы найти упаковку для своих прямоугольников. Вы получите кучу ответов «нет» до первого «да», который гарантированно будет оптимальным решением.
Для внутреннего цикла вашего алгоритма - того, который отвечает «да» или «нет» на ограничивающую рамку определенного размера, я бы просмотрел ссылку Хуанга и просто реализовал его алгоритм. Он включает в себя множество оптимизаций поверх базового алгоритма, но вам действительно нужны только базовое мясо и картофель. Поскольку вы хотите обрабатывать вращения, в каждой точке ветвления во время поиска просто попробуйте оба поворота и возврат, если оба поворота не приводят к решению.