Discussion :

[poulette]

Bonjour,

J'ai un ensemble de segments dans un plan, chacun definis par 2 points.
Ces segments definissent un ou plusieurs polygones irreguliers concaves, qui peuvent avoir des intersections les uns avec les autres.
Je dois trouver les segments composants le contour de l'ensemble, c'est a dire le polygone concave enveloppant.
(Certains segments sont hors polygone)

Merci pour votre aide

un petit dessin pour clarifier les choses:

situation de depart:
..........................................
.......___________________..
......|............|............../......
......|............|............./.......
..__|__.........|.............\.......
..|......|.........|..............\......
..|___|..........|................\....
.....|.............|..................\...
.....|_______|___________\.
..........|...............................
..........|................................
........_|____.........................
..........\...............................

situation finale:
..........................................
.......________________.......
......|.........................../......
......|........................../.......
..__|...........................\.......
..|................................\......
..|__..............................\....
.....|................................\...
.....|__________________\.
..........................................

Je ne pense pas qu'il s'agit de trouver la distance minimale mais plutot le contour exterieur en eliminant tous les segments partie de segments parasites.

[Mac LAK]

Ton problème me fait énormément penser au classique "Problème du voyageur de commerce", la minimalisation de la distance étant remplacée par la concavité (d'ailleurs, pourquoi pas convexe ? ).
Tu devrais essayer une recherche sur le net sur cet algo, et voir si tu peux l'appliquer à ton cas.

[Kangourou]

salut,

je pense qu'il faut d'abord extraire les sommets des polygones generes par les segments.

puis, on peut calculer l'enveloppe convexe des sommets, ca sera forcement l'enveloppe convexe des polygones. (-> "Convex Hull").

Mais j'avoue que je vois pas trop le lien entre les segments et les polygones.

A+

[Mac LAK]

A moins que les segments ne doivent faire partie intégrante du polygone englobant, peut-être ?
J'avoue qu'un schéma serait le bienvenu pour mieux comprendre...
poulette, pourrais-tu faire deux dessins et les poster, histoire que l'on voie mieux le résultat demandé ?

[poulette]

J'ai complete le message initial par un dessin.

Pour chaque segment, j'ai les coordonnees des deux extremites.
Les segments ne sont pas triés initialement, ils sont dans un odre aleatoire.
Je peux calculer tous les points d'intersections.
Les segments composants le polygone final que je recherche a identifier sont forcement parmi les segments initiaux.

[plegat]

Salut,

Une idée vite faite...

Tu calcules toutes tes intersections, afin d'avoir un tableau de segments uniquement, sans intersection (au besoin couper les "droites" aux intersections)
Tu commences à virer tous les segments qui ont une extrémité libre. Tu boucles jusqu'à ce qu'il n'y en ait plus.
Tu cherches un segment qui va te permettre de déterminer l'intérieur et l'extérieur de ton polygone. En gros, tu cherches un segment qui ne soit connecté qu'à un seul segment à chaque extrémité, pas de connexion multiple. Tu orientes ton segment extrémité1->extrémité2, ce qui te permet de définir un côté "droit" et un côté "gauche". Tu détermines où se trouve l'extérieur du polygone en te basant sur la boite enveloppante de ton groupe de segments (le rectangle qui les contient tous). Si ça marche pas, tu changes de segment et tu reprends de puis le début de ce paragraphe... une fois l'extérieur déterminé, tu l'associe soit au côté droit, soit au côté gauche.
Ensuite tu parcours tes segments de proche en proche (dans le sens extrémité1->extrémité2). Dès que tu tombes sur un noeud à connexion multiple, tu cherches quel est le segment connecté qui est le plus à l'extérieur. Et tu vires les autres. Vu que tu as déconnecté quelques segments, là il faut relancer la première procédure, celle qui enlève les segments connectés qu'à une seule extrémité.
Et tu répètes jusqu'à ne plus avoir de connexion multiple dans ton ensemble de segments.

C'est pas très mathématique, mais c'est le principe qui me viens à l'esprit. Avec quelques tableaux et quelques produits scalaires, ça devrait donner quelque chose.

[Kangourou]

salut,

effectivement, ca parait une bonne piste.

j'essaierai de transformer la liste des segments en graphe planaire, avec des sommets aux extremites de segments, et ds aretes representant soit un segment, soit un segment coupe en 2.

Une premiere etape consisterait a ebarbuler le graphe pour ne garder que des sommets avec au moins 2 aretes.

La deuxieme etape est plus complexe :
j'y reflechi ce soir

A+

[poulette]

Merci pour toutes vos idees qui m'ont mise sur la voie.

La solution que j'ai retenue (et qui fonctionne pas mal) est en gros la suivante:
1 - calculer tous les points d'intersections et les nouveaux segments correspondants a ces intersections
2 - trouver le segment numero 1 : ayant un point le plus en haut a gauche
3 - a partir de ce segment, trouver tous les segments etant rattaches a son extremite et donc candidats pour etre le segment numero 2 en les orientant de facon a tourner autour de l'ensemble graphique dans le sens non trigo.
4 - parmi les segments candidats numero 2, retenir le segment formant l'angle le plus petit avec le segment numero 1, toujours dans le sens non trigo. Le segment numero 2 est ainsi obtenu.
5- chercher les segments candidats pour etre le segment numero 3 a partir du segment numero 2 en reprenant l'etape 3.
Continuer jusqu'a obtenir un segment bouclant sur le premier.

Les segments ainsi trouves sont stockes dans un arbre n-aires. En cas d'impasse (pas de segment candidats), on remonte dans l'arbre en supprimant la branche remontee et on reprend la recherche.

Les problemes que j'ai rencontres viennent essentiellement de segments qui ne sont pas tout a fait jointifs. J'ai donc mis en place une approximation qui gagnerait a etre parametree pour s'adapter a tous les cas.
Ces problemes de non jointement des segments sont engendres par le manque de precision des donnees initiales mais aussi par les arrondis realises durant les calculs d'intersections.