----- Original Message -----
From: "Bertrand Lenoir-Welter" <bertrand-dot-2008-at-galaad-dot-net>
Newsgroups: fr.comp.algorithmes
Sent: Saturday, April 26, 2008 2:34 PM
Subject: Contour d'un nuage de points


> 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.
via l'algo de Voronoi ou son pendant l'algo de triangulation de Delaunay
(cherche "convex hull"), vous pouvez trouver une solution (déjà implémentée
un peu partout).

> En plus, le contour peut avoir des concavités.
ça n'a guère de sens, les concavités n'ont de sens que si tes points sont
ordonnés (sinon il y a probablement autant de contours concaves différents
possibles que de points dans ton nuage ou presque...), par exemple rien
qu'avec cinq points, les sommets d'un quadrilatère, et un point à
l'intérieur, vous vous retrouvez avec 4 possibilité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.
>
> Bertrand
Armel