Le 28/04/2008 08:58, Jean-Marc Bourguet a écrit :

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

Cette idée me semble pas mal, en tout cas je ne crois pas qu'elle ait le
défaut visible dans la proposition de Jean-marc sans nom, à savoir que
certains points qui semblent très près de l'enveloppe sont oubliés alors
que d'autres plus lointains sont conservés.


J'ai une autre proposition qui donne peut-être le même résultat que le
tien en choisissant l'angle droit.

1) Déterminer l'enveloppe convexe.

2) Pour chaque segment AB de l'enveloppe, chercher un point « assez
proche du segment AB » selon la définition donnée ci-dessous.

3) Si un tel point M existe, remplacer AB par AM et MB, puis réappliquer
le point (2) à chaque nouveau segment créé, etc.


On considère qu'un point M est assez proche du segment AB si l'angle AMB
est supérieur à un angle donné (par exemple l'angle droit). Or tous les
points M en question sont compris entre le segment AB et un arc de
cercle passant par A et B. Lorsque l'angle est l'angle droit, le centre
du cercle en question est le milieu du segment AB ; lorsque l'angle est
strictement supérieur à l'angle droit, le centre du cercle est quelque
part sur la médiatrice de AB, à l'extérieur du contour.

Pour chaque segment AB, il suffit alors de déterminer I, le milieu de
AB, puis O, le centre du cercle, puis de chercher s'il existe des points
M tels que |OM| < |OA| = |OB|. Si oui, on choisit le plus proche d'entre
eux. La distance |IO| est très facile à calculer puisque le rapport
|IO|/|AB| est une constante pour un angle theta donné. Si je ne me suis
pas trompé dans les calculs, en posant t = tan(theta/2) on a :
 |IO|/|AB| = (1-t²)/(4t)


Je suis désolé de ne pas savoir faire facilement un dessin, et j'espère
ne pas m'être trompé dans les calculs...

Cordialement,
--
Olivier Miakinen