Задать вопрос
@babatus
Учусь кодить и верстать)

Какой алгоритм выбрать для двумерной упаковки?

Здравствуйте. Помогите пожалуйста выбрать алгоритм для данного случая двумерной упаковки:
Имеются прямоугольные объекты, которые нужно разместить в ломанной области. Пример такой области (на картинке заштрихована):
20be94d450fb4842b1c9ad24fb89de2c.jpg
Этот алгоритм хочу использовать для решения подзадачи трехмерной упаковки контейнера (послойно). Помогите пожалуйста.
  • Вопрос задан
  • 1152 просмотра
Подписаться 3 Оценить Комментировать
Ответ пользователя aynur_safin К ответам на вопрос (3)
@aynur_safin
Гуглите "задача об упаковке в контейнеры" или "Bin packing problem".
https://en.wikipedia.org/wiki/Bin_packing_problem

Искал решение для своих задач, вот несколько ссылок.

Неплохая реализация решения BPP в Excel.
Прямо в Excel можно задавать все параметры (кол-во и размеры коробок и элементов) и получить готовое решение и даже визуализацию результата.
verolog.deis.unibo.it/bpp-spreadsheet-solver

Статья на Хабре, описание алгоритмов, есть пример реализации.
https://habrahabr.ru/post/136225/

Больше всего мне подошли решения этого автора.
Лучшее сочетание - время выполнения/результат.
clb.demon.fi/projects/rectangle-bin-packing
clb.demon.fi/projects/more-rectangle-bin-packing
clb.demon.fi/projects/even-more-rectangle-bin-packing
Реализация:
https://github.com/juj/RectangleBinPack

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