Слияние и разбиение перекрывающихся прямоугольников для получения неперекрывающихся прямоугольников

Я ищу следующий алгоритм:

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

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

Существуют ли известные методы для это / идеи / указатели?

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

2 3
algorithm rectangles mathematical-optimization computational-geometry

2 ответа:

Что-то, основанное на алгоритме линейной развертки, будет работать, я думаю:

  • отсортируйте все координаты ваших прямоугольников min и max x в массив, как события" start-rectangle "и" end-rectangle "
  • Шаг через массив, добавляя каждый новый встреченный прямоугольник (start-event) в текущий набор
  • одновременно поддерживайте набор "неперекрывающихся прямоугольников", который будет вашим выходным набором
  • каждый раз, когда вы сталкиваетесь с новым прямоугольником, вы можете проверить, является ли он полностью содержится уже в текущем / выходном наборе (достаточно простого сравнения y-координат)
  • Если это не так, добавьте новый прямоугольник в свой выходной набор, с y-координатами, установленными на ту часть нового прямоугольника, которая еще не покрыта.
  • каждый раз, когда вы попадаете в событие окончания прямоугольника, остановите все прямоугольники в вашем выходном наборе, которые больше ничего не покрывают.

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

7

Итак, если бы я попытался сделать это, первое, что я сделал бы, - это придумал бы единое сеточное пространство. Найдите все уникальные координаты x и y и создайте сопоставление с индексным пространством. Таким образом, если у вас есть значения x { -1, 1.5, 3.1}, то сопоставьте их с { 0, 1, 2}, а также для y. тогда каждый прямоугольник может быть точно представлен этими упакованными целочисленными координатами.

Затем я бы выделил битвектор или что-то, что покрывает всю сетку, и растеризовал бы ваши прямоугольники в сетке. Ницца дело в том, что с сеткой действительно легко работать, и, ограничивая ее уникальными координатами x и y, она минимальна и точна.

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

Давайте посмотрим на 4 соседних пикселя, маленький квадрат 2x2. Когда я пишу алгоритмы, подобные этим, обычно я думаю в терминах вершин, ребер и граней. Итак, это лица вокруг Верта. Если 3 из них включены, а 1 выключен, то у вас есть вогнутый угол. Это единственный недопустимый случай. Например, если у меня нет вогнутых углов, я просто хватаю экстенты и сбрасываю все это как один прямоугольник. Для каждого вогнутого угла вам нужно решить, разделять ли его по горизонтали, вертикали или и то, и другое. Я думаю о расщеплении как о маркировке краев, которые нельзя пересекать при поиске экстентов. Вы также можете сделать это как раскрашивание в наборы, что для вас проще.

Вогнутые углы и их расщепленные направления-это ваше пространство поиска.. вы можете использовать любой алгоритм оптимизации, который вам нравится. Ответвление / привязка может работать хорошо. Держу пари, что вы можете найти простую эвристику, которая хорошо работает (например, если есть еще один вогнутый угол прямо напротив того, который вы рассматриваете, всегда разделяйте в этом направлении. В противном случае разделите на более короткие направление). Ты можешь просто пожадничать. Или вы можете просто разделить каждый вогнутый Верт в обоих направлениях, что обычно даст вам меньше прямоугольников, чем вывод каждого "пикселя" в виде прямой линии, и будет довольно просто.

Перечитывая это, я понимаю, что могут быть неясные области. Дайте мне знать, если вы хотите, чтобы я что-нибудь прояснил.

1