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 :

Tester si un chemin est fermé


Sujet :

Algorithmes et structures de données

  1. #1
    Membre à l'essai
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    7
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Novembre 2008
    Messages : 7
    Points : 10
    Points
    10
    Par défaut Tester si un chemin est fermé
    Bonjour,

    Voilà ma situation, je crée un chemin :



    Je veux que lorsque ce chemin est "fermé", il l'est sur l'image, j'en soit informé et récupérer ensuite les positions des carrés vides (1) à l'intérieur de la forme créee.

    Ensuite je refais un chemin à partir de la forme créee :



    Je veux à nouveau retester mes carrées jaunes et pouvoir remplir les zones fermées.



    Comment que quoi ?

  2. #2
    Membre régulier
    Homme Profil pro
    Consultant informatique
    Inscrit en
    Mars 2007
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Consultant informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mars 2007
    Messages : 8
    Points : 74
    Points
    74
    Par défaut
    Bonjour,

    je viens de lire votre problème et sans prétendre pouvoir y apporter une solution, j'aimerais quand vous soumettre quelques idées que j'ai eues
    après la lecture de ce dernier.

    Si on considère le chemin créé comme un graphe planaire, alors je pense
    qu'il suffit de connaître un algorithme permettant de de dire si une suite
    de points données d'un graphe constitue un cycle (ou une chaîne) de ce
    graphe. Un tel algorithme trouvé, il suffirait de calculer l'enveloppe convexe
    des points du graphe, et de vérifier que la suite de points qui la compose
    forme un cycle de ce graphe. A mon avis ce serait un bon critère de
    fermeture (sans doute pas le plus efficace, mais bon c'est juste une
    proposition).

  3. #3
    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 : 51
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Idées en vrac:

    - detecter qu'un chemin est fermé : A chaque fois qu'on ajoute un pixel jaune, on regarde si ses voisins sont jaunes. C'est un indicateur pour lancer une vérification, par exemple avec un algo de "contour tracing"

    - pour trouver la partie intérieure d'un polygone fermé, on peut utiliser les algos de remplissage (Flood fill) si on connait un point intérieur au polygone.

    - on peut aussi segmenter l'intégralité de l'image, par exemple avec un algo de composantes connexes, ce qui nous donne la liste de toutes les zones bleues/jaunes de l'image.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  4. #4
    Membre à l'essai
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    7
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Novembre 2008
    Messages : 7
    Points : 10
    Points
    10
    Par défaut
    Merci pour les algos, le countour tracing c'est ok le flood fill aussi.

    pour trouver la partie intérieure d'un polygone fermé, on peut utiliser les algos de remplissage (Flood fill) si on connait un point intérieur au polygone
    Mon problème c'est de trouver ce fameux point intérieur au polygone maintenant :S

    Edit : J'ai bien une idée ça a l'air de tenir la route mais j'ai pas testé


    • Je crée un carré autour de ma forme jaune
    • Je démarre d'un des coins et je parcours toutes mes cases par balayage bas vers haut et gauche vers droite par exemple.
    • à chaque case bleue trouvée je vérifie pour chaque direction (haut, droite, bas gauche) si la nouvelle case trouvée est bleue ou jaune
      • si c'est bleu je continue à tester dans la même direction
      • si c'est jaune je m'arrête
      • si je tombe sur le bord rouge j'arrête toutes les vérifications : je considère être à l'extérieur de ma forme, je remplis la zone à l'aide d'un algo de flood fill pour éviter d'avoir à retester toutes les cases de la zone (verte).
      • si pour les 4 directions testées je tombe sur une case jaune, c'est gagné je suis à l'intérieur

  5. #5
    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 : 51
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Avec ce genre d'algo, il faut faire attention aux formes en "U".

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
     ............
     .####.......
     .#..#..#..#.
     .#..#..#..#.
     .#..####..#.
     .#........#.
     .##########.
     ............
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  6. #6
    Membre à l'essai
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    7
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Novembre 2008
    Messages : 7
    Points : 10
    Points
    10
    Par défaut
    Raaah oui en effet...

    Autre idée, je fais un colour fill sur chaque case bleue rencontrée et dans l'algo de colour fill même je teste si la zone touche le carré rouge si c'est pas le cas c'est fermé...

    ou pas !?

  7. #7
    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 : 51
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par carignou Voir le message
    Raaah oui en effet...

    Autre idée, je fais un colour fill sur chaque case bleue rencontrée et dans l'algo de colour fill même je teste si la zone touche le carré rouge si c'est pas le cas c'est fermé...

    ou pas !?
    Oui, ça marche.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  8. #8
    Membre à l'essai
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    7
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Novembre 2008
    Messages : 7
    Points : 10
    Points
    10
    Par défaut
    Merci à toi pseudocode.

    J'ai utilisé un des algorithmes du lien que t'as donné, précisément le "Square Tracing Algorithm" et ça fonctionne.

    Désolé de remonter un vieux topic mais j'avais jamais donné de retour ni taggué "résolu".

  9. #9
    Futur Membre du Club
    Inscrit en
    Novembre 2005
    Messages
    7
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 7
    Points : 6
    Points
    6
    Par défaut
    Je suis à l'origine du déterrement du post suite à un MP à Carignou. Désolé pour cela

    Merci pour le nom de l'algorithme choisi.
    ++

  10. #10
    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 : 51
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Inutile de s'excuser de donner des nouvelles et de fermer proprement un sujet.
    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. [AC-2003] Tester si un classeur est fermé
    Par flet le kid dans le forum VBA Access
    Réponses: 2
    Dernier message: 15/06/2009, 14h10
  2. [mysqli] tester si une connection est fermée
    Par raoulchatigre dans le forum Administration
    Réponses: 4
    Dernier message: 06/10/2006, 16h00
  3. [XSL] Tester si la valeur est un entier dans un xml
    Par MrMaze dans le forum XSL/XSLT/XPATH
    Réponses: 2
    Dernier message: 23/07/2003, 05h35
  4. Tester si un champ est NULL
    Par titititi007 dans le forum MS SQL Server
    Réponses: 3
    Dernier message: 19/06/2003, 11h17
  5. tester si une date est valide
    Par Andry dans le forum Langage
    Réponses: 5
    Dernier message: 17/09/2002, 12h54

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