Algorithme de forme

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:

---

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:

---

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:

---

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

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:

---

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:

---

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:

---

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 ?

Citation:

---

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.

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:

---

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

Citation:

---

Envoyé par Casshern123

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é. :aie:

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 ?

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

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

Heu.. Ouais c'est pas encore trop clair dans ma tête mais disons...

Parce que là, l'algo fait quoi? Il trouve une forme et la remplit tout seul? Transformer la carte en 1,2 et 0 ok, mais pour dire que y a une forme avec des 1 c'est la tout le probleme. De trouver une forme

Je vois quand même pas comment l'algorithme se comporte quand il n y a pas de forme, c'est a dire des X un peu random mais qui se referme pas.

Citation:

---

Parce que là, l'algo fait quoi? Il trouve une forme et la remplit tout seul?

---

L'algo te crée le tableau "carte des c.connexes" à partir du tableau "src extended"

Citation:

---

mais pour dire que y a une forme avec des 1 c'est la tout le probleme. De trouver une forme

---

la composante 0 n'est pas une forme, car c'est la composante associée à un bord de ton image (et on a étendu le tableau pour être certain que les bords ne contiennent pas de forme).

Les autres composantes (1,2,..) sont donc associées soit à une case "x", soit a l'intérieur d'une forme.
=> il suffit de regarder dans le tableau de départ pour savoir dans quel cas on est.

Citation:

---

Je vois quand même pas comment l'algorithme se comporte quand il n y a pas de forme, c'est a dire des X un peu random mais qui se referme pas.

---

Tu auras des 0 partout, sauf pour les cases "x" ou tu auras le numéro de la composante (=point X isolé, ou ligne de X, ou bloc de X).

+-----------+      +-----------+
|           |      |00000000000|
|    X    X |      |00001000020|
|  X      X |      |00300000020|
|         X |      |00000000020|
| XXXXX   X | ---> |04444400020|
| XXXXX   X |      |04444400020|
|         X |      |00000000020|
|         X |      |00000000020|
|           |      |00000000000|
|           |      |00000000000|
+-----------+      +-----------+
 src extended        c.connexes 

Merci de ta réponse c'est un peu plus clair. Mais ce que je pige toujours pas, c'est comment avec ça je trouve une forme. Parce qu'ok passait de src a la carte des c. connexes, je vois bien mais ensuite ?
Si tu mets ça a mon problème initial je pige pas. Ca va transformer ma map ok, mais en quoi ça aide a trouver et colorier une forme? Désolé je suis un peu lent a saisir là .. :p

Edit : ok après avoir bien relu et tout ça, j'ai compris en effet! Mais maintenant comment je fais pour adapter ton algortihme sur un tableau et non une image?

Citation:

---

Envoyé par Casshern123

Mais maintenant comment je fais pour adapter ton algortihme sur un tableau et non une image?

---

La contribution parle d'image, mais l'algorithme traite en réalité des tableaux.

Dans l'implémentation en C:

* Le tableau en entrée (image) est un tableau 2D : int image[456][123] = /* ... */;

* La tableau en sortie (CCroots) est un tableau 1D: long *CCroots;
=> pour y accéder avec des coordonées 2D: long numero_composante = CCroots[x+y*W];

ou alors un recast du genre:
long (*composantes)[123] = (long (*)[123]) CCroots;
long numero_composante = composantes[x][y];

Ah oui effectivement, mon erreur c'était que je pensais que ça modifiait mon tableau directement :)!
Ca a l'air de marcher pas trop mal :D !
Merci ! Juste tu sais ou je pourrai trouver une explication de l'algo ? Parce que là je l'ai lancé en regardant vite fait. Plus t'as de lien, plus ça me va :)!

Parce que j'aimerai bien le faire marcher aussi en "diagonale" si c'est possible, du style

Code:

---

1 2 3 4 5 6 7 8 9 10

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

---

Dailleurs, dans CCinit, t'as un "long i" qui est pas utilisé.
Et dailleurs, y a un moyende pouvoir le faire sans extend le tableau en hauteur et largeur ? (juste voir si une opti est possible)

Citation:

---

Envoyé par Casshern123

Ah oui effectivement, mon erreur c'était que je pensais que ça modifiait mon tableau directement :)!
Ca a l'air de marcher pas trop mal :D !
Merci ! Juste tu sais ou je pourrai trouver une explication de l'algo ? Parce que là je l'ai lancé en regardant vite fait. Plus t'as de lien, plus ça me va :)!

---

Regarde le message #6 dans la contribution.

Citation:

---

Parce que j'aimerai bien le faire marcher aussi en "diagonale" si c'est possible, du style

---

L'algo proposé fusionne les composantes reliées "en diagonale".
Pour annuler ce comportement, il faut supprimer les tests avec les pixels en diagonale (NORD_OUEST, et NORD_EST)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

...   // test la liaison avec le pixel OUEST if ( (x>0) && (image[pos-1]==image[pos]) ) root = CCunion( CCfind(pos-1) , root);   // test la liaison avec le pixel NORD_OUEST if ( (x>0 && y>0) && (image[pos-1-W]==image[pos]) ) root = CCunion( CCfind(pos-1-W) , root);   // test la liaison avec le pixel NORD if ( (y>0) && (image[pos-W]==image[pos]) ) root = CCunion( CCfind(pos-W) , root);   // test la liaison avec le pixel NORD_EST if ( (x<(W-1) && y>0) && (image[pos+1-W]==image[pos]) ) root = CCunion( CCfind(pos+1-W) , root);   ...

---

Citation:

---

Dailleurs, dans CCinit, t'as un "long i" qui est pas utilisé.

---

Exact, c'est une erreur. Ca fait 8 ans que c'est comme ca :aie:

Citation:

---

Et dailleurs, y a un moyende pouvoir le faire sans extend le tableau en hauteur et largeur ? (juste voir si une opti est possible)

---

Tu peux, mais sans étendre le tableau tu peux avoir plusieurs composantes de "fond" si ta forme touche 2 bords.

Merci de ta réponse, j'ai pu l'implémenter et je dois admettre que ça marche plutot bien :-)!

Je passe ça en résolu !