Упаковка Javascript со многими ограничениями, поиск простого решения

Это не совсем упаковка, так как я могу сам задать размеры прямоугольника, мне просто нужен упакованный результат. У меня есть прямоугольники одного соотношения и разных размеров
ПОЛНЫЙ,
ПОЛОВИНА (площадь = 1/4 * ПОЛНАЯ),
ЧЕТВЕРТЬ (площадь = 1/4 * ПОЛОВИНА ).
Все будет располагаться только горизонтально. Ширина контейнера в 3 раза больше FULL, а высота подстроится под размер прямоугольника.

Будет 150 прямоугольников, которым будут заданы случайные размеры из массива (полный, половинный, четверть). Теперь я хочу расположить эти прямоугольники в контейнере так, чтобы не было зазора.

Контейнер и прямоугольники — это элементы HTML DIV. Я использую JavaScript для их упаковки.

Вот скрипт http://jsfiddle.net/MywQ2/1/

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


javascript jquery mathematical-optimization packing
person sabithpocker    schedule 17.01.2012    source источник

Ответы (2)


arrow_upward
1
arrow_downward

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

В примере кода, который у вас есть сейчас, вы выбираете их полуслучайно, так как это зависит от модуля status.

Если ваша цель состоит в том, чтобы заполнить контейнер, казалось бы, случайными прямоугольниками, возможно, вам подойдет следующий алгоритм (код peude):

for rectangle in ['large', 'medium', 'small']:
    try:
        place_rectangle_randomly_in_container(rectangle)
    except NoFreeSpace:
        if rectangle == 'small':
            # container filled
            break

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

Чтобы реализовать размещение, отслеживайте контейнер с помощью двумерного массива логических значений, которые указывают, свободно ли это место; каждый элемент в массиве представляет пространство, которое заполнил бы маленький прямоугольник, поэтому, если контейнер может содержать маленькие прямоугольники 12x12, это будет размерность массива. Чтобы проверить, поместится ли средний прямоугольник в [2,3], вам нужно проверить массив на [2,3], [2,4], [3,3] и [3,4].

Затем размещение прямоугольников выполняется путем их позиционирования, а не плавания влево.

person Wesley    schedule 17.01.2012
comment
Может я чего не понял, попробую еще раз объяснить. У меня есть 150 коробок, я просто хочу заполнить контейнер 150 коробками, они должны быть случайным образом заполнены, наполовину, на четверть. Мы также можем отклонить случайно выбранный размер и получить другой, если будет обнаружено, что он создает зазор. - person sabithpocker; 17.01.2012
comment
Я проверил ваш алгоритм, но я не думаю, что мне нужна такая сложность размещения прямоугольника в любом месте контейнера, я просто хочу заполнить контейнер сверху слева и распространить его вбок и вниз. - person sabithpocker; 17.01.2012
comment
Что ж, я не думаю, что предложенный мной алгоритм такой уж сложный, кажется, он вполне подходит для ваших нужд:) Какую часть вы считаете сложной? Если вы можете придумать более простой алгоритм, пожалуйста, поделитесь им со мной. - person Wesley; 17.01.2012
comment
Может быть, я не очень хорошо понимаю ваш алгоритм, извините. Поместить прямоугольник в любое место контейнера и проверить, занята ли область уже, кажется мне сложным с помощью javascript. Есть ли возможность отслеживать новые угловые точки, доступные после проверки и вставки прямоугольника. Я не уверен, работает ли это, и я не добавлял логику для проверки, происходит ли перекрытие. Может быть, мне следует попробовать какую-нибудь безопасную случайность, чтобы они никогда не пересекались. Я очень ценю ваш интерес :) вот новая скрипка наших идей jsfiddle.net/RXrcf/7 - person sabithpocker; 17.01.2012
comment
Я добавил дополнительный текст о том, как отслеживать занятое пространство. - person Wesley; 17.01.2012
comment
Это отличный совет, я пробовал способы его реализации, я реализую логику и сообщу вам. Большое спасибо за поддержку :) - person sabithpocker; 17.01.2012
comment
извините за поздний ответ, я реализовал идею использования матрицы для хранения вакантных должностей. Но вместо того, чтобы распределять проблему по всей площади, я взял небольшие порции и заполнил каждую случайным образом. Вот скрипт jsfiddle.net/Ua8Cv Большое спасибо за вашу потрясающую поддержку :) - person sabithpocker; 20.01.2012
comment
Не за что, рад, что все получилось :) Можешь отметить мой ответ как ответ, если хочешь - person Wesley; 20.01.2012

arrow_upward
1
arrow_downward

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

Решение состояло в том, чтобы разделить холст на сетки 4x4 и заполнить каждую из них «на первый взгляд случайным образом», используя матрицу для отслеживания вакантных позиций.

Этот пример скрипта хорошо объясняет http://jsfiddle.net/Ua8Cv/ .

(Решение Уэсли должно быть помечено как ответ, я пишу отдельное решение только для того, чтобы помочь людям, заходящим на эту страницу из Google, поэтому сначала посмотрите его ответ)

person sabithpocker    schedule 19.01.2012