Расположение разных фигур в прямоугольной области

Необходимо максимально плотно (без пересечения) разместить различные фигуры, разного размера, на изображении.

Вот что получилось сделать с помощью случайных чисел

Прикреплённая картинка

Кроме очевидной проблемы, подбор координат занимает продолжительное время.

Подскажите, какой алгоритм использовать для решения данной задачи.
Возможно подойдет какая-то библиотека, вроде OpenCV.

Сообщение отредактировано: WinAx - 28.12.17, 23:46

Должно получится вот так, только с разными фигурами

Прикреплённая картинка

Сообщение отредактировано: WinAx - 29.12.17, 00:03

Я бы разбил задачу на 2 этапа:
1. Окружение всякой фигурки в N-угольником. (впредь можно будет выбирать для каждой фигуры свой N).
2. Плотное размещение N-угольников в прямоугольнике (k-угольнике).

Цитата WinAx @ 29.12.17, 00:00

Должно получится вот так

То есть фигурки можно вращать?

Цитата Mikle @ 29.12.17, 07:41

То есть фигурки можно вращать?

В моем варианте требуется без вращение.
Второе изображение прикрепил для демонстрации необходимой плотности.

Цитата WinAx @ 28.12.17, 23:45

Вот что получилось сделать с помощью случайных чисел

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

Mikle сам до этого дошел. Компактнее, конечно. Но все ровно не подходит

Прикреплённая картинка

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

А так, лучшее, что приходит в голову, случайно бросать фигуры на область, а потом уплотнять. "Сдвигать влево вверх до касания" не всегда лучший вариант. Обычно лучшие результаты даёт "виброуплотнение" (хотя оно и медленное). Фигура размещается на свободное место, а потом небольшими случайными сдвигами перемещается к точке укладки. Если на очередном шаге она наползает на ранее уложенную, шаг отменяется, если новое положение хуже "энергетически" чем предыдущее (фигура дальше от точки притяжения/ближе к точке отталкивания), то оно либо тоже отменяется, либо принимается с какой-то постепенно убывающей до нуля вероятностью.

На самом деле лучше продолжать так "трясти" все фигуры, а не только последнюю, но это ещё сильнее замедлит работу.

Цитата amk @ 29.12.17, 16:20

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

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

1) Самую большую фигуру стараемся расположить в центре
2) Далее обходим сперва менее большими фигурами по 1 витку спирали
3) Потом средними и мелкими по той же спирали, дабы выровнять края
4) И так N, или даже M итераций-спиралей
5) К краям области заполнения "добираемся" уже совсем самыми мелкими фигурами

Тут же приходит в голову контрпример, JoeUser, показывающий ужасность такового решения: семейство крайне тонких окружностей различного радиуса.
Впрочем, примеры строить - не алгоритм предлагать, так что полезность этих примеров весьма сомнительна. Но всё же! :-)

Цитата JoeUser @ 29.12.17, 18:47

Потом средними и мелкими по той же спирали, дабы выровнять края

Совсем мелкие можно было бы размещать между ранее уложенными крупными объектами, заполняя промежутки

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

Добавлено 29.12.17, 20:58
В некоторых методах разрешается втискивать мелкий объект в промежутки недостаточные по размеру, для этого соседние объекты просто раздвигаются в стороны

Цитата Славян @ 29.12.17, 20:10

семейство крайне тонких окружностей различного радиуса.

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

Цитата amk @ 29.12.17, 20:54

Это особый случай.

Да, в определённом смысле согласен.

Цитата amk @ 29.12.17, 20:54

сплошными, без полостей, в которые можно было бы уложить другой объект.

Когда на "идеальной" картинке автора темы сердечки втыкаются в сердечки и капли обткают капли(на первой), то тут начинает развиваться и другой/ваш случай, - "в которые". Так что всё довольно размыто.

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

Прикреплённая картинка

"Не стягиваемый" объект в математике называется многосвязным. Кольцо - двусвязно, восьмёрка - трёхсвязна.
Описанными четырьмя классами всё и ограничивается. Но, на самом деле швеллер (1/3) по укладке не сильно отличается от звёздочки, например, любой подходящий объект можно просто вдвинуть в него справа. Другое дело - разрезанное в виде буквы "С" кольцо, в которое через щель могут быть вдвинуты мелкие объекты, но крупные в щель не пройдут.

Моя идея с размещением на свободное место и встряхиванием не сильно зависит от такой классификации

Цитата amk @ 30.12.17, 16:43

Моя идея с размещением на свободное место и встряхиванием не сильно зависит от такой классификации

Да, идея с "встряхиванием" весьма мощная, ибо сдвигом можно очень многое получить. Однако, при форме фигур - древовидного вида, встряхивание будет тоже давать слабоватые результаты, т.к. деревья будут вечно цепляться краями друг за дружку и отказываться двигаться далее. Это, бесспорно, вообще ещё более "особый случай", но всё же!..