Поиск смежных областей битов в двумерном битном массиве

Проблема

У меня есть бит-массив, который представляет собой двумерную "карту" "плиток". Это изображение представляет собой графический пример бит в массиве бит:

Мне нужно определить, сколько смежных "областей" бит существует в массиве. В приведенном выше примере есть две такие смежные "области", как показано здесь:

Плитки должны быть расположены непосредственно N, S, E или W плитки, которые считаются "смежными". Диагонально трогательные плитки не учитываются.

Что у меня до сих пор

Поскольку эти битовые массивы могут стать относительно большими (несколько мегабайт), я намеренно избегал использования какой-либо рекурсии в моем алгоритме.

Псевдокод выглядит следующим образом:

LET S BE SOURCE DATA ARRAY
LET C BE ARRAY OF IDENTICAL LENGTH TO SOURCE DATA USED TO TRACK "CHECKED" BITS
FOREACH INDEX I IN S
    IF C[I] THEN 
        CONTINUE 
    ELSE
        SET C[I]
        IF S[I] THEN
            EXTRACT_AREA(S, C, I)

EXTRACT_AREA(S, C, I):
    LET T BE TARGET DATA ARRAY FOR STORING BITS OF THE AREA WE'RE EXTRACTING
    LET F BE STACK OF TILES TO SEARCH NEXT
    PUSH I UNTO F
    SET T[I]
    WHILE F IS NOT EMPTY
        LET X = POP FROM F
        IF C[X] THEN 
            CONTINUE
        ELSE
            SET C[X]
            IF S[X] THEN
                PUSH TILE NORTH OF X TO F
                PUSH TILE SOUTH OF X TO F
                PUSH TILE WEST OF X TO F
                PUSH TILE EAST OF X TO F
                SET T[X]
    RETURN T

Что мне не нравится в моем решении

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

Что я хотел бы видеть

Улучшенный профиль памяти
Более быстрая обработка больших площадей.

Решение/последующее наблюдение

Я повторно написал решение, чтобы исследовать только края (за каждое предложение @hatchet).

Это было очень просто реализовать - и устраняли необходимость полностью отслеживать "посещенные плитки".

Основываясь на трех простых правилах, я могу пересекать края, отслеживать значения min/max x и y и заканчивать, когда я снова прихожу к началу.

Здесь демо с тремя правилами, которые я использовал:

Ответ 1

Одним из подходов будет периметр. Помните эту точку с учетом начальной точки в любом месте по краю фигуры.

Начните ограничительную рамку как только эту точку.

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

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

Продолжайте, пока не будет достигнута начальная точка.

Минусы: если в форме много одиночных пиксельных "нитей", вы будете пересматривать их по мере того, как возвращается прогулка.

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

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

Edit

Как это часто бывает, эта проблема известна, называется и имеет множество алгоритмических решений. Проблема, которую вы описали, называется минимальным ограничивающим прямоугольником. Один из способов решить эту проблему - Контурная трассировка. Метод, описанный выше, находится в этом классе и называется Moore-Neighbor Tracing или Радиальная развертка. Ссылки, которые я включил для них, подробно обсуждают их и указывают на проблему, которую я не поймал. Иногда вы переходите к начальной точке, прежде чем пройдете весь периметр. Если ваша начальная точка, например, где-то рядом с "нитью" с одним пикселем, вы пересматриваете ее до того, как вы закончите, и если вы не рассмотрите эту возможность, вы остановитесь преждевременно. Веб-сайт, на котором я ссылался, рассказывает о способах решения этой проблемы. Другие страницы этого сайта также говорят о двух других алгоритмах: Square Tracing и Theo Pavlidis Algorithm. Следует отметить, что они рассматривают диагонали как смежные, в то время как вы этого не делаете, но это должно быть просто что-то, с чем можно справиться с незначительными изменениями в основных алгоритмах.

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

Дополнительный ресурс:

Алгоритм отслеживания контура морфа в С++

Ответ 2

У меня действительно был такой вопрос в одном интервью.

Вы можете притворяться, что массив представляет собой график, а связанные узлы - смежные. Мой алгоритм будет включать в себя переход 1 вправо, пока вы не найдете отмеченный node. Когда вы обнаружите, что каждый делает первый поиск по ширине, который работает в O (n), и избегает рекурсии. Когда BFS возвращает поиск с того места, где вы остановились, и если node уже отмечен одной из предыдущих BFS, вам явно не нужно искать. Я не был уверен, хотите ли вы фактически вернуть количество найденных объектов, но легко отслеживать, просто увеличивая счетчик, когда вы нажмете первый отмеченный квадрат.

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

Один хакерский способ уменьшить потребление памяти будет слишком хранить short[][] вместо логического. Затем используйте эту схему, чтобы избежать создания целого второго 2d-массива

unmarked = 0, отмечен = 1, отмечен и не отмечен = 3, отмечен и отмечен = 3

Таким образом вы можете проверить статус записи по ее значению и избежать создания второго массива.