Fabien LE LEZ a écrit :
On Sat, 26 Apr 2008 14:34:27 +0200, Bertrand Lenoir-Welter :
tracer le contour délimitant un groupe de points dans un plan.
Ça, c'est typiquement le problème de l'enveloppe convexe...
.... qui doit être bien documenté sur internet, oui, c'est classique.
Histoire de donner une piste, une méthode possible (je dis pas que c'est
la meilleure, hein...) est de partir du point de X le plus petit (ou Y,
ou le plus grand, peu importe -- un point extrême) et de tourner autour
du nuage de points en faisant pivoter une droite autour de ce premier
point jusqu'à en trouver un deuxième, puis recommencer depuis ce
deuxième, jusqu'à boucler.
En plus, le contour peut avoir des concavités.
...sauf que non :-o
Si ton "contour" n'est pas forcément convexe, comment le définis-tu ?
Est-ce que relier tous les points, de proche en proche, ne répondrait
pas à la question ?
En modélisation d'objets géologiques (un peu mon domaine, donc je
connais ça, mais c'est sans doute similaire dans d'autres), on définit
par exemple des critères d'angle de concavité maximum ou de distance
maximale de l'enveloppe aux points (ou une combinaison des deux), pour
définir jusqu'où on peut "creuser" l'enveloppe convexe.
Par exemple, si un segment de l'enveloppe convexe passe à plus d'une
distance d de n'importe quel autre point (sauf ses deux extrémités),
alors on rajoute un point au milieu qu'on déplace suivant la médiatrice
du segment aussi loin que possible vers l'intérieur du nuage (ça marche
bien avec l'exemple du carré + le centre, on obtient une sorte d'étoile
à 4 branches). Dans ce cas, on se retrouve avec une enveloppe dont les
sommets ne sont pas tous des points du nuage (mais dans certains cas,
c'est une solution acceptable), mais on peut aussi ajouter un point
existant comme sommet intermédiaire.
Ce sont des problèmes qui surviennent quand on essaye par exemple de
faire des triangulations, ou plus généralement des tesselations, d'un
ensemble de points. Il doit y avoir de la doc disponible sur internet...
--
Rémi Moyen
