Программно позиционирование фигур - эффективная упаковка

Question

Допустим, у меня есть несколько абстрактных фигур, каждая из которых имеет ширину и высоту (для простоты сделаем их прямоугольниками). Как я могу разместить как можно больше из них на одном холсте (просто термин, не обязательно холст HTML5) определенной ширины и высоты?

Очевидно, что это какая-то проблема удовлетворения ограничений, но я не знаю, с чего начать (кроме грубой силы). Поиск в Google просто приводит к несвязанным результатам (вероятно, потому что я не знаю, что искать). Каким будет хороший алгоритм или как создать алгоритм для этого?

Fizz является хорошим примером. Формы (в данном случае круги) появляются в группах и не перекрывают друг друга, и они не мешают друг другу. Мой вариант использования - это скорее сделка с однократным позиционированием. Другой пример - SpriteRight , который максимально эффективно размещает в определенных границах.

Answer 1

Ваша проблема может быть полезна при программировании логики ограничений в конечных областях ( clpfd ).

Рассмотрим вопрос и ответы на Обработка ограничений Пролога: квадраты упаковки . Он показывает несколько методов, один из которых использует выделенные ограничения размещения , чтобы найти макет неперекрывающихся прямоугольников в 2D.

clpfd также позволяет применять дополнительные ограничения в дополнение к ограничению упаковки. Существуют как бесплатные (например, SWI и YAP ), так и коммерческие (например, SICStus ) пролог реализации, которые поддерживают clpfd .

Answer 2

Вы также можете посмотреть на http://www.aimms.com/downloads/application-examples/circle-packing. Здесь математическое программирование / моделирование используется для решения проблемы упаковки кругов.Другие варианты также могут быть определены.В ограниченном программировании существуют специальные ограничения на упаковку бинов, http://www.aimms.com/cp.

В общем, математическое программирование - хороший способ решения таких проблем.

Answer 3

Я нашел пример с открытым исходным кодом с JavaScript и HTML5 canvas.Прямоугольники генерируются случайным образом, а затем упаковываются.Автор, однако, не претендует на эффективность.

Я также нашел статью , которая выглядит многообещающе.