Bertrand Lenoir-Welter <bertrand-dot-2008-at-galaad-dot-net> writes:

Bonjour

Petite question de géométrie : je cherche un algorithme ou une piste de
travail pour tracer le contour délimitant un groupe de points dans un
plan. Chaque point a une coordonnée (X,Y) et l'on considère qu'ils sont
relativement groupés, mais ne sont pas dans une matrice cartésienne bien
ordonnée. En plus, le contour peut avoir des concavités.

Pour le moment, je choisis le premier point comme étant celui de plus
grande coordonnée X, et ensuite... ensuite je sèche.

Merci d'avance pour toute idée même baroque.

Je partirais de quelque chose comme:

1/ calculer une triangulation de Delaunay

2/ partir de l'enveloppe convexe

3/ faire sauter de l'enveloppe les cotes des triangles de la triangulation
de Delaunay dont l'angle au sommet qui n'est pas sur l'enveloppe est
superieur a un angle donne (sur deux ou trois petits dessins, l'angle droit
semble une bonne proposition, plus il est eleve, moins tu acceptes de
rentrer dans l'enveloppe convexe -- si je ne me trompe pas, utiliser
l'angle droit peut s'interpreter comme la contrainte qu'aucun point
exterieur a l'enveloppe n'est plus proche d'un point interieur a celle-ci
que d'un sommet de l'enveloppe, ce qui semble aussi un assez bon critere en
soi).

A+

--
Jean-Marc
Site de usenet-fr: http://www.usenet-fr.news.eu.org