Алгоритм размещения объектов в пространстве

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

Существуют ли какие-либо алгоритмы PHP для этого и как это называется?

Обновление: После дополнительных поисков я думаю, что то, что мне нужно, называется проблемой упаковки в корзину. Тем не менее, я также хотел бы добавить некоторую степень рандомизации для определенных типов проблем с упаковкой (например, изображений), чтобы обеспечить человеческий интерес.


person Xeoncross    schedule 13.07.2011    source источник
comment
Являются ли эти объекты фиксированными по размеру... т. е. вы хотите найти диапазон изображений, которые поместятся в определенную рамку. Или вы хотите масштабировать эти изображения (сохраняя пропорции) в заранее заданную рамку?   -  person diagonalbatman    schedule 13.07.2011
comment
Я бы на самом деле согласился на любой. Однако меня больше интересует, чтобы они хорошо подходили друг к другу, чем конечная матрица определенного размера.   -  person Xeoncross    schedule 13.07.2011
comment
Я думаю, что этот вопрос очень близок к тому, что мне нужно: stackoverflow.com/questions/4904049/php-array-performance< /а>   -  person Xeoncross    schedule 13.07.2011
comment
Я нашел кое-что в JavaScript, поэтому хочу проверить, Я могу понять это и преобразовать некоторые из них.   -  person Xeoncross    schedule 13.07.2011
comment
Есть алгоритмы, и есть реализации этих алгоритмов для конкретных языков, таких как PHP. Я предлагаю сделать этот вопрос независимым от языка, потому что это QI (довольно интересно).   -  person Karoly Horvath    schedule 14.07.2011
comment
Всегда есть math.stackexchange.com, чтобы заинтересовать математиков. По-видимому, они уже некоторое время говорили об этом:   -  person Andresch Serj    schedule 15.07.2011
comment
Обратите внимание на швейную промышленность, где приоритетом является оптимальная установка выкройки нестандартного размера на метраж ткани, а также на лесопромышленность, которая встраивает выкройки в бревна.   -  person Patrick Hughes    schedule 16.07.2011
comment
В Java есть Drools Planner: возможно, вы сможете перенести некоторые эвристики построения (сначала уменьшение соответствия, уменьшение наилучшего соответствия, ...) и метаэвристика (поиск табу, имитация отжига) для PHP (поскольку это открытый исходный код под лицензией ASL).   -  person Geoffrey De Smet    schedule 17.07.2011
comment
@Geoffrey: я уже сделал 1d-bin-packing в php, но не с открытым исходным кодом. Вы можете скачать его на phpclasses.org (bin-packing).   -  person Gigamegs    schedule 18.07.2011
comment
Мне кажется, что вы хотите воссоздать функцию показа всех окон Mac OS X, Exposé. Я не правильно понимаю вашу проблему?   -  person Pops    schedule 21.09.2011
comment
@LordTorgamus, я не уверен, но эта функция звучит очень близко.   -  person Xeoncross    schedule 21.09.2011


Ответы (3)


2D-упаковка контейнеров — это NP-сложная задача. Однако существуют приближенные алгоритмы.

Посмотрите на этот код (и объяснение). Он содержит несколько алгоритмов и графический интерфейс:

Решение проблемы двухмерной упаковки

person Petar Ivanov    schedule 16.07.2011
comment
Извините за -1, но связанный сайт требует, чтобы вы зарегистрировались и вошли в систему, чтобы просмотреть его, что обычно не является проблемой, но для них требуется адрес .. компания, размер компании .. ect. Не должен был предоставлять это для ответа. - person Loktar; 05.08.2011

Я написал алгоритм упаковки 1d bin в php. Вы хотите искать наиболее подходящий, первый подходящий и так далее. Но это не для 2d задачи, может вы хотите поискать задачу о рюкзаке?

person Gigamegs    schedule 15.07.2011
comment
Я нашел PHP-версию проблемы с рюкзаком, но я не уверен, как это относится к 2D-области для заполнения. - person Xeoncross; 16.07.2011
comment
@Xeon: По крайней мере, у вас есть алгоритм с двумя переменными: весом и стоимостью. Может быть, вы можете изменить его? Еще одно приложение — drools-planer. - person Gigamegs; 16.07.2011
comment
Проблема в том, что формула использует только одно ограничение и один приоритет. Так что это просто прославленный алгоритм 1D. Мне нужно что-то, что обрабатывает 2 ограничения (с необязательным приоритетом). - person Xeoncross; 16.07.2011
comment
@Xeon: я вижу, вы пробовали алгоритм Флойда-Уоршалла или алгоритм максимального соответствия Эдмонда? - person Gigamegs; 16.07.2011
comment
@Xeon: Может быть, пространственный индекс или дерево квадрантов? Si уменьшает сложность 2d до сложности 1d. - person Gigamegs; 16.07.2011
comment
@Xeon: Вы хотите заглянуть в блог кривой Гильберта квадрантов пространственного индекса Ника. - person Gigamegs; 16.07.2011

Я думаю, вы можете использовать алгоритм имитации отжига. Я использовал его, чтобы заполнить прямоугольные газетные страницы прямоугольными рекламными объявлениями. Как вы сказали, вы можете начать с рандомизированного решения, а затем постепенно прийти к хорошему решению. См. здесь http://codetuner.blogspot.com/2010/03/simulated-annealing-approach-to.html. Я использовал его для решения проблемы с нумерацией страниц. Я думаю, вы можете использовать его и для своих требований.

person Jayantha Lal Sirisena    schedule 22.07.2011