algorithme pour trouver et remplir les formes fermées sur une grille

Question

dire donc que nous avons une grille vide de 0s:

0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 

Et vous pouvez dessiner des formes sur elle. 1 représente une cellule remplie.

1 1 1 1 0 0 0 0 
1 0 0 1 0 0 0 0 
1 0 0 1 0 0 0 0 
1 1 1 1 0 0 0 0 
0 0 0 0 0 0 0 0 
0 1 1 0 0 1 1 1 
1 0 0 1 0 1 0 0 
0 1 1 0 0 1 0 0 

Une forme est considérée comme fermée si un algorithme flot de remplissage à quatre directions ne fuir et remplir toutes les cellules en dehors de la forme. Une forme ne peut pas utiliser la limite de la grille comme l'un de ses côtés. Donc, si nous avons rempli toutes les formes fermées dans cette grille avec 2 s, nous aurions:

1 1 1 1 0 0 0 0 
1 2 2 1 0 0 0 0 
1 2 2 1 0 0 0 0 
1 1 1 1 0 0 0 0 
0 0 0 0 0 0 0 0 
0 1 1 0 0 1 1 1 
1 2 2 1 0 1 0 0 
0 1 1 0 0 1 0 0 

La mise en œuvre de l'algorithme de remplissage d'inondation est facile, mais je ne peux pas trouver un moyen de (programatically) remplir dans toutes les formes arbitraires enfermées dans une grille. Existe-t-il un type d'algorithmes ou de recherches que je pourrais utiliser pour cela?

Answer 1

Qu'est-ce qui ne va pas avec l'algorithme flood-fill? C'est une fin simple efficace avec la complexité O (N).

Au premier balayage des bords pour les valeurs nulles et inondation des zones vides avec la valeur de marque 3. Ensuite, traversez l'intérieur. Si vous trouvez la cellule zéro, remplissage à flot de cette cellule avec la valeur 2.

(Peut-être vous cherchez quelque chose comme connected-component labeling algorithm. Il est destiné à marquer toutes les régions reliées par la valeur de la marque unique)

Answer 2

Vous pouvez d'abord trouver 0 qui ont un chemin à la limite:

Prendre une cellule 0 arbitraire dans la frontière, la marquer comme -1, le faire pour toutes ses cellules voisines récursivement (voisins de voisins et ainsi de suite tous mis à -1). Une fois qu'aucune des cellules limites n'est nulle, mettez toutes les cellules zéro à 2. Cela signifie qu'elles sont entourées de seulement 1. Après tout, mettez tous les -1 à 0. C'est O (n) qui n est le nombre de cellules dans la grille.

est ici un (paresseux) pseudo-code, en supposant que nous avons grille n_1xn_2:

function fill() 
{ 
for int i=1..n_1 
{ 
    recursivecolor(i,1); 
    recursivecolor(i,n_2); 
} 

for int j=1..n_2 
{ 
    recursivecolor(1,j); 
    recursivecolor(n_1,j); 
} 

for i=1..n_1 
    for j=1 .. n_2 
    if (a[i][j] == 0) 
     a[i][j] = 2; 

for i=1..n_1 
    for j=1 .. n_2 
    if (a[i][j] == -1) 
     a[i][j] = 0; 
} 


function recursivecolor(i,j) 
{ 
    if (a[i][j]!=0) return; 

    a[i][j] = -1; 
    if (a[i-1][j] == 0) 
    { 
     a[i-1][j] = -1; 
     recursivecolor(i-1,j); 
    } 
    // do this for all neighbours of i,j cell 
    // it also needs check for boundaries, e.g. i-1 should not be zero ... 
}