Existe um algoritmo para determinar as regiões coloridas contíguos em uma grade?

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

O artigo da Wikipedia sobre preenchimento de inundação pode ser útil para você aqui: http: //en.wikipedia. org / wiki / Flood_fill

Answer 5

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.

Answer 6

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.

Answer 7

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.