Union de deux polygones

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!

Tu parles de ce pdf là ? :

http://pilat.free.fr/pdf/weiler.pdf

Qu'est-ce qui te pose problème là-dedans ?

non ce n'est pas ce pdf là, le pdf de MM. weiler et atherton c'est celui là: http://www.cs.drexel.edu/~david/Clas...214-weiler.pdf

Mais je suis tombé sur le pdf que tu proposes, mais je ne vois pas comment générer les premières listes...donc j'avais cherché des exemples de code, mais pas moyen d'en trouver. D'où ma remarque que c'est le secret le mieux gardé d'internet. :)

Ce pdf (celui que tu proposes) est le plus complet que j'ai pu trouver, mais je bute sur comment établir les premières liste, celles des point et intersections des polygones. En effet, suivre le contour et detecter les collisions, c'est facile, mais je ne sais pas comment garantir que je mettrai les intersections que je detecte dans le bon ordre: après tout il n'y a aucune raison pour que je ne detecte pas l'intersection I0 avant I1 en cherchant les points de P0 à P1 (pour reprendre l'exemple du pdf) et dans ce cas, comment les remettres dans l'ordre? et si j'en ai plus de deux, par exemple de Q3 à Q0, même topo, je fais comment?

Et lors de mes recherches, j'ai aussi appris qu'il fallait faire particulièrement attention lorsque les points tombaient sur les segments de l'autre polygone, ou que les deux polygones partageaient un morceau de segment, mais sans trouver ce que voulait dire "faire particulièrement attention"...
Donc voilà, je sèche...

Merci :)

Pour les remettre dans l'ordre il tre suffit de comparer la distance entre chaque point par rapport à un des points du segment que tu es en train de traiter.

Pour P0 et P1 par exemple, tu peux évaluer les distances entre I0 et P1, I1 et P1, et les classer par ordre de distance décroissante. Cette méthode marche pour plusieurs points.

Pour éviter d'avoir à recalculer une seconde fois les intersection pour Q, tu peux mémoriser à quel segment de Q appartenait l'intersection trouvée. Et ensuite les classer par distance (croissante ou décroissante suivant le point de départ que tu prends pour ton polygone).

Par contre je ne sais pas si c'est ce qu'il y à de plus efficace.

Oui, je voulais eviter ça, ça me paraissait trop bourrin, mais après tout pourquoi pas.

par contre, je continue de secher sur les cas particuliers: comment faire lorsque un point est sur un segment de l'autre polygone, comment faire quand les polygone possede un segment en commun, etc...j'ai l'impression que ça va m'obliger a rajouter une tonne de tests, et ce qui etait un algo simple va devenir une usine a gaz...