----- 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