Оптимальное размещение прямоугольников с доп. условиями

[ibnz]

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

Во вложении иллюстрация тривиального размещения, гарантирующего непересечение:

1. список отсортировать по ординате
2. вынимать первый встреченный с ординатой большей конца предыдущего вынутого в новый список-столбец
3. при достижении конца, начать новый столбец с начала
4. повторять до исчерпания списка
5. Разделить ширину контейнера на количество столбцов и всем прямоугольникам установить полученную ширину.
6. разместить столбцы один за другим.

Очевидно, что оно неоптимально. Думаю над алгоритмом лучшего размещения...

[Igors]

Наверное имеется ввиду что ширина тоже задана или по крайней мере "не меньше", иначе смысла нет. Если прямоугольников относительно немного, то перебором. До конца не вижу, пока ясно

Выстраиваем все прямоугольники слева так что они перекрывают друг друга. Имеем ряд интервалов по Y. Для каждого интервала известна макс ширина - сумма ширин покрывающих его пр-ков. Выбираем интервал с макс шириной, дальше перебираем все возможные расстановки входящих в интервал. На каждом шаге повторяем для верхней и нижней половинок.  

[ibnz]

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

Выбираем интервал с макс шириной, дальше перебираем все возможные расстановки входящих в интервал.

А какой брать локальный критерий лучшей расстановки?


В данный момент мне кажется перспективной идея  итеративного "раздувания" площади виджетов до "выравнивания давления" после тривиального размещения. Обдумываю как ее формализовать.

[ibnz]

надо получить нечто вроде такого

[Bepec]

оффтоп: по-моему получится нечитабельный писец, а не интерфейс. Ну да дело каждого.

[Igors]

А какой брать локальный критерий лучшей расстановки?

На первом шаге находим интервал покрываемый N пр-ками. Их ширны известны, сумма дает макс общую ширину, меньше не выйдет. Однако больше - может, поэтому на последующих шагах оптимальный - который дает наименьшую новую общую ширину. Если новая == старой, то остаток можно не перебирать

[ibnz]

На первом шаге находим интервал покрываемый N пр-ками. Их ширны известны, сумма дает макс общую ширину, меньше не выйдет. Однако больше - может, поэтому на последующих шагах оптимальный - который дает наименьшую новую общую ширину. Если новая == старой, то остаток можно не перебирать

На примере вложения из 1 поста. Интервал с макс пр-ками 2:00-2:10.
Пытаемся расставить пр-ки 5,6,7,8,9. Ширина каждого 0,2 (1 =ширина контейнера). Как понять какой из 120 вариантов перестановки в дальнейшем даст лучший выигрыш? Без учета того, что встретится далее, я не понимаю как это сделать. а учитывать накладно - сложность растет по факториалу.

[Igors]

На примере вложения из 1 поста. Интервал с макс пр-ками 2:00-2:10.
Пытаемся расставить пр-ки 5,6,7,8,9. Ширина каждого 0,2 (1 =ширина контейнера). Как понять какой из 120 вариантов перестановки в дальнейшем даст лучший выигрыш? Без учета того, что встретится далее, я не понимаю как это сделать. а учитывать накладно - сложность растет по факториалу.

Ну чего ж 120 когда 2^5 = 32? Для каждого варианта считаем  пр-ки 5,6,7,8,9 расставлеными и с учетом этого занимаемся верхней и нижней половинками. Где ж факториал когда их там уже осталось с гулькин "нос"? 

[ibnz]

Ну чего ж 120 когда 2^5 = 32? Для каждого варианта считаем  пр-ки 5,6,7,8,9 расставлеными и с учетом этого занимаемся верхней и нижней половинками. Где ж факториал когда их там уже осталось с гулькин "нос"? 

спору нет, 2^5 = 32, но количество перестановок = n!