IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Algorithme de forme


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Nouveau membre du Club
    Homme Profil pro
    Responsable sécurité
    Inscrit en
    Février 2014
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Responsable sécurité

    Informations forums :
    Inscription : Février 2014
    Messages : 7
    Par défaut 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 : 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

  2. #2
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    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.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Nouveau membre du Club
    Homme Profil pro
    Responsable sécurité
    Inscrit en
    Février 2014
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Responsable sécurité

    Informations forums :
    Inscription : Février 2014
    Messages : 7
    Par défaut
    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

  4. #4
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par Casshern123 Voir le message
    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 ?
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Nouveau membre du Club
    Homme Profil pro
    Responsable sécurité
    Inscrit en
    Février 2014
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Responsable sécurité

    Informations forums :
    Inscription : Février 2014
    Messages : 7
    Par défaut
    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

  6. #6
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    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
    
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Algorithme reconstruction de forme 3D
    Par firespirit dans le forum Traitement d'images
    Réponses: 9
    Dernier message: 03/12/2009, 09h42
  2. Algorithme pour redimensionnement de me form vs composantes
    Par burnx22 dans le forum Mathématiques
    Réponses: 3
    Dernier message: 26/02/2009, 01h27
  3. Réponses: 1
    Dernier message: 14/05/2008, 17h31
  4. [Image] Algorithme pour déterminer une forme continue
    Par wizzmasta dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 25/04/2006, 15h56
  5. algorithme : en forme sql
    Par lou87 dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 05/04/2006, 09h24

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo