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

Question

Мне нужно решить следующую проблему: у меня есть несколько прямоугольников размеров: ширина высота, ширина / 2 высота / 2, ширина / 4 высота / 4, ширина / 8 высота / 8 ... и т. Д.

Мне нужно упаковать эти прямоугольники в большой прямоугольник размером x * width y * height так, чтобы прямоугольники не перекрывались, прямоугольники распределялись случайным образом в упаковке, и любой прямоугольник должен хотя бы касаться другого прямоугольника.Я попробовал довольно простой жадный алгоритм, но он не работает.

Можете ли вы дать мне несколько советов, как решить проблему?

Спасибо!

РЕДАКТИРОВАТЬ: Вы можете иметь более одного прямоугольника каждого размера

Это не домашняя работа.Я пытаюсь создать эффект, подобный эффекту на ted.com

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

Answer 1

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

Answer 2

Вы можете использовать пространственный индекс или квадродерево, чтобы подразделить 2d-плоскость.Идея состоит в том, чтобы свести 2-мерную проблему к 1-мерной.Как только вы получили пространственный индекс (или кривую заполнения пространства) и можете дискретизировать 2d в 1d, вы можете использовать 1d для поиска сходства или для сортировки от низкого к высокому или наоборот, например, по длине.Если вы получили этот заказ, вы можете затем вычислить индекс обратно в 2d представление и наиболее эффективно упаковать их в свой контейнер.Есть много способов сделать пространственный индекс.Одной из лучших, но трудных для построения является кривая Гильберта.Другой - это Z-образная кривая или кривая МортонаОн отличается от кривой zizag, потому что он подразделяет плоскость на 4 квадрата (не прямоугольники).

РЕДАКТИРОВАТЬ: Вот ссылка на плагин Jquery: http://www.fbtools.com/jquery/treemap/ Здесь с населением мира: http://www.fbtools.com/jquery/treemap/population.html

РЕДАКТИРОВАТЬ: http://people.csail.mit.edu/konak/papers/socg_2008-circular_partitions_with_applications_to_visualization_and_embeddings.html

РЕДАКТИРОВАТЬ: http://lip.sourceforge.net/ctreemap.html

Answer 3

На каждом шаге вы делите поверхность вашего нового прямоугольника на 4.

SUM (1/4 n для n в [0, inf]) = 4 /3 **

Итак, лучшее, что вы можете сделать, это поместить прямоугольник в прямоугольник с поверхностью 4/3 (высота * ширина)

(это нижняя граница)

@ алгоритм mloskot дает возможное решение, которое будет в прямоугольнике поверхности 3/2 * (высота * ширина): Вот иллюстрация:

Надеюсьне вижу, как вы можете сделать лучше.

Answer 4

Это очень похоже на MIP-отображение

Answer 5

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

1. Возьмите первый прямоугольник и поместите его в угол целевой плоскости.
2. Возьмите следующий прямоугольник (утверждайте, что он меньше предыдущего прямоугольника)
3. Поворот на 90 градусов
4. Место так
   • его более короткий размер соседствует с более длинным размером последнего большего соседа
   • и его более длинная сторона примыкает к краю целевой плоскости или к краю соседа того же самого размер
5. Повтор 2 - 4

Я понимаю, что описание может быть неясным, поэтому вот изображение, представляющее решение - оно должно помочь понять: