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.

[Jean Dumoncel]

Salut,

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.

Es-tu sûr que la complexité serait trop importante? Sur combien de segments tu travailles?

[kirua_sama]

1M-2M.

De plus Il faut traiter les cas des polygones adjacents .
Apparament, cela doit pouvoir se faire plus simplement avec la bibliotheque

CGAL -- > http://www.cgal.org/Manual/3.2/doc_h...a_shape_2.html

La structure est capable de me renvoyer tres rapidement le nobre de polygones fermes... :

"A.number of solid components performs a graph traversal and takes time linear in the number of faces of the underlying triangulation. "

Cependant je n`arrive pas a trouve le moyen de reproduire ceci avec la meme complexite : / -- Je suppute un manque de connaissance dans la gestion des structures de donnees : Edges/Surfaces.

[Jean Dumoncel]

1M-2M.

Miliers? Millions? Milliards?

Si c'est milliers, perso je tenterais la reconstruction des polygones par recherches de voisins, les temps de calcul devrait être raisonnable...

Apparament, cela doit pouvoir se faire plus simplement avec la bibliotheque

CGAL -- > http://www.cgal.org/Manual/3.2/doc_h...a_shape_2.html

La structure est capable de me renvoyer tres rapidement le nobre de polygones fermes... :

"A.number of solid components performs a graph traversal and takes time linear in the number of faces of the underlying triangulation. "

Cependant je n`arrive pas a trouve le moyen de reproduire ceci avec la meme complexite : / -- Je suppute un manque de connaissance dans la gestion des structures de donnees : Edges/Surfaces.

Je ne connais pas cet algorithme dans le détail, mais mais je ne comprends pas bien ce que tu pourrais en faire : apparemment l'alpha shape permet de reconstruire une enveloppe après triangulation, toi tu as déjà les contours de tes polygones.

De plus Il faut traiter les cas des polygones adjacents .

C'est bien là la difficulté, ça rajoute des contraintes et des vérifications mais en orientant convenablement tes polygones, tu devrais t'en sortir.

[kirua_sama]

Millions.
Desole. Je pensais que le grand M etait universellement le million...

Je ne connais pas cet algorithme dans le détail, mais mais je ne comprends pas bien ce que tu pourrais en faire : apparemment l'alpha shape permet de reconstruire une enveloppe après triangulation, toi tu as déjà les contours de tes polygones.

En realite, c`est cet algorithme que j`utilise pour realise mes formes ; c`est pourauoi je postais le liens pour monter a partir de quoi je travaillais exactement.

C'est bien là la difficulté, ça rajoute des contraintes et des vérifications mais en orientant convenablement tes polygones, tu devrais t'en sortir.

Tu veux dire en reorientant mes segments pour creer mes polygons ?

[Jean Dumoncel]

Millions.
Desole. Je pensais que le grand M etait universellement le million...

Oui, mais c'était surtout pour être sûr...

En realite, c`est cet algorithme que j`utilise pour realise mes formes ; c`est pourquoi je postais le liens pour monter a partir de quoi je travaillais exactement.

Ok, mais du coup je ne comprends pas : que te renvoie cet algorithme? Un liste de segments et c'est à toi de faire le tri si j'est bien compris? Ce n'est pas possible qu'il te renvoie directement l'ensemble des polygones?

Tu veux dire en reorientant mes segments pour creer mes polygons ?

J'ai vu que tu as une autre discussion ouverte dans le forum algo. En fait ce que je disais rejoint ce qui est dit par pseudocode ou Graffito (sur le fait de tourner le plus à droite ou le plus à l'ouest) : il va falloir que tu décides d'une stratégie pour reconstruire tes polygones, cette stratégie s'appliquera à chacun de tes polygones.

[kirua_sama]

J'ai vu que tu as une autre discussion ouverte dans le forum algo.

Oui, je ne savais pas si cela avait sa place dans un forum mathematique ou directement dans le forum C++ due a la bibliotheque que j`utilisais. Puis mon message precedemment situe dans la categorie C++ a ete deplace.

Ok, mais du coup je ne comprends pas : que te renvoie cet algorithme? Un liste de segments et c'est à toi de faire le tri si j'est bien compris? Ce n'est pas possible qu'il te renvoie directement l'ensemble des polygones?

Ce serait evidement bien trop beau ... Il me renvoi une structure template complexe contenant des "face", des "edges" provenant d`une triangulation de delaunay je recupere mes segments en parcourant les "edges". Cependant celle-ci ne sont pas distribue dans le bon ordre.... Je dessinne donc les segments dans un ordre aleatoire dans l`espace qui au final me donne une forme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
for (Alpha_Shape_Edges_Iterator edge_alpha_it=_alphaShape.alpha_shape_edges_begin(); edge_alpha_it!=_alphaShape.alpha_shape_edges_end(); edge_alpha_it++)
            {
                Alpha_Edge& edge = *edge_alpha_it;
 
                const Point_2& p1 = edge.first->vertex(edge.first->ccw(edge.second))->point();
                const Point_2& p2 = edge.first->vertex(edge.first->cw (edge.second))->point(); }

J`ai progresser depuis, je suis en train d`essayer de parcourir les face et d`en determine le sens... celle qui pointent vers le meme espace et sont donc interieur.

Je poste ma solution si elle s`avere functionnelle et efficace dans la journee je l`espere.

Merci bien,
Cordialement.

[kirua_sama]

Bon voila, j`ai quasiment fini :
Il ne me reste plus qu`a prendre le qhull de chacunes de mes triangulation :

Un petit Screen :

[IMG][/IMG]