@makaleks

Как называется задача или алгоритм выявляния из заданного набора тех прямоугольников, которые больше всего не подходят для замощения заданной области?

Не хватает кругозора и терминологии, чтобы нагуглить решение или наиболее близкий ответ.

Постановка. Есть на входе доступная 2D-область со свойствами {av_width, av_height} (available, в смысле) и набор прямоугольников со свойствами {x, y, width, height}, которые в идеальном мире должны замощать первую, доступную область. Проблема в том, что набор прямоугольников может быть +-корявым, то есть надо:
  1. Выявить самые неподходящие для замощения многоугольки.

    Тут вроде понятно: надо отобрать такие, у которых доля пересечения относительно собственной площади максимальна. С другой стороны ведь хорошо бы Не учитывать пересечения с 'исключёнными' прямоугольниками, то есть в наивной попытке решения каждое новое исключение будет вести к пересчёту исключений старых. Какая-то релаксация получается, или как оно называется.
  2. Подогнать оставшиеся прямоугольники до полного замощения (то есть без 'просветов') доступной области.

    Даже как подступиться не знаю.

Приложение. Есть окно, в которое пользователь передаёт строку с разбивкой на области (передаёт, потому что строкой можно поделиться и воспроизвести сессию). Строго говоря, в элементах списка разбивки есть ещё идентификатор открываемого в подокне ресурса (для примера, пусть файла), но к задаче это не относится. Разбивка не ограничена прямоугольной сеткой, например может быть как колонка_из_третей+колонка_из_половинок, так и то же самое для строк. Группировки тоже нет никакой, то есть методы тайловых менеджеров вроде неприменимы. Дополнительно, есть ограничение на минимальные высоту и ширину подокна, но для начала найти бы решение без учёта этого ограничения.

Спасибо
  • Вопрос задан
  • 130 просмотров
Решения вопроса 2
Ответ написан
Комментировать
sergiks
@sergiks Куратор тега Алгоритмы
♬♬
Задача о замощении в общем случае же NP-полная, решается полным перебором всех вариантов.

Ну и как уже подсказали: нужна функция оценки варианта замощения.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
gbg
@gbg
Любые ответы на любые вопросы
Для начала нужно четко сформулировать критерий оптимального замощения, в таком случае, те прямоугольники, что при таком замощении были выброшены и будут самыми неподходящими.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы