Алгоритм, необходимый для равномерного распределения прямоугольников внутри другого прямоугольника

Question

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

Я посмотрел на алгоритмы упаковки бинов, но они, кажется, минимизируют количество пространства между прямоугольниками (в моем случае все упаковываемые предметы будут квадратными).

Я думаю, я хочу максимизировать расстояние между всеми квадратами и границей внешнего прямоугольника.

Вот примериз того, что я пытаюсь сделать:

Answer 1

Что, если вы упаковали их как можно плотнее, используя алгоритм, подобный , который описан здесь , а затем равномерно расширялся, чтобы соответствовать целевому вмещающему прямоугольнику?

Например, скажем, вы можете упаковать 3 вышеупомянутых прямоугольника в коробку 3x2, и ваша внешняя коробка будет 7x5. Затем возьмите вектор из центра прямоугольника в центр каждого прямоугольника и умножьте компонент x на (7/3), а компонент y на (5/2), и это даст новый центр.

Answer 2

Это, кажется, обобщение задачи о ранце .

Динамическое программирование решит ее за полиномиальное время.