Алгоритм нахождения наименьшего количества прямоугольников для покрытия набора прямоугольников без перекрытия
У меня есть набор прямоугольников, и я хотел бы "уменьшить" набор, чтобы у меня было наименьшее количество прямоугольников для описания той же области, что и исходный набор. Если возможно, я хотел бы, чтобы это было быстро, но меня больше беспокоит получение количества прямоугольников как можно меньше. У меня есть подход, который работает большую часть времени.
В настоящее время я начинаю с самого верхнего левого прямоугольника и вижу, могу ли я развернуть его вправо и вниз, сохраняя его прямоугольником. Я так и делаю пока он больше не сможет расширяться, удалите и разделите все пересекающиеся прямоугольники и добавьте расширенный прямоугольник обратно в список. Затем я снова начинаю процесс со следующего самого верхнего левого прямоугольника и так далее. Но в некоторых случаях это не работает. Например:
с этим набором из трех прямоугольников, правильное решение будет в конечном итоге с двумя прямоугольниками, как это:
однако в этом случае мой алгоритм начинается с обработки синего прямоугольника. Это расширяется вниз и разбивает желтый прямоугольник (правильно). Но затем, когда остальная часть желтого прямоугольника обрабатывается, вместо того, чтобы расширяться вниз, он сначала расширяется вправо и возвращает часть, которая была ранее отколота. Затем обрабатывается последний прямоугольник, и он не может расширяться вправо или вниз, поэтому исходный набор прямоугольников остается слева. Я мог бы настроить алгоритм, чтобы сначала развернуть его вниз, а затем вправо. Это исправит этот случай, но это вызовет ту же проблему в аналогичном сценарии, который был переворачивать.
Edit: просто чтобы уточнить, исходный набор прямоугольников не перекрываются и не должны быть связаны. И если подмножество прямоугольников связано, то полигон, который полностью их покрывает, может иметь в нем отверстия.
2 ответа:
несмотря на название вашего вопроса, я думаю, что вы на самом деле ищете минимум рассечение в прямоугольники прямолинейного многоугольника. (Ссылки Джейсона о минимуме крышки по прямоугольникам, что совсем другая проблема.)
Дэвид Эпштайна Расположе обсуждает эту проблему в разделе 3 своей обзорной статьи 2010 года теоретико-графовые решения задач вычислительной геометрии, и он дает хорошее резюме в этот ответ на mathoverflow.net:
идея в том, чтобы найти максимальное количество оси-параллельными непересекающимися диагоналями двух вогнутых вершин на концах, разделенный вдоль, и затем еще один сплит для каждого оставшегося вогнутой вершиной. Чтобы найти максимальное число осей-параллельных непересекающихся диагоналей, форма графика пересечения диагоналей; этот граф-двудольный, поэтому его максимальном независимом множестве можно найти за полиномиальное время по паросочетание методы.
вот мой лоск на этом восхитительно кратком описании, используя Рисунок 2 из статьи Эппштейна. Предположим, что мы имеем прямолинейный многоугольник, возможно, с отверстиями.
когда многоугольник рассекается на прямоугольники, каждая из вогнутых вершин должна быть встречена по крайней мере одним краем рассечения. Так что мы получаем минимум рассечение, если как можно больше этих краев выполняют двойную работу, то есть они соединяют два из них вогнутые вершины.
Итак, давайте нарисуем ось-параллельна диагонали между двумя вогнутыми вершинами, которые находятся полностью внутри полигона. (Здесь "ось-параллель "означает" горизонтальная или вертикальная", а диагональ многоугольника - это линия, соединяющая две несмежные вершины.) Мы хотим использовать как можно больше этих линий в разрезе, пока они не пересекаются.
(Если нет оси-параллельными диагоналями, в рассечение тривиально-просто сделайте разрез от каждой вогнутой вершины. Или, если нет пересечений между осепараллельными диагоналями, мы используем их все, а также вырез из каждой оставшейся вогнутой вершины. В противном случае, читайте дальше.)
The график перекрестке из набора сегментов линии имеет узел для каждого сегмента линии, и ребро соединяет два узла, если линии пересекаются. Вот график пересечения для оси-параллели диагонали:
Это двудольные с вертикальными диагоналями в одной части и горизонтальными диагоналями в другой части. Теперь мы хотим выбрать как можно больше диагоналей, пока они не пересекаются. Это соответствует нахождению максимальный независимый набор в графе перекрестке.
нахождение максимального независимого множества В общем графе является NP-трудной задачей, но в частном случае a двудольный граф, теорема Кенига показывает, что это эквивалентно задаче нахождения максимального соответствия, которая может быть решена за полиномиальное время, например, с помощью алгоритм Хопкрофта–карпа. Данный график может иметь несколько максимальных соответствий, но любой из них будет делать, так как все они имеют одинаковый размер. В Примере все максимально сравнения имеют три пары вершин, например {(2, 4), (6, 3), (7, 8)}:
(другие максимальные совпадения в этом графике включают {(1, 3), (2, 5), (7, 8)}; {(2, 4), (3, 6), (5, 7)}; и {(1, 3), (2, 4), (7, 8)}.)
чтобы получить от максимального соответствия к соответствующему минимального вершинного покрытия применить доказательство теоремы Кенига. В приведенном выше сопоставлении левый набор равен L = {1, 2, 6, 7}, правильный набор является R = {3, 4, 5, 8}, и набор непревзойденных вершин в L и U = {1}. Существует только один переменный путь, начинающийся в U, а именно 1-3-6, поэтому множество вершин в чередующихся путей Z = {1, 3, 6} и, таким образом, минимальное покрытие вершины K = (L\ Z) ∪ (R ∩ Z) = {2, 3, 7}, показано красным цветом ниже, с максимальным независимым набором в зеленом цвете:
переводя это обратно в проблему рассечения, это означает, что мы можем использовать пять оси-параллельные диагонали в разрезе:
наконец, сделайте разрез из каждой оставшейся вогнутой вершины, чтобы завершить рассечение:
вот некоторые научные статьи, обсуждающие решения этой проблемы;
алгоритм линейно-временной аппроксимации для минимального прямоугольного покрытия (это для покрытия полигонов, так что это более общий случай, чем то, что вы тут представили).
оптимальные прямоугольные покрытия для выпуклых прямолинейных полигонов (это один больше по линии вашей конкретной проблемы)
вы также можете попробовать здесь для a библиография других работ по этой теме.