Polygones simple A Partir de Segment

**kirua_sama** · 05/11/2009, 10h03

Bonjour,

Je buttes acutellement sur un petit probleme assez simple en apparence.
J`ai procede a une detection de formes dans mon programes et recupere alors une liste de segments non classes.

Avec Ceux-ci je peux donc afficher mes formes et creer un polygone complexe.
Ce que j`aimerais faire, est de pouvoir creer des polygones pour chacunes de mes formes detectees.

Pour cela l`idee la plus simple qui me vient est de parcourir tout les segments et de les rattacher lorsque ils ont un point en commun. cependant la complexite, en terme de computation, de cette solution ne me plait guerre.

La seconde serais de decompose un polygone complexe en une multitude de polygone simple. Seuleument, je ne pense que cela soit simplement faisable.

Quelqu`un aurait il une idee ou des conseilles ?
Je vous remercie.

**Cheps** · 05/11/2009, 10h22

Je ne suis pas sûr de bien comprendre le problème, un dessin serait le bien venu pour pouvoir t'aider

Sinon tu trouveras peut-être plus d'aide sur le forum algorithmes.

**kirua_sama** · 05/11/2009, 11h13

[IMG]

[/IMG]

Voici donc mes polygones construit par listes de segments.
A partir de cela, j`aimerais pouvoir creer mes 8 polygones visible...

Actuellement j`utilise la lib CGAL... et j`ai poste en doublons dans la categorie math, ne sachant pas trop ou cela avait sa place.

**Cheps** · 05/11/2009, 12h39

Tu pourrais d'abord les trier (un quicksort semble adapté), avant de parcourir ta structure pour relier les segments entre eux, ce qui te donnerait une complexité de O(n*log(n) + n), qui t'évite le n carré quand tu considéres chaque paire de segments. Après pour faire mieux je sais pas trop. Mais tu risques d'avoir un autre problème: vu que les polygones se touchent, il faut faire attention à ne pas construire les mauvais polygones, et ça c'est pas trivial à mon avis.

**kirua_sama** · 05/11/2009, 13h01

Oui l`adjacence est un probleme important ....
Je pense que je vais essayer de chercher un autre moyen de recuperer mes formes....

Autrement je fait de la detection de forme dans un nuage de point 2D, j`utilise un algorithme de type alpha shape (cercle circulator). Si tu as un meilleure idee qui pourrait me fournir plus simplement des polygones, ce serait sympa ^^.

J`avais pense a Hough mais ca ne me semblait par super adapter aux millions de points.

Merci pour ta reponse.