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

StackOverflow https://stackoverflow.com/questions/452480

  •  19-08-2019
  •  | 
  •  

Вопрос

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

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

Это было полезно?

Решение

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

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

Редактировать:

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

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

Другие советы

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

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
            }
        }
    }
}

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top