Нахождение самого большого прямоугольника в 2D массиве

Question

Мне нужен алгоритм, который может анализировать 2D-массив и возвращать самый большой непрерывный прямоугольник.Для справки посмотрите на изображение, которое я сделал, демонстрируя мой вопрос.

Answer 1

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

Вот примерный план того, как это будет работать.

Пронумеруйте все строки в вашем изображении от 0..6, я буду работать снизу вверх.

Изучая строку 0, вы начинаете с двух прямоугольников (я предполагаю, что вас интересует только черный квадрат).Я буду ссылаться на прямоугольники, используя (x, y, width, height).Два активных прямоугольника: (1,0,2,1) и (4,0,6,1).Вы добавляете их в список активных прямоугольников.Этот список отсортирован по возрастанию координаты х.

Теперь вы закончили со строкой сканирования 0, так что вы увеличиваете свою строку сканирования.

Изучая строку 1, вы работаете вдоль строки, проверяя, есть ли у вас что-либо из следующего:

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

По мере продвижения по строке вы увидите, что у вас есть новый активный прямоугольник (0,1,8,1), мы можем увеличить один из существующих активных прямоугольников до (1,0,2,2)) и нам нужно удалить активный (4,0,6,1), заменив его двумя более узкими.Нам нужно запомнить это.Это самое большое, что мы видели до сих пор.Он заменен двумя новыми активными: (4,0,4,2) и (9,0,1,2)

Итак, при отправке строки сканирования 1 мы имеем:

• Активный список: (0,1,8,1), (1,0,2,2), (4,0,4,2), (9, 0, 1, 2)
• Наибольшее на данный момент: (4,0,6,1)

Вы продолжаете в том же духе, пока у вас не закончатся линии сканирования.

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

Надеюсь, это поможет.Это немного сложно описать.

Answer 2

Мне нравится подход к этому региону.

• Для каждой открытой точки в ARRAY
• расти на восток как можно дальше
• расти ЗАПАД насколько возможно
• увеличьте СЕВЕР насколько возможно, добавив строки
• увеличивайте ЮГ как можно дальше, добавляя строки
• сохранить полученную область для используемого начального пикселя
• После циклического прохождения каждой точки в ARRAY выберите начальный пиксель с наибольшим результатом области

... это был бы тщательный, но, возможно, не самый эффективный способ сделать это.

Полагаю, вам нужно ответить на философский вопрос "Является ли линия точек тонким прямоугольником?" Если линия == тонкий прямоугольник, вы можете оптимизировать ее следующим образом:

• Создайте второй массив целых чисел с именем LINES, который имеет те же размеры, что и ARRAY
• Перебрать каждую точку в массиве
• Определите самую длинную действительную линию к EAST, которая начинается в каждой точке, и сохраните ее длину в соответствующей ячейке LINES.
• После этого для каждой точки в ARRAY выполните цикл по LINES
• Для каждой точки в LINES определите, сколько соседей SOUTH имеют одинаковое значение длины или меньше.
• Примите южного соседа с меньшей длиной, если это увеличит площадь прямоугольника.
• Наибольший прямоугольник, использующий эту начальную точку: (Number_of_acceptable_southern_neighbors * the_length_of_longest_accepted_line)
• Поскольку вычисляется наибольшая прямоугольная площадь для каждого семени, проверьте, есть ли у вас новое максимальное значение, и сохраните результат, если вы это сделаете.
• И ... вы могли бы сделать это без выделения массива LINES, но я подумал, что использование его в моем объяснении упростило описание.
• И ... я думаю, вам нужно сделать то же самое с VERTICAL_LINES и EASTERN_NEIGHBORS, или в некоторых случаях могут пропустить большие прямоугольники, которые являются высокими и тощими. Так что, возможно, этот второй алгоритм не так уж и оптимизирован.

Используйте первый метод, чтобы проверить свою работу. Я думаю, что Кнут сказал: «... преждевременная оптимизация - корень всего зла».

НТН,

Perry

---

ADDENDUM: Несколько правок позже, я думаю, этот ответ заслуживает группового отката.

Answer 3

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

var biggestFound
for each potential rectangle:
    if area(this potential rectangle) > area(biggestFound)
        biggestFound = this potential rectangle

Тогда вам просто нужно найти потенциальные прямоугольники.

for each square in grid:
    recursive loop 1:
        if not occupied:
            grow right until occupied, and return a rectangle
            grow down one and recurse (call loop 1)

Это дублирует большую часть работы (например, вы будете переоценивать много под прямоугольников), но это должно дать вам ответ.

Редактировать

Альтернативный подход может состоять в том, чтобы начать с одного квадрата размера сетки и «вычесть» занятые квадраты, чтобы в итоге получить окончательный набор потенциальных прямоугольников. Здесь могут быть возможности оптимизации с использованием quadtree и обеспечением того, что вы сохраняете разделенные прямоугольники «по порядку», сверху вниз, слева направо, в случае, если вам нужно повторно объединить прямоугольники дальше вниз в алгоритме .

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

Я не собираюсь публиковать псевдокод для этого, потому что идея полностью экспериментальная, и я понятия не имею, будет ли результат лучше для свободной сетки пикселей;)

Системные «регионы» и «грязные прямоугольники» Windows, а также общее «временное кеширование» могут послужить хорошим источником вдохновения для большей эффективности. Есть также много трюков z-буфера, если это для графического алгоритма ...

Answer 4

Использовать подход динамического программирования. Рассмотрим функцию S (x, y) такую, что S (x, y) содержит область наибольшего прямоугольника, где (x, y) - самая нижняя правая угловая ячейка прямоугольника; x - координата строки, а y - координата столбца прямоугольника.

Например, на вашем рисунке S (1,1) = 1, S (1,2) = 2, S (2,1) = 2 и S (2,2) = 4. Но, S (3,1) = 0, потому что эта ячейка заполнена. S (8,5) = 40, что говорит о том, что самый большой прямоугольник, для которого нижняя правая ячейка (8,5) имеет площадь 40, является оптимальным решением в этом примере.

Вы можете легко написать уравнение динамического программирования для S (x, y) из значений S (x-1, y), S (x, y-1) и S (x-1, y-1) , Используя это, вы можете получить значения всех S (x, y) за время O (mn), где m и n - размерность строки и столбца данной таблицы. Как только S (x, y) известны для всех 1 <= x <= m, а для всех 1 <= y <= n нам просто нужно найти x и y, для которых S (x, y) равно самый большой; этот шаг также занимает O (MN) время. Сохраняя дополнительные данные, вы также можете найти длину стороны наибольшего прямоугольника. </p>

Общая сложность O (mn). Чтобы узнать больше об этом, прочитайте главу 15 или книгу алгоритмов Кормена, в частности, раздел 15.4.