Discussion :

[Chekov]

Bonjour,

j'ai un petit probleme de geometrie que je n'arrive pas à resoudre:

j'ai une liste de rectangles (4 coordonnées [x,y] par rectangle).
Je dois determiner le polygone englobant tous ces rectangles.

Avec le module Math-Geometry-Planar, j'arrive à obtenir le rectangle minimum englobant (plus grand que le polygone que je veux pouvoir obtenir en général) ou l'enveloppe convexe englobant ces polygones... qui est presque ce que je veux sauf que c'est convexe, justement... (c'est à dire encore plus grand que le polygone que je dois obtenir, generalement).

Sur l'image, on devine en traits fins 2 rectangles (1 petit et un plus grand dessous). En traits gras, c'est le polygone minimum englobant mes 2 rectangles. C'est ce que je veux obtenir, mais je n'y arrive pas.

Y-a-t-il un géomathématicien dans la salle ?

Merci de m'avoir lu...

[pseudocode]

il faut une methode optimisée pour les rectangles, ou une methode générale ?

[Chekov]

MMmh... il me faut une methode qui marche, je n'ai pas besoin d'un truc optimisé niveau vitesse d'exécution, je n'aurai pas des milliers de rectangles dans ma liste.

Je précisais juste ce dont je disposais. Mon principal souci, c'est le fait que le polygone final (l'enveloppe) peut etre concave.
Autre précision: je controle l'ordre et le sens des points de mes rectangles.

En fait, en terme math je crois que je cherche l'union de tous mes polygones ? mais je ne suis pas matheux, je cherche un pédagogue en plus d'un geomathicien

[Sylvain Togni]

Regarde du coté des algorithmes d'union de polygones, cela ce trouve facilement sur le net. Ton problème est juste un cas particulier ou tous les polygones sont des rectangles.

[pseudocode]

Oups... désolé pour l'attente, un petit pb avec une base SQL

En fait, en terme math je crois que je cherche l'union de tous mes polygones ? mais je ne suis pas matheux, je cherche un pédagogue en plus d'un geomathicien

Arf... pas de bol, moi je fais juste dans l'algorithmie.

MMmh... il me faut une methode qui marche, je n'ai pas besoin d'un truc optimisé niveau vitesse d'exécution, je n'aurai pas des milliers de rectangles dans ma liste.

Bon, deja il faut savoir que ce probleme (minimum area hull) n'est pas simple.

Une methode simple (mais pas rapide), consiste a partir d'un sommet (exterieur) et suivre une des arretes. A chaque intersection, on choisi de se déplacer sur une arrete qui mene directement a un sommet/intersection exterieur.

Ca a l'air compliqué comme ca, mais on peut faire plein d'optimisation et calculer les intersections et les points exterieurs au fur et a mesure de la progression.

Hum... je viens de me relire et ca n'a pas l'air clair. Essaye avec un papier et un crayon et dis moi si tu vois de quoi je parle...

[Chekov]

Une methode simple (mais pas rapide), consiste a partir d'un sommet (exterieur) et suivre une des arretes. A chaque intersection, on choisi de se déplacer sur une arrete qui mene directement a un sommet/intersection exterieur.

Ca a l'air compliqué comme ca, mais on peut faire plein d'optimisation et calculer les intersections et les points exterieurs au fur et a mesure de la progression.

Oui, je vois tout à fait la méthode, c'est comme ça que ferait mon cerveau, mais je ne vois pas comment écrire ça en code ... , le fait de suivre les arretes. Ca devient vectoriel là et ce n'est pas non plus mon fort (me demandez pas ce que je fous à faire ça, dans ce cas, svp )

Merci en tout cas pour ta réponse pseudocode

[pseudocode]

Oui, je vois tout à fait la méthode, c'est comme ça que ferait mon cerveau, mais je ne vois pas comment écrire ça en code ... , le fait de suivre les arretes. Ca devient vectoriel là et ce n'est pas non plus mon fort (me demandez pas ce que je fous à faire ça, dans ce cas, svp )

Merci en tout cas pour ta réponse pseudocode

Deja, si tu as pigé le principe, c'est bon.

Maintenant, tu peux chercher/copier/coller sur le net l'algo de Weiler-Atherton qui est une application de ce principe.