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

Question

Допустим, у меня есть сетка блоков, 7x12.Мы используем цвета '*', '%', '@' и пустую ячейку '-'.

1 2 3 4 5 6 7
- - - - - - -  1
- - - - - - -  2
% % - - - - -  3
% % - - - - *  4 
% % - - - @ %  5
@ @ @ - - @ %  6
@ @ * * * - *  7
* * * % % % %  8 
% @ @ % * * %  9
% @ % % % % %  10
* * * % % @ @  11
* * @ @ @ @ *  12

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

В этом примере рассмотрим минимальный размер 1x4, 4x1, 2x2, поэтому значение 1x3 недопустимо, а значение 2x3 - недопустимо.Если нам нужны самые большие прямоугольники, мы находим следующее:

• 4x1 в (4,8)
• 5x1 в (3,10)
• 2x3 в (1, 3)
• 2x2 при (6,1)
• 2x2 при (1,11)
• 4x1 при (3,12)

Обратите внимание, что прямоугольники не могут находиться в пространстве друг друга, они не могут перекрываться.Например, прямоугольник 2x2 в (4,10) не упоминается, потому что он будет перекрывать прямоугольник 5x1 в (3,10).

Все они являются абсолютно допустимыми прямоугольниками: они равны или больше минимального размера ивсе блоки на прямоугольник одного цвета.

Я хочу сделать это программно.Когда вы говорите кому-то найти прямоугольники в сетке, он находит их немедленно, не задумываясь об этом.Вопрос в том, как мне написать алгоритм, который делает то же самое?

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

В интернете я вижу много вопросов о прямоугольниках, но я удивлен, что этот вопрос еще нигде не задавался.Я слишком сложно думаю, или никто никогда не хотел делать что-то подобное?

Answer 1

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

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

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

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

Answer 2

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

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

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

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

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

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

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

Answer 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 version 2) здесь , он тщательно прокомментирован. Возможно, вам придется немного адаптировать его к вашим потребностям, например, предложенным j_random_hacker.

Answer 4

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

Мы знаем, что в худшем случае мы должны посмотреть на каждый узел в сетке хотя бы один раз,Это означает, что наш худший бросок в лучшем случае - 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?
      }
  
  }
  

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

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

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

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