Fiche d'exercices de calculs géométriques : ps pdf

Quelques programmes en rapport avec le cours. Il s'agit d'algorithmes classiques, dont on peut trouver des codes sources ailleurs sur le web ; voir par exemple la section computational geometry du Stony Brook Algorithm Repository. Néanmoins, certains détails dans mes implémentations sont peut-être originaux. Tous les programmes produisent une sortie en postscript.

1. Construction de l'enveloppe convexe d'un ensemble de points du plan, par l'algorithme de Graham : graham.tgz
2. Construction du diagramme de Voronoï d'un ensemble de points du plan, séparément pour chaque cellule de Voronoï. C'est un cas particulier d'un problème plus général : calculer les arêtes d'un polygone défini comme une intersection de demi-plans . L'algorithme est une adaptation de celui de Graham. L'adaptation est de moi, mais une version similaire a probablement déjà été décrite. voronoi.tgz
3. Construction de la triangulation de Delaunay d'un ensemble de points du plan, par une méthode incrémentale : delaunay_incremental.tgz
4. Construction de l'enveloppe convexe d'un ensemble de points de l'espace, par une méthode incrémentale : hull3D_incremental.tgz