Enveloppe convexe d'un nuage de points
Ces travaux pratiques sont à effectuer seul.
Les réponses aux exercices sont à envoyer à mon adresse mail avant la séance suivante.
Le but de ces travaux pratiques est de vous faire écrire un programme qui va permettre de calculer l'enveloppe convexe↓ d'un nuage de points en utilisant un ou plusieurs algorithmes, en fonction de vos avancement.
Il existe au moins deux algorithmes fameux : la marche de Jarvis et le parcours de Graham.
La marche de Jarvis est peut-être plus simple à écrire pour commencer, mais le parcours de Graham est intéressant du fait de sa complexité en O(n log(n)).
Il vous est demandé d'écrire une ou plusieurs classes permettant de déterminer l'enveloppe convexe d'un nuage de points. Pour cela, vous pouvez vous aider de classes utilitaires que vous écrirez, telles qu'une classe point et une classe arrête par exemple.
L'entrée de votre programme se fera au travers d'un fichier texte décrivant le nuage de points comme un ensemble de couples dans le plan. Un exemple de fichier est fourni↓.
La sortie de votre programme devra se faire également dans un fichier qui contiendra la liste des points constituant l'enveloppe convexe.