Существует ли алгоритм для определения смежных цветных областей в сетке?

Question

Учитывая базовую сетку (например, лист миллиметровки), где каждая ячейка была случайно заполнена одним из n цветов, существует ли проверенный и верный алгоритм, который может сказать мне, какие смежные области (группы ячеек того же цвета, которые соединяются сбоку) есть? Допустим, n - это что-то разумное, например 5.

У меня есть некоторые идеи, но все они кажутся ужасно неэффективными.

Answer 1

Наилучшим из возможных алгоритмов является O (количество ячеек), и он не связан с количеством цветов.

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

Edit:

Вот простой пример псевдокода поиска в глубину, который является простым для реализации обхода графа:

function visit(cell) {
    if cell.marked return
    cell.marked = true
    foreach neighbor in cell.neighbors {
        if cell.color == neighbor.color {
            visit(neighbor)
        }
    }
}

Answer 2

В дополнение к рекурсивному ответу рекурсии вы можете использовать стек, если рекурсия слишком медленная:

function visit(cell) {
    stack = new stack
    stack.push cell

    while not stack.empty {
        cell = stack.pop
        if cell.marked continue
        cell.marked = true
        foreach neighbor in cell.neighbors {
            if cell.color == neighbor.color {
                stack.push neighbor
            }
        }
    }
}

Answer 3

Вам может быть полезна статья в Википедии о заливке: http://en.wikipedia.org/wiki/Flood_fill

Answer 4

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

Answer 5

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

Способ использования структуры данных объединения-поиска заключается в следующем: сначала создайте структуру данных объединения-поиска с таким количеством элементов, сколько у вас есть ячеек. Затем выполните итерацию по ячейкам и union двум соседним ячейкам, если они имеют одинаковый цвет. В конце запустите find в каждой ячейке и сохраните ответ. Клетки с одинаковым find находятся в одной смежной цветной области.

Answer 6

Вы перебираете регионы по линии сканирования, переходя влево-вправо сверху вниз. Для каждой ячейки вы создаете список ячеек, совместно используемых одним и тем же объектом памяти между ячейками. Для каждой ячейки вы добавляете текущую ячейку в список (совместно с ней или созданные). Затем, если ячейка справа или снизу имеет одинаковый цвет, вы делитесь этим списком с этой ячейкой. Если в этой ячейке уже есть список, вы объединяете списки и заменяете ссылку на объект списка в каждой ячейке, указанной в списках, новым объединенным списком.

Затем в каждой ячейке находится ссылка на список, который содержит каждую смежную ячейку с этой ячейкой. Это удачно сочетает работу заливки между каждой ячейкой. Вместо того, чтобы повторять это для каждой клетки. Поскольку у вас есть списки, замена данных объединенными данными - это просто перебор списка. Это будет O (n * c), где n - количество ячеек, а c - мера соприкосновения графа. Полностью разрозненная сетка будет n раз. Полностью смежный одноцветный граф с n ^ 2 / 2.

Answer 7

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