Tester si un chemin est fermé

Bonjour,

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

http://tof.canardpc.com/view/e4f4058...8f5af58d36.jpg

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 :

http://tof.canardpc.com/view/d6f57a6...c375f3b2c8.jpg

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

http://tof.canardpc.com/view/8bc197b...a158d6987d.jpg

Comment que quoi ?

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

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.

Merci pour les algos, le countour tracing c'est ok le flood fill aussi.

Citation:

---

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é

http://img714.imageshack.us/img714/6609/13533676.png

• 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

Avec ce genre d'algo, il faut faire attention aux formes en "U".

Code:

---

1 2 3 4 5 6 7 8 9

............ .####....... .#..#..#..#. .#..#..#..#. .#..####..#. .#........#. .##########. ............

---

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 !?

Citation:

---

Envoyé par carignou

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.

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".

Je suis à l'origine du déterrement du post suite à un MP à Carignou. Désolé pour cela :oops:

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

Inutile de s'excuser de donner des nouvelles et de fermer proprement un sujet. :D