Существует ли алгоритм для определения смежных цветных областей в сетке?
-
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.