Как я могу найти все прямоугольники, которые связывают области в растровом изображении?

У меня проблема: мне нужен алгоритм для моего движка плиток.

У меня есть 2d-массив, в котором хранятся мои неприступные плитки.

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

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

Мне нужен набор прямоугольников, которые ограничивают неприступные части массива (ячейки, которые имеют 1s)
Например:

http://makerland.de/Zerlegt.png

Черная плитка 1s; Мне нужно найти множество красных прямоугольников, которые полностью их заключают.

Источник

2 ответа

Решение

После дальнейших размышлений я нашел более быстрое решение:

  1. Создать неизменный Range структурировать с StartX, StartY, а также EndY свойства.

  2. Поддерживать разреженный массив тока Ranges, с длиной, равной высоте изображения, и единственной переменной currentRange со значением NULL. Этот массив будет содержать диапазон, если он есть, который начинается с каждой координаты Y

  3. Для каждого столбца

    1. Очистить currentRange

    2. Для каждой ячейки в столбце:

      1. Если не существует currentRange, или если есть, но он закончился до этой ячейки (если currentRange.EndY <= y), установите currentRange на yэлемент в массиве диапазонов.
        Таким образом, currentRange всегда будет ссылаться на диапазон, который содержит текущую ячейку, или null если текущая ячейка не находится в диапазоне.

      2. Если текущая ячейка 1:

        1. Если мы находимся в диапазоне, ничего не делаем - диапазон продолжается в следующем столбце.

        2. Если мы не находимся в пределах досягаемости, перебираем колонку, пока не достигнем 0 или конец столбца, а затем создать новый диапазон, растягиваясь от 1 мы только что нашли до конца цикла.
          Затем перейдите к следующему if (так как текущая ячейка сейчас 0 или конец столбца, и мы не в диапазоне)
          Если вы нажмете существующий диапазон, когда создаете новый диапазон, вы можете либо остановить новый диапазон, и оставить существующий диапазон ниже его (лучше всего для нечетких краев), либо закрыть существующий диапазон (см. Ниже) и позволить новый диапазон растягивается вниз, чтобы перенять существующий диапазон.

      3. Если текущая ячейка 0:
        1. Если мы находимся в диапазоне, закройте диапазон:
          1. Вернуть новый прямоугольник, растягивающийся от начала X и Y диапазона до текущего Y и конца X диапазона.
          2. Очистить диапазон из массива активных диапазонов.

Этот алгоритм O(x * y) в вычислениях и O(y) в космосе. Я считаю, что это самое быстрое решение проблемы.

Вы также можете вращать этот алгоритм и сканировать строки, а не столбцы (чтобы диапазоны были растянуты вниз, а не вправо), что будет O(x) в хранилище.

Вот реализация C#:

class BoxFinder {
    class Range {
        public Range(int startX, int startY, int endY) {
            StartX = startX;
            StartY = startY;
            EndY = endY;
        }

        public int StartX { get; private set; }
        public int StartY { get; private set; }
        public int EndY { get; private set; }
    }
    public BoxFinder(int[,] data) {
        Data = data;
        Width = data.GetLength(0);
        Height = data.GetLength(1);
        ranges = new Range[Height];
    }

    public int[,] Data { get; private set; }
    public int Width { get; private set; }
    public int Height { get; private set; }

    private Range[] ranges;
    public IEnumerable<Rectangle> GetBoxes() {
        for (int x = 0; x < Width; x++) {
            Range currentRange = null;
            for (int y = 0; y < Height; y++) {
                Func<Range, Rectangle> CloseRange = r => {
                    currentRange = null;
                    ranges[r.StartY] = null;
                    return new Rectangle(
                        r.StartY,
                        r.StartX,
                        x - r.StartX,
                        r.EndY - r.StartY
                    );
                };

                if (currentRange == null || currentRange.EndY <= y)
                    currentRange = ranges[y];

                if (Data[x, y] == 1) {
                    if (currentRange == null) {
                        int startY = y;
                        for (; y < Height && Data[x, y] == 1; y++) {
                            if (ranges[y] != null)
                                yield return CloseRange(ranges[y]);
                            //If there are fuzzy edges, break; instead
                        }
                        ranges[startY] = new Range(x, startY, y);
                        if (y == Height)
                            continue;
                        //Otherwise, continue to the next if in case a previous range just ended
                    }
                }
                //No else; we can get here after creating a range
                if(Data[x, y] == 0) {
                    if (currentRange != null)
                        yield return CloseRange(currentRange);
                }
            }
        }
    }
}
Источник

Попробуйте что-то вроде этого:

  1. Создайте список, содержащий каждую желаемую точку. (В вашем случае координаты каждого 1)

  2. Для каждой точки в этом списке:

    1. Зацикливайте ось Y от этой точки до тех пор, пока не достигнете нежелательной точки (0)
    2. Зацикливайтесь прямо вдоль оси X, пока не достигнете координаты X, которая имеет 0 при любом значении Y между точкой и конечной координатой Y, полученной на шаге 1.
    3. Добавьте только что найденный прямоугольник в список прямоугольников
    4. Удалите каждую точку в прямоугольнике из исходного списка.

Это, вероятно, не самый быстрый способ сделать это, но он должен работать.

Источник
Другие вопросы по тегам