Поиск прямоугольников в блоке 2d блоков

Ответ 1

Вызовите ширину и высоту входного массива W и H соответственно.

• Запустите этот умный алгоритм O (WH) для определения самого большого прямоугольника, но вместо отслеживания только самого большого прямоугольника для каждого (x, y) запись в матрице W * H ширины и высоты (одного или всех) наибольших прямоугольников, верхний левый угол которых (x, y), обновляющий эти значения по мере продвижения.
• Прокрутите эту матрицу, добавив в нее каждый достаточно большой прямоугольник в max-heap, упорядоченный по области (ширина * высота).
• Прочитайте записи из этой кучи; они будут производиться в порядке убывания площади. С каждой записью, чей верхний левый угол (x, y) и ширина ширины w и высота h, отметьте каждое из мест, включенных в прямоугольник, как "использовано" в массиве бит WH. При чтении прямоугольников из кучи мы должны отбросить любые прямоугольники, которые содержат "используемые" квадраты, чтобы избежать создания перекрывающихся прямоугольников. Достаточно проверить только четыре ребра каждого прямоугольника-кандидата по отношению к "использованному" массиву, поскольку единственным другим способом, которым прямоугольник-кандидат мог бы перекрывать другой прямоугольник, было бы, если бы последний прямоугольник был полностью сложен им, что невозможно из-за факт, что мы читаем прямоугольники в порядке убывания площади.

Этот подход является "жадным", поскольку он не гарантирует выбор самой большой последовательности прямоугольников в целом, если существует несколько способов вырезать сплошную окрашенную область в максимальные прямоугольники. (Например, может быть, есть несколько прямоугольников, верхний левый угол которых находится в (10, 10) и которые имеют площадь 16: 16x1, 8x2, 4x4, 2x8, 1x16. В этом случае один выбор может привести к появлению больших прямоугольников "downstream", но мой алгоритм не гарантирует, что вы сделаете этот выбор.) При необходимости вы можете найти эту общую оптимальную серию прямоугольников с использованием обратного отслеживания, хотя я подозреваю, что это может быть очень медленным в худшем случае.

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

Ответ 2

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

Мы знаем, что в худшем случае мы должны рассматривать каждый node в сетке хотя бы один раз. Это означает, что наилучшим примером наилучшего результата является O(len*wid).

Ваша грубая сила будет O(len*len*wid*wid) с наивным подходом "Проверка прямоугольников в точке O(len*wid), и вы делаете это O(len*wid) раз.

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

Основной алгоритм:

for(x = 1 .. wid) {
    for(y = 1 .. len) {
        Rectangle rect = biggestRectOriginatingAt(x,y);
        // process this rectangle for being added
    }
}

• Следите за наибольшими прямоугольниками k. По мере продвижения вы можете искать по периметру, где может быть подходящий прямоугольник.

  Rectangle biggestRectOriginatingAt(x,y) {
      area = areaOf(smallestEligibleRectangle); // if we want the biggest k rect's, this
                                                // returns the area of the kth biggest
                                                // known rectangle thus far
  
      for(i = 1 .. area) {
          tempwid = i
          templen = area / i
  
          tempx = x + tempwid
          tempy = y + templen
  
          checkForRectangle(x,y,tempx,tempy); // does x,y --> tempx,tempy form a rectangle?
      }
  
  }
  

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

Это также не работает для более случайных распределений.

• Другая оптимизация - использовать алгоритм заполнения красок, чтобы найти самые большие последовательные области. Это O(len*wid), что является небольшой стоимостью. Это позволит вам искать наиболее вероятные области для большого прямоугольника.

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

Ответ 3

Мне пришлось решить очень похожую проблему для моего шутера от первого лица. Я использую это для ввода:
[   ] [   ] [   ] [   ] [   ] [   ] [   ] [   ] <бр/" > [   ] [   ] [   ] [X] [   ] [   ] [   ] [   ]
[   ] [X] [X] [X] [X] [X] [X] [X]
[   ] [   ] [X] [X] [X] [X] [   ] [   ]
[   ] [X] [X] [X] [X] [   ] [   ] [   ]
[   ] [X] [X] [X] [X] [   ] [   ] [   ]
[   ] [   ] [X] [   ] [   ] [   ] [   ] [   ]
[   ] [   ] [   ] [   ] [   ] [   ] [   ] [   ] <бр/" >
Я получаю это на выходе:
[   ] [   ] [   ] [   ] [   ] [   ] [   ] [   ] <бр/" > [   ] [   ] [   ] [A] [   ] [   ] [   ] [   ]
[   ] [B], [G], [G], [G], [F], [E] [E]
[   ] [   ] [G], [G], [G], [F], [   ] [   ]
[   ] [D], [G], [G], [G], [   ] [   ] [   ]
[   ] [D], [G], [G], [G], [   ] [   ] [   ]
[   ] [   ] [C], [   ] [   ] [   ] [   ] [   ]
[   ] [   ] [   ] [   ] [   ] [   ] [   ] [   ] <бр/" >
Эта схема лучше. Исходный код (в соответствии с GNU General Public License версии 2) здесь, он сильно комментируется. Возможно, вам придется немного приспособить его к вашим потребностям, например, предложенному j_random_hacker.

Ответ 4

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

Ссылка на источники С++

Он найдет меньше прямоугольников, чем принятый ответ, потому что мне трудно принять этот алгоритм, чтобы сохранить каждый промежуточный прямоугольник при поиске самого большого. Алгоритм пропускает все меньшие прямоугольники, поэтому мы должны проходить через каждую точку в нашей сетке, чтобы сохранить каждый прямоугольник, а затем отбросить меньшие, и это перевернет алгоритм до сложности O (M³ ⋅ N³).

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

    ****|***|***                ************
    ****|***|***                ************
    ****#####***                ----#####---
    ****#####***        vs      ****#####***
    ****#####***                ----#####---
    ****|***|***                ************

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

Редактирование: я просто понял, что рекурсивно проверять оба варианта расщепления повышает алгоритм до факторной сложности, что-то вроде O (min (M, N)!). Поэтому я отключил разделение второй области, что оставляет алгоритм со сложностью вокруг O (M⋅N⋅log (M⋅N)).