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.

[akoril]

Je ne suis pas sur que la méthode fonctionne si le sens de rotation des points est différent dans les 2 polygones.

A savoir, , la surface d'un polygone est la moitié de la Somme(0-n)(xi * (yi+1 - yi-1))
Sachant que le résultat est signé en fonction du sens du parcours du polygone (trigo ou topo), on a donc une fonction qui permet de signer le sens et éventuellement d'inverser un des polygones...

..., ou encore deux points confondus.

Pour une intersection entre P et Q, si elle est aussi un sommet d’un des polygones et si on ne peut déterminer si on (vas) rentrer ou sortir de Q, on peut regarder voir si on était à l’intérieur ou pas, on teint compte du sommet uniquement si notre état change…
- Plus tard ce dernier changera, en fait quand les segments ne seront plu superposés .
- On peut connaître notre état de départ en regardent si le premier sommet de P est ou non, à l'intérieur de Q. (on compte le nombres d'intersection entre une demi-droite horizontale passant par P0 et le polygone Q...).

Ou bien, connaissant le sens du polygone Q, par rapport au segment intersecté Qe-Qf on regarde si on vient de droite ou de gauche...

On peut utiliser les algos SAM et SIAM qui permettant rapidement de voir si il y a une intersection (sans la calculer) et savoir si par rapport a un segment d'où on vient et où on vas (intérieur, commun, extérieur).

Bonne chance, y'a du taff

Une autre solution, consisterait à trianguler ( concave ) les deux polygones, et a découper les triangles qui se croisent, pour n’avoir au final que des triangles de P ou Q ou commun. A voir, suivant le type de résultat voulu ?

[Nemerle]

akoril>> tu peux éviter STP les , on a l'impression que tes chevilles enflent trop, surtout par rapport à ta contribution, très scolaire

[Graffito]

Bonjour,

A savoir, , la surface d'un polygone est la moitié de la Somme(0-n)(xi * (yi+1 - yi-1))
Sachant que le résultat est signé en fonction du sens du parcours du polygone (trigo ou topo), on a donc une fonction qui permet de signer le sens et éventuellement d'inverser un des polygones...

Bien vu, si il existe une formule lorsqu'il s'agit non pas d'un polygone plan, mais d'un "polygone" défini sur la surface sphérique du globe par les coordonnées polaires des points, je suis preneur ...

[Rakken]

Bonjour,

Alors voila, je fait parti de ces informaticiens qui n'ont toujours été des quiches en math et même si j'admire Nemerle pour sa vision mathématicoinformatique, je dois avouer que je n'ai jamais vraiment réussi à faire le lien entre une formule mathématique et un algo.

Pour moi, un polygone, c'est quoi ? C'est juste une grande série de point stockée dans un tableau.
L'algo que je vais proposer n'est pas necessairement applicable dans tous les cas, c'est juste une idée comme ca, en passant (pour être vraiment honnete, je ne sais même pas s'il est vraiment applicable).

Si j'ai bien compris, ce que tu veux, c'est le contour extérieurs de tes polygones (je ne vais pas détecter les "creux" dans l'intersection des polygone).
Prennons un grand tableau qui représentent une feuille ou serai dessiné tes deux polygones. Chaque case de ton tableau représente un "pixel". De base, tout est a 0. Maintenant, tu "dessines" ton premier polygone dans le tableau (oui, je sais, ca exige d'interpoler les points en fonction des coordonnées de départ, et ca c'est des maths, mais notez comme je ne dis pas comment faire pour interpoller ) en mettant des 1 dans les cases adéquate.
Tu fait pareil, en mettant des 2 pour le second polygone (en fesant une addition binaire, pour ne pas perdre l'information du premier polygone).
Et maintenant, tu colorie ton tableau, en partant que tu sais être a l'extérieur de la forme de ton polygone final (ne serait-ce que parce que tu as construit ton tableau avec une ligne en plus, expres pour). Genre tu prend un 0 dans un coin et tu colories de proche en proche tout ses ptits copains en fesant de nouveau une addition binaire avec 4. Il faut que tu colorie également les traits, (genre la ou tu avais précédament stocké dans ton tableau des 1/2/3) mais sans les dépasser.

Une fois tes joyeux coloriages fait, tu obtiens une super représentation en 2d de l'extérieur de tes polygones.
Tous les points de ton tableau qui sont > 4 sont de fait, les contours de ton polygone.

Enfin bref, voila, c'étais juste une idée en passant. Ceci dit, après vous avoir détendu quelques instant avec ce fabuleux algo a la rapidité défiant toute concurence de faire pire, je crois quand même que... pour le coup, une solution mathématique, c'est quand même mieux ^_^

--
Rakken, qui s'amuse comme il peut.

[akoril]

Graffito

akoril>> tu peux éviter STP les , on a l'impression que tes chevilles enflent trop, surtout par rapport à ta contribution, très scolaire

Ma contribution scolaire vient de MA propre expérience... Je ne m'appuie pas sur des algos des autres, mais sur des développements que j'ai déjà réalisés. J'essaie d'être simple et clair c'est tout.

Je ne voie pas ce que a de prétentieux... il agrémente surtout la lecture...
Mais tu en fait ce que tu veux, je m'en tape.

PS: Sinon dans mon post précédent, je répondais à aidos

[Nemerle]

Je ne voie pas ce que a de prétentieux... il agrémente surtout la lecture...
Mais tu en fait ce que tu veux, je m'en tape.

http://www.developpez.net/forums/showthread.php?t=7

entre autre politesse et style sobre. Si tu considères que les sont des agréments, si tu ne vois pas ton post était suffisant, je ne peux rien pour toi.

Et pas la peine de dire encore que tu t'en tapes, on a compris.