Не хватает кругозора и терминологии, чтобы нагуглить решение или наиболее близкий ответ.
Постановка. Есть на входе
доступная 2D-область со свойствами {av_width, av_height} (available, в смысле) и набор прямоугольников со свойствами {x, y, width, height}, которые в идеальном мире должны замощать первую,
доступную область. Проблема в том, что набор прямоугольников может быть +-корявым, то есть надо:
- Выявить самые неподходящие для замощения многоугольки.
Тут вроде понятно: надо отобрать такие, у которых доля пересечения относительно собственной площади максимальна. С другой стороны ведь хорошо бы Не учитывать пересечения с 'исключёнными' прямоугольниками, то есть в наивной попытке решения каждое новое исключение будет вести к пересчёту исключений старых. Какая-то релаксация получается, или как оно называется.
- Подогнать оставшиеся прямоугольники до полного замощения (то есть без 'просветов') доступной области.
Даже как подступиться не знаю.
Приложение. Есть окно, в которое пользователь передаёт строку с разбивкой на области (передаёт, потому что строкой можно поделиться и воспроизвести сессию). Строго говоря, в элементах списка разбивки есть ещё идентификатор открываемого в подокне ресурса (для примера, пусть файла), но к задаче это не относится. Разбивка не ограничена прямоугольной сеткой, например может быть как колонка_из_третей+колонка_из_половинок, так и то же самое для строк. Группировки тоже нет никакой, то есть методы тайловых менеджеров вроде неприменимы.
Дополнительно, есть ограничение на минимальные высоту и ширину подокна, но для начала найти бы решение без учёта этого ограничения.
Спасибо
