Как эффективно найти открытый прямоугольник с определенным размером?

Фон

У меня прямоугольная область, разделенная на квадраты (это для игры, которую я делаю). Я представляю это в своем коде как простой двумерный массив boolean:

  ┌──┬──┬──┬──┬──┐
  │  │  │  │  │  │ X = X-value, also increasing width
  ├──┼──┼──┼──┼──┤ Y = Y-value, also increasing length
  │  │  │  │  │  │
  ├──┼──┼──┼──┼──┤
  │  │  │  │  │  │
  ├──┼──┼──┼──┼──┤
  │  │  │  │  │  │
  ├──┼──┼──┼──┼──┤
^ │  │  │  │  │  │
Y └──┴──┴──┴──┴──┘
   X >

Некоторые квадраты могут быть помещены в прямоугольники зданиями и т.д., как этот вход (**= взято):

┌──┬──┬──┬──┬──┐
│**│**│  │  │  │ 3 taken rectangles
├──┼──┼──┼──┼──┤
│**│**│**│**│  │
├──┼──┼──┼──┼──┤
│  │  │**│**│  │
├──┼──┼──┼──┼──┤
│  │  │**│**│  │
├──┼──┼──┼──┼──┤
│**│  │**│**│  │
└──┴──┴──┴──┴──┘

В массиве 2D boolean квадраты "взяты" установлены на true, а квадраты "открытые, незанятые" равны false.

Моя проблема

Мне нужно найти все "открытые" прямоугольники (не взятые), которые имеют определенный размер. Это потому, что мне нужно найти все возможные пространства, чтобы поставить следующее здание. Например, из предыдущего рисунка, если бы я хотел получить все "открытые" прямоугольники 1x2, я должен получить эти выходы:

┌──┬──┬──┬──┬──┐
│**│**│1 │12│2 │ 3 taken rectangles (input)
├──┼──┼──┼──┼──┤ 4 open 1x2 rectangles (output)
│**│**│**│**│  │ Open rectangles are numbered
├──┼──┼──┼──┼──┤ 
│3 │3 │**│**│  │ Rectangles can overlap.
├──┼──┼──┼──┼──┤ The '12' square represents the overlapping
│4 │4 │**│**│  │ of rectangle 1 and 2.
├──┼──┼──┼──┼──┤ 
│**│  │**│**│  │ (Haha, my diagram kind of looks like old Minesweeper)
└──┴──┴──┴──┴──┘

Что я сделал

Здесь я тестировал (поиск грубой силы, код С# и бит псевдокода):

List<Rectangle> findOpenSpaces(boolean[][] area, int width, int length) {
    List<Rectangle> openSpaces = new List<Rectangle>();
    boolean open = true;
    // Loop through all rectangles with size "width" and "length"
    for x = 0 to (total area length) - length {
        for y = 0 to (total area width) - width {
            // Check this rectangle to see if any squares are taken
            Rectangle r = new Rectangle(x, y, width, length);
            if checkRectangle(area, r) returns true {
                // rectangle was fully open, add to the list
                openSpaces.Add(r);
            }
        }
    }
    return openSpaces;
}

boolean checkRectangleIsOpen(boolean[][] area, Rectangle r) {
    for i = r.x to r.width {
        for j = r.y to r.length {
            if area[i][j] is true {
                // means that this square in the rectangle is taken,
                // thus the rectangle is not fully open
                // so return false (not open)
                return false;
            }
        }
    }
    return true; // no square in the rectangle was taken
}

struct Rectangle { // just a struct to help store values
    int x, y, width, length;
}

Вопрос

Вышеприведенный (псевдо) код работает, но если вы посмотрите на него, время приходит к O(n^4):( (я думаю, из-за четырех вложенных циклов for, но я не эксперт)., в игре общая площадь прямоугольной области 50x50, а не 5x5, как и мои примеры здесь. Игра заметно заметна всякий раз, когда я делаю эту операцию.

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

Ответы

Ответ 1

Некоторое быстрое мышление покажет, что вы просто не можете сделать это быстрее, чем O(NM), потому что есть как минимум много возможных выходов. У вас уже есть решение O(N^2M^2), поэтому давайте посмотрим, найдем ли мы O(NM).

Что бы я сделал, вместо поиска местоположений, которые могут образовать прямоугольник размером a x b, найдите местоположения, которые не могут.

То есть, что-то вроде этого (псевдокод):

for each taken square:
    for each rectangle starting position:
        if rectangle at starting position includes this taken square,
            mark starting position as non-tenable

Если ваши прямоугольники маленькие (например, пример 1x2, который у вас был выше), это (эффективно реализовано) вполне достаточно. Однако для подхода, который не полагается на размер прямоугольников для асимптотической скорости.,.

Рассмотрим, что выполняется (x,y). Тогда прямоугольники, которые перекрываются с этой точкой, образуют прямоугольник самостоятельно, и ничто в этом диапазоне не может быть использовано. Поэтому мы хотим отметить (дискретный) диапазон как непригодный для использования. Это можно сделать с помощью 2-D дерева Fenwick, стоимость которого составляет O(log N log M) за обновление или запрос. Чтобы отметить диапазон (x1, y1, x2, y2) как "в использовании", мы:

Приращение (x1, y1) одним
Уменьшение (x1, y2) на один
Уменьшение (x2, y1) на один
Приращение (x2, y2) одним

Итак, мы закончили выполнение четырех операций 2D-дерева Фенвика на один квадрат, из которых не более O(NM). Затем, когда мы закончим, мы проверяем каждое значение каждой возможной исходной позиции: если оно равно нулю, это допустимое место для запуска. Если он отличен от нуля, его нельзя использовать.

Общая стоимость: O(NM log N log M). В то время как вы, скорее всего, сделаете это быстрее, соотношение скорости и размера реализации для этого подхода чрезвычайно хорошо (для двухмерного дерева Фенвика используется примерно десять строк).

Ответ 2

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

Что, если вместо массива или матрицы вы программируете ящик как класс со ссылками на соседние объекты. При запуске вашей игры у вас есть довольно занятый процесс построения строк со всеми перекрестными ссылками на соседние поля.

Но тогда во время игры вы обновляете только один квадрат + (соседи * с определенным размером окна) за раз.
Если размер заданного размера больше 2 - или вы заботитесь о нескольких размерах - это может быть много повторений, но значительно меньше, чем вложенные петли всех ящиков.

Если вы хотите найти "пустоту" по всей сетке, вам нужно будет только вызвать функцию один раз на каждом поле, так как ответ был сохранен заранее как состояние объекта-контейнера.

Ответ 3

Вот решение, которое использует динамическое программирование и теорию множеств для сокращения временной сложности: -

1. Evaluate Free[i][j] which counts all free tiles in rectangle (i,j) to (n,n).
2. Rect[i][j] is whether there is rectangle (h,w) starting at (i,j).
3. Count[i][j] = Free[i][j] - Free[i][j+w] - Free[i+h][j] + Free[i+h][j+w]
4. Rect[i][j] = (Count[i][j] == h*w)

Сложность времени: -

Free[i][j] можно снова оценить с помощью DP: -

Free[i][j] = Row[i][j]+Col[i][j]+Free[i+1][j+1] где Row[i][j] - количество свободных фрагментов в строке i от j и далее Col[i][j] засчитывается в col j от i и далее. Как массив Col, так и Row можно оценить в O(NM) с помощью DP. Поэтому после предварительного вычисления Col & Row вы можете оценить Free[i][j] в O(NM).

Rect[i][j] можно оценить в O(NM) после предварительного вычисления Free[i][j].

Total Complexity : O(NM)