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

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

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

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

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

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

68
задан Peter O. 22 November 2016 в 12:50
поделиться