Discussion :

[aidos]

Bonjour,

Pour me simplifier la vie dans projet, j'aurai besoin de "fusionner" deux polygones, appellons les P et Q, c'est à dire de prendre P et Q, et si ils se coupent, de suivre le contour jusqu'a recupérer un seul contour qui englobe les deux polygones P et Q.

Pour cela, j'ai voulu implémenter un algorithme à la sauce maison, et en decretant que les polygones sont orientés dans le sens trigo, je suit le contour, et à chaque intersection, j'insere le point d'intersection et je passe sur l'autre polygone. Sauf que si on a une double intersection sur le meme segments, à la suite (donc un point de P en dehors de Q, un point dans et un point re dehors à la suite), ça ne marche plus... etj'ai l'impression que si je veux que ça marche, ça me rajoute tellement de tests que ça deviendra le pire algo de tout les temps.
Donc j'ai fait mes devoirs, et j'ai cherché avec mon ami Google, qui m'a mis sur la voie de l'algo de Weiler-Atherton, qui me parait parfait pour ce travail, mais qui a aussi l'air d'être le secret le mieux gardé d'internet!

Alors si quelqu'un qui a déjà eu l'occasion de s'en servir pouvait m'éclairer dessus, parce que pour le moment, je n'ai pas trouvé d'explication complète de l'algo, et je comprend rien au PDF de ses "inventeurs"...

Bien sûr , si vous avez un algo maison qui marche du feu de Dieu, je prend

Merci infiniment!
PS. je me suis permis de poster ce message dans le forum C++ aussi, ne sachant pas trop dans quel forum il etait le plus adapté.

[Nemerle]

est-ce que le bon exemple http://pilat.free.fr/pdf/weiler.pdf ne te suffit pas pour comprendre l'algo???? C'est vraiment très clair...

[Nemerle]

Un +: l'article originel: http://www.cs.drexel.edu/~david/Clas...214-weiler.pdf

[aidos]

en fait, ma difficulté réside surtout dans le traitement des cas particuliers, comme un segment partagé, ou un point d'un polygone sur un segment de l'autre polygone, ou encore deux points confondus. Par exemple dans le cas dun segment partagé, doit je considérer qu'il est secant à lui même? si oui, comment determiner une intersection entrante de sortante? etc...
J'ai feuilleté ces deux pdf, mais le premier n'apporte pas de réponse à ce niveau, et le second m'est parfaitement hérmétique...

[Nemerle]

http://m.strasser.faculty.free.fr/Mo...sationBase.pdf

Tu détermines un sommet d'un des 2 polygones intérieurs à l'autre: page 14

Le chainage décrit p17 dans l'algo de WA est facile à maîtriser. Par exemple, si une intersection Ri tombe sur un sommet Qj, tu peux remplacer Qj par Ri au lieu d'insérer Ri dans ta liste.

Donc si au départ tu as

Code :

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

1
2
P1 P2 P3 P4 ...
Q1 Q2 Q3 Q4...

avec P2=Q2 et P3=Q3 (segment partagé), tu remplaces par

Code :

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

1
2
3
P1 R1 R2 P4...
     |   |
Q1 R1 R2 Q4...

L'application stricto sensu du parcours des listes avec bascule d'une à l'autre quand c'est un Ri est intègre et suffisante, et ne devrait pas te poser de problème d'implémentation.

[Graffito]

Bonjour,

est-ce que le bon exemple http://pilat.free.fr/pdf/weiler.pdf ne te suffit pas pour comprendre l'algo????

Je ne suis pas sur que la méthode fonctionne si le sens de rotation des points est différent dans les 2 polygones. Dans ce cas, Il faudrait rajouter un algo qui normalise le sens de rotation.

Pour le traitement des cas particuliers, une méthode simple consiste à déplacer les sommets d'epsilon, quitte à les remettre en position initiale à la fin du traitement.