Алгоритм поиска наименьших прямоугольников для покрытия набора прямоугольников без перекрытия

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

В настоящее время я начинаю в самом верхнем левом прямоугольнике и вижу, могу ли я расширять его справа и вниз, сохраняя при этом прямоугольник. Я делаю это, пока он больше не может расширяться, удалите и разделим все пересекающиеся прямоугольники и добавим расширенный прямоугольник обратно в список. Затем я снова запускаю процесс со следующим верхним левым прямоугольником и так далее. Но в некоторых случаях это не работает. Например:

С этим набором из трех прямоугольников правильное решение будет состоять из двух прямоугольников, например:

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

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

Ответ 1

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

Дэвид Эпштейн обсуждает эту проблему в разделе 3 своей обзорной статьи за 2010 год Графо-теоретические решения задач вычислительной геометрии, и он дает хорошее резюме в этом ответе на mathoverflow.net:

Идея состоит в том, чтобы найти максимальное число непересекающихся осевых параллельных диагоналей, которые имеют две вогнутые вершины в качестве конечных точек, разделенных по ним, а затем образуют еще один раскол для каждой оставшейся вогнутой вершины. Чтобы найти максимальное число непересекающихся осевых параллельных диагоналей, сформируем граф пересечений диагоналей; этот граф двудольный, поэтому его максимальный независимый набор можно найти в полиномиальном времени методами сопоставления графа.

Здесь мой блеск по этому замечательно краткому описанию, используя рисунок 2 из статьи Эппштейна. Предположим, что у нас есть прямолинейный многоугольник, возможно с отверстиями.

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

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

График пересечения набора сегментов линии имеет node для каждого сегмента линии, а ребро соединяет два узла, если линии пересекать. Здесь граф пересечений для оси-параллельных диагоналей:

Он bipartite с вертикальными диагоналями в одной части и горизонтальными диагоналями в другой части. Теперь мы хотим выбрать как можно больше диагоналей, если они не пересекаются. Это соответствует обнаружению максимального независимого набора в графе пересечений.

Поиск максимального независимого множества в общем графике является NP-полной проблемой, но в частном случае двудольного графа теорема Кёнига показывает, что это эквивалентно задаче нахождения максимального соответствия, которое может быть разрешено в полиномиальное время, например, алгоритмом Hopcroft-Karp. Здесь максимальное совпадение:

И вот соответствующая минимальная обложка вершин (красный) и максимальный независимый набор (зеленый):

Переведя это обратно в проблему диссекции, это означает, что мы можем использовать пять осевых параллельных диагоналей при вскрытии:

Наконец, сделайте вырез из каждого оставшегося вогнутого угла, чтобы завершить вскрытие:

Ответ 2

Вот некоторые научные статьи, в которых обсуждаются решения этой проблемы;

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

Оптимальные прямоугольные обложки для выпуклых ректинилинговых полигонов (это больше соответствует вашей конкретной проблеме)

Вы также можете попробовать здесь для библиографии дополнительных работ по этому вопросу.