Discussion :

[Casshern123]

Bonjour,

J'ai un petit problème, j'ai un tableau de string contenant n*m cases (donc un tableau en 2D). De plus, une case peut avoir deux états :
Les cases vides qui sont représentés par un espace.
Les cases qui représente un "pixel noir" et qui sont représentés par un "X"

L'idée est que j'ai implémenté l'algorithme de flood_fill qui consite a remplir une forme dans le tableau en lui donnant les coordonées d'une case vide (représenté par un espace) :
Pour mieux comprendre, voilà un exemple avec "flood_fill(array, 1, 2);"

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
Avant : 
----------
|  XXXXXXX|
| X      X|
|X       X|
|XXXXX   X|
|    X   X|
|    XXX X|
|       XX|
|         |
|         |
----------
 
Apres : 
 
----------
|  XXXXXXX|
| XZZZZZZX|
|XZZZZZZZX|
|XXXXXZZZX|
|    XZZZX|
|    XXXZX|
|       XX|
|         |
|         |
----------

Maintenant moi, mon problème c'est de trouver automatiquement ce "1,2". Du coup je suis partie du principe que j'allais re-utiliser flood_fill et que si je tombais sur les bors de mon tableau, donc i = 0 ou j = 0 et que la case n'était pas un X, ça veut dire que je suis en dehors d'une forme non? Et si c'est le cas, je mets une variable z (par référence) à 0 et je "return;" cela donne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
void check(std::string array[9][9], int i, int j, int &z)
{
  if ((i == 0 || j == 0 || i == 8 || j == 8 ) && array[i][j] != "X")
  {
   std::cout << "Here" << std::endl; // Ca c'est mon print de debug pour le bug que j'explique après
   z = 0;
   return;
  }
  if (array[i][j] == " ")
  {
    array[i][j] = "Z";
    z++;
    check(array, i+1, j, z);
    check(array, i-1, j, z);
    check(array, i, j+1, z);
    check(array, i, j-1, z);
  }
}

L'idée est donc que je parcours mon tableau en lancant check(array, i, j, z) et si j'ai (z != 0) alors je lance flood_fill sur i et j et tout devrait marcher correctement!
Sauf que dans certain cas ça marche pas du tout.. Par exemple sur "check(array, 1, 3, 0);" et en modifiant mon tableau d'origine j'ai :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
----------
|  XXXXXXX|
| X      X|
|X       X|
|        X|
|    X   X|
|    XXX X|
|       XX|
|         |
|         |
----------
 
Here
Here
Here
Here
Here
Here
Here
Here
Here
Here
Here
Here
Here
 
----------
|  XXXXXXX|
| XZZZZZZX|
|XZZZZZZZX|
| ZZZZZZZX|
| ZZZXZZZX|
| ZZZXXXZX|
| ZZZZZZXX|
| ZZZZZZZ |
|         |
----------

Du coup, le problème c'est que pour debugger un algo reccursif comme ça c'est ultra chaud... du coup je sèche un peu.
Si quelqu'un a une idée ou des questions n'hésitez pas :-). Ou si quelqu'un a un meilleur algorithme pour trouver une forme je suis preneur!

Merci d'avance

[pseudocode]

Je n'ai pas compris le rapport entre le besoin (trouver automatiquement un point de départ ?) et le problème (remplissage incorrect).

Tout ce que je peux dire, c'est que le seul moyen de sortir d'un appel de check(), c'est de passer par ce block:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
std::cout << "Here" << std::endl; // Ca c'est mon print de debug pour le bug que j'explique après
z = 0;
return;

C'est à dire qu'à la sortie de l'appel de check(), on a forcément z=0

Du coup, le bloc de code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
array[i][j] = "Z";
z++;
check(array, i+1, j, z);
check(array, i-1, j, z);
check(array, i, j+1, z);
check(array, i, j-1, z);

est équivalent à:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
array[i][j] = "Z";
z++;
check(array, i+1, j, z); // --->  quand on sort de cet appel, forcément z=0
check(array, i-1, j, 0);
check(array, i, j+1, 0);
check(array, i, j-1, 0);

Du coup, qu'est ce que cette variable "z" est censée représenter pour toi ?

si quelqu'un a un meilleur algorithme pour trouver une forme je suis preneur!

Les algos de type "scanline" sont beaucoup moins complexes (en terme de mémoire et de temps), et plus facile a débugguer car il n'y a pas d'appels récursifs.

[Casshern123]

Merci de ta réponse pseudocode. Effectivement j'ai oublié de préciser quelque chose, ici check remplit mon tableau avec des Z ok ? Et l'idée c'est que si z est différent de 0 alors il est censé avoir trouvé une forme (dans l'idée). Du coup ce que je faisais c'est une double boucle pour parcourir mon tableau (qui est elle meme a l'intérieur de ma double boucle) et qui ensuite va dire si c'est Z ok alors tu le remplaces par un " ".
Parce que l'algo de check ecris dans mon tableau pour faire les tests et j'ai pas pu annuler les modifications que la fonction check faisaient.
En code ça donne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
  for (int i = 0; i < 9; i++)
  {
    for (int j = 0; j < 9; j++)
    {
      check(array, i, j, z);  // du coup je le lance sur la case, et vu que z est une référence (déclaré plus haut) alors la valeur de z va se modifier
      for (int c = 0; c < 9; c++)
      {
        for (int y = 0; y < 9; y++)
        {
          if (array[c][y] == "Z")
          {
            array[c][y] = " "; // l'algo de check écrit des Z un peu partout pour faire ses tests alors je remet mon tableau comme avant check
          }
        }
      }
      if (z != 0)
      {
        floodfill(array, i, j); // si (z != 0) alors en théorie on a trouvé une forme, du coup on lance flood_fill dessus
      }
    }
  }

Sauf que comme je l'ai dit, le problème c'est que pour certain cas comme (1,3) check me retourne une valeur supérieur a 0 alors qu'il ne devrait pas vu qu'il finit sur des bords.
Dailleurs je peux pas changer le 0 par z puisque z est une référence et donc dans l'appel de check je dois mettre une référence.

Du coup si tu as des idées de comment fixer l'algorithme ou des meilleurs je suis preneur. Pendant ce temps je vais me renseigner sur les algos de scanlines.


Merci d'avance

[pseudocode]

Effectivement j'ai oublié de préciser quelque chose, ici check remplit mon tableau avec des Z ok ? Et l'idée c'est que si z est différent de 0 alors il est censé avoir trouvé une forme (dans l'idée). Du coup ce que je faisais c'est une double boucle pour parcourir mon tableau (qui est elle meme a l'intérieur de ma double boucle) et qui ensuite va dire si c'est Z ok alors tu le remplaces par un " ".

Ah... je comprends mieux.
En gros tu vas faire deux fois le travail: ton premier parcours pour trouver les formes, et le second parcours pour les remplir.

Bon, hum... comment dire. C'est pas vraiment optimal en plus d'être assez compliqué.

J'avais posté il y a loooongtemps une contribution qui s'appelle "Etiquettage de composantes connexes".
Ca utilise l'algo union-find et ca permet de remplir toutes les formes de ton tableau avec une valeur différente pour chaque forme.

Est-ce que c'est ca que tu veux ?

[Casshern123]

Ouais, tu as parfaitement compris ce que je souhaitais faire !
Du coup, oui l'idee c'est de "colorier" chaque forme de mon tableau. Quand je dis colorier je parle bien entendu de mettre un "O" a dans les cases vides entourés d'un "X" par exemple.
Du coup j'ai regardé ton algo mais la pour l'instant je vois pas trop comment l'adapter dans mon cas

[pseudocode]

L'algo en question te crée un deuxième tableau qui est la carte des composantes connexes.
Pour chaque case du tableau d'origine, la case correspondante dans la carte te donne le numero de la composante (=l'identifiant de la forme).

Dans ton cas, l'idée serait de

1. étendre ton tableau d'origine avec une ligne/colonne supplémentaire en haut/bas/gauche/droite.
Cela permet d'être certain que la forme ne touche pas le bord du tableau. La composante associée a la case (0,0) sera donc le "fond" de l'image.

2. Créer la carte des composantes connexes

3. Conserver les composantes qui ne sont ni le "fond" ni un "contour" (les cases "x" dans ton tableau de départ)

             +-----------+      +-----------+  +-----------+
+---------+  |           |      |00000000000|  |           |
|  XXXXXXX|  |   XXXXXXX |      |00011111110|  |           |
| X      X|  |  X      X |      |00122222210|  |   222222  |
|X       X|  | X       X |      |01222222210|  |  2222222  |
|XXXXX   X|  | XXXXX   X | ---> |01111122210|  |      222  |
|    X   X|  |     X   X |      |00000122210|  |      222  |
|    XXX X|  |     XXX X |      |00000111210|  |        2  |
|       XX|  |        XX |      |00000000110|  |           |
|         |  |           |      |00000000000|  |           |
|         |  |           |      |00000000000|  |           |
+---------+  +-----------+      +-----------+  +-----------+
   source     src extended        carte des     sans fond et
                                  c.connexes    sans contour