Discussion :

[kirua_sama]

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]

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]

[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]

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]

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.

[3DArchi]

Salut,
Est-ce que ce tuto peut t'aider : Méthode des contours actifs ? L'enveloppe pourrait t'aider à construire ton polygone ?

[kirua_sama]

Hi,

Absolument pas .

Mais merci pour le liens, toujours interessant.

[pseudocode]

Oui l`adjacence est un probleme important ....

Suffit de toujours tourner le plus à droite possible à une intersection. non ?

[Graffito]

Pourrais-tu donner quelques précisions :

• Quand 2 segments AB et CD ont un point commun, ce point est-il obligatoirement l'un des 4 points A, B, C ou D?
• Les coordonnées des points sont-elles des entiers (exactes) ou des float (approximatives)?
• Les contours sont-ils forcément fermés?
• La figure est-elle forcément connexe ?

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.

cela ne me parait pas si stupide, si on simplifie l'algo en construisant la figure par itération sur les segments triés en fonction de leur point le plus à l'Ouest.

[kirua_sama]

* Quand 2 segments AB et CD ont un point commun, ce point est-il obligatoirement l'un des 4 points A, B, C ou D?

Absolument -- En fait pour donner plus de detail, la detection de formes se fait sur la base d`une triangulation de delaunay en 2D.

* Les coordonnées des points sont-elles des entiers (exactes) ou des float (approximatives)?

Les donnees sont exactement approximative. . Mais je pense que pour le probleme, cela ne change rien ou presque ... !?

* Les contours sont-ils forcément fermés?

Ouip ^^, les contours sont toutes mes formes detectees.

* La figure est-elle forcément connexe ?

Non, on le vois sur le dessin ^^.

[Graffito]

La figure est-elle forcément connexe ?
--> Non, on le vois sur le dessin ^^.

Effectivement Le contour n'est pas convexe, mais il y a 1 seule figure connexe.

Les donnees sont exactement approximative.... Mais je pense que pour le probleme, cela ne change rien ou presque ... !?

Si tu peux établir une fonction qui détermine que 2 points sont identiques (à epsilon près), je conseillerais de faire une passe préalable qui "déplace" légérement chaque points situé aux voisinage d'un autre de façon à ce que les 2 points soient confondus.

En fonction de tes réponses, ert après avoir trié les segments d'Ouest en Est sur leur point le plus à l'ouest (et en critère secondaire l'autre extrémité la plus à l'ouest), la méthode itérative de construction me parait jouable. A chaque fois que tu ajoutes un segment, tu as une liste de polygones fermés ou "ouverts". Les cas possibles sont :
- 1 point du segment sur une extrémité d'un polygone ouvert, tu prolonges le polygone ouvert et éventuellement tu le fermes
- Autres cas : tu crées un polygone ouvert.

[kirua_sama]

Il reste le probleme de l`adjacance dans ta solution .

Mais merci beaucoup, je commence a avancer sympatiquement ^^.
Avant que le message ne soit deplace, j`avais aussi poste dans le forum d`algorithme mathematique :

http://www.developpez.net/forums/d83...n/#post4770501

Je progress, et espre pouvoir poste une solution dans la journee.
Merci a vous.

[pseudocode]

Ca n'irait pas plus vite de reconstruire le Quad-Edge ?