Esiste un algoritmo per determinare regioni colorate contigue in una griglia?

Question

Data una griglia di base (come un pezzo di carta millimetrata), in cui ogni cella è stata riempita casualmente con uno di n colori, esiste un algoritmo provato e reale che può dirmi quali regioni contigue (gruppi di celle dello stesso colore che sono uniti ai lati) ci sono? Diciamo che n è qualcosa di ragionevole, come 5.

Ho alcune idee, ma si sentono tutti terribilmente inefficienti.

Answer 1

Il miglior algoritmo possibile è O (numero di celle) e non è correlato al numero di colori.

Questo può essere ottenuto iterando attraverso le celle e ogni volta che visiti una che non è stata contrassegnata come visitata, esegui un attraversamento grafico per trovare tutte le celle contigue in quella regione e quindi continua iterando.

Modifica:

Ecco un semplice esempio di pseudo codice di una prima ricerca approfondita, che è un traversal grafico facile da implementare:

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

Answer 2

Oltre alla risposta ricorsiva ricorsiva, puoi usare uno stack se la ricorsione è troppo lenta:

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

Potresti provare a fare un riempimento di piena su ogni quadrato. Mentre l'inondazione si diffonde, registra i quadrati della griglia in una matrice o qualcosa del genere e colorali con un colore inutilizzato, ad esempio -1.

Answer 4

L'articolo di Wikipedia sull'inondazione potrebbe essere utile qui: http: //en.wikipedia. org / wiki / Flood_fill

Answer 5

Union-find funzionerebbe qui anche. In effetti, puoi formulare la tua domanda come un problema su un grafico: i vertici sono le celle della griglia e due vertici sono adiacenti se le loro celle della griglia hanno lo stesso colore. Stai cercando di trovare i componenti collegati.

Il modo in cui useresti una struttura di dati di unione-find è il seguente: prima crea una struttura di dati di unione-find con tutti gli elementi che hai delle celle. Quindi scorrere le celle e unione due celle adiacenti se hanno lo stesso colore. Alla fine, esegui find su ogni cella e archivia la risposta. Le celle con lo stesso find si trovano nella stessa regione colorata contigua.

Answer 6

Se vuoi un po 'più di controllo della grana fine, potresti pensare di utilizzare A * algoritmo e utilizzare l'euristica per includere tessere di colore simile.

Answer 7

Esamini le regioni in una linea di scansione, andando da sinistra a destra in alto in basso. Per ogni cella si crea un elenco di celle condivise come lo stesso oggetto di memoria tra le celle. Per ogni cella, aggiungi la cella corrente all'elenco (condivisa con essa o creata). Quindi se la cella a destra o in basso ha lo stesso colore, condividi tale elenco con quella cella. Se quella cella ha già un elenco, puoi combinare gli elenchi e sostituire il riferimento all'oggetto elenco in ogni cella elencata negli elenchi con il nuovo elenco unito.

Quindi si trova in ogni cella un riferimento a un elenco che contiene ogni cella contigua con quella cella. Questo combina in modo appropriato il lavoro dell'inondazione tra ogni cella. Invece di ripeterlo per ogni cella. Dal momento che hai le liste che sostituiscono i dati con i dati uniti, sta solo scorrendo una lista. Sarà O (n * c) dove n è il numero di celle e c è una misura di quanto contiguo sia il grafico. Una griglia completamente disgiunta sarà n volta. Un grafico a 1 colore completamente contiguo con n ^ 2/2.