Existe um algoritmo para determinar as regiões coloridas contíguos em uma grade?
-
19-08-2019 - |
Pergunta
Dada uma rede básica (como um pedaço de papel gráfico), onde cada célula tem sido preenchida aleatoriamente com um de n cores, existe um algoritmo testado e comprovado por aí que pode me dizer o que as regiões contíguas (grupos de células da mesma cor que são unidos ao lado) existem? Vamos dizer que n é algo razoável, como 5.
Eu tenho algumas idéias, mas todos sentimos terrivelmente ineficiente.
Solução
O melhor algoritmo possível é O (número de células), e não está relacionado com o número de cores.
Isto pode ser conseguido por iteração através das células, e cada vez que você visita um que não tenha sido marcado como visitado, fazer um percurso gráfico para encontrar todas as células contíguas naquela região, e depois continuar a iteração.
Editar:
Aqui está um exemplo de código pseudo simples de uma primeira busca em profundidade, que é um fácil de implementar gráfico travessia:
function visit(cell) {
if cell.marked return
cell.marked = true
foreach neighbor in cell.neighbors {
if cell.color == neighbor.color {
visit(neighbor)
}
}
}
Outras dicas
Além de resposta recursiva de recursiva, você pode usar uma pilha se recursão é muito lento:
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
}
}
}
}
Você poderia tentar fazer um preenchimento em cada quadrado. Como os spreads de inundação, gravar as quadrículas em uma matriz ou algo assim, e cor-los em uma cor não utilizado, diz-1.
O artigo da Wikipedia sobre preenchimento de inundação pode ser útil para você aqui: http: //en.wikipedia. org / wiki / Flood_fill
União-encontrar iria trabalhar aqui também. Na verdade, você pode formular a sua pergunta como um problema sobre um gráfico: os vértices são as células da grade, e dois vértices são adjacentes se suas células da grade têm a mesma cor. Você está tentando encontrar os componentes ligados.
A maneira como você usaria uma estrutura de dados união-descoberta é o seguinte: primeiro criar uma estrutura de dados união-achado com tantos elementos como você tem células. Então iteração através das células, e union
duas células adjacentes, se eles têm a mesma cor. No final, executar find
em cada célula e armazenar a resposta. As células com a mesma find
estão na mesma região contígua de cor.
Se você quiser um controle de grãos pouco mais fino, você pode pensar sobre o uso do A * algoritmo e utilizar a heurística para incluir telhas coloridas semelhantes.
Você interagir através das regiões em uma linha de varredura, indo de cima para baixo esquerda-direita. Para cada célula que você faça uma lista de células compartilhadas como o mesmo objeto de memória entre as células. Para cada célula, você adicionar a célula atual à lista (seja compartilhado com ele ou criado). Então, se a célula à direita ou abaixo é a mesma cor, você compartilhar essa lista com essa célula. Se essa célula já tem uma lista, você combinar as listas e substituir a referência ao objeto de lista em cada célula apareça nas listas com o novo lista mesclada.
Em seguida, localizado em cada célula é uma referência a uma lista que contém todas as células contíguas com essa célula. Este apropriadamente combina o trabalho do floodfill entre cada célula. Em vez de repetir que para cada célula. Desde que você tem as listas substituindo os dados com os dados mesclado é apenas iteração através de uma lista. Será O (N * c) em que n é o número de células e c é uma medida de como o gráfico é contígua. Uma grade completamente desarticulada será n tempo. Um gráfico de uma cor completamente contígua com estar n ^ 2/2.