Existe-t-il un algorithme pour déterminer les régions colorées contiguës dans une grille?

Question

Étant donné une grille de base (comme un morceau de papier graphique), où chaque cellule a été remplie de manière aléatoire avec l'une des n couleurs, existe-t-il un algorithme éprouvé qui peut me dire quelles régions contiguës (groupes de cellules de la même couleur qui sont joints sur le côté) il y a? Disons que n est quelque chose de raisonnable, comme 5.

J'ai des idées, mais elles se sentent toutes terriblement inefficaces.

Answer 1

Le meilleur algorithme possible est O (nombre de cellules) et n’est pas lié au nombre de couleurs.

Cela peut être réalisé en parcourant les cellules, et chaque fois que vous visitez une personne qui n'a pas été marquée comme visitée, effectuez une traversée de graphe pour rechercher toutes les cellules contiguës dans cette région, puis continuez la répétition.

Modifier:

Voici un exemple de pseudo-code simple d'une recherche de profondeur d'abord, qui est un moyen facile d'implémenter la traversée de graphe:

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

Answer 2

En plus de la réponse récursive de récursive, vous pouvez utiliser une pile si la récursivité est trop lente:

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

Vous pouvez essayer d’inonder les cases de chaque carré. Au fur et à mesure que le flot se propage, enregistrez les carrés de la grille dans un tableau ou quelque chose du genre et colorez-les d'une couleur inutilisée, par exemple -1.

Answer 4

L'article de Wikipedia sur les crues pourrait vous être utile ici: http: //en.wikipedia. org / wiki / Flood_fill

Answer 5

Union-find fonctionnerait ici ainsi que. En effet, vous pouvez formuler votre question sous la forme d’un problème concernant un graphique: les sommets sont les cellules de la grille et deux sommets sont adjacents si leurs cellules ont la même couleur. Vous essayez de trouver les composants connectés.

Pour utiliser une structure de données Union-Find, procédez comme suit: commencez par créer une structure de données Union-Find avec autant d'éléments que vous avez de cellules. Ensuite, parcourez les cellules et union deux cellules adjacentes si elles ont la même couleur. À la fin, exécutez find sur chaque cellule et stockez la réponse. Les cellules avec le même find sont dans la même région colorée contiguë.

Answer 6

Si vous souhaitez un peu plus de contrôle du grain, vous pouvez envisager d'utiliser le A *

Answer 7

Vous parcourez les régions d'une ligne de balayage en allant de gauche à droite en haut. Pour chaque cellule, vous créez une liste de cellules partagées sous le même objet mémoire entre les cellules. Pour chaque cellule, vous ajoutez la cellule actuelle à la liste (partagée ou créée). Ensuite, si la cellule à droite ou au-dessous est de la même couleur, vous partagez cette liste avec cette cellule. Si cette cellule contient déjà une liste, vous combinez les listes et remplacez la référence à l'objet liste dans chaque cellule répertoriée dans les listes par la nouvelle liste fusionnée.

Ensuite, dans chaque cellule se trouve une référence à une liste contenant toutes les cellules contiguës avec cette cellule. Cela combine judicieusement le travail de la crue entre chaque cellule. Plutôt que de le répéter pour chaque cellule. Puisque vous avez les listes, les données remplacées par les données fusionnées ne font que parcourir une liste. Ce sera O (n * c) où n est le nombre de cellules et c est une mesure de la contiguïté du graphique. Une grille complètement décousue sera n fois. Un graphe 1 couleur complètement contigu avec be n ^ 2/2.