TD d'informatique No. 2 :
Calcul d'enveloppe convexe
Patrick Gros -- Patrick.Gros@irisa.fr
Didier Le Botlan -- didier.le_botlan@inria.fr
Lundi 20 novembre 2000
Le but du TD est de programmer le balayage de Graham. Ne perdez pas de temps
sur le premier exercice.
1 Enveloppe convexe : algorithme du cordeau
Le but de cet exercice est de programmer effectivement l'algorithme du cordeau vu en
PC. Pour cela, recopiez un fichier donnant la trame du programme chez vous :
cp ~pgros/tc_00_01/enveloppe_convexe.java .
Écrivez les fonctions suivantes :
-
fonction d'initialisation du tableau de points ;
- fonction d'affichage des points et du résultat ;
- modifiez la fonction main pour tester ces deux premières fonctions ;
- fonction qui cherche le point d'ordonnée minimale ;
- fonction de calcul de l'angle ;
- modifiez la fonction main pour tester l'ensemble.
2 Enveloppe convexe : balayage de Graham
On propose d'utiliser un nouvel algorithme plus rapide.
-
On trouve le point d'ordonnée minimale.
- On calcule l'angle associé à tous les autres points et on les trie par
angle croissant.
- On considère chaque point dans l'ordre comme prochain point de
l'enveloppe.
- Back-tracking : on revient en arrière pour assurer qu'on ne prend que
des virages à gauche.
- Éventuellement, on revient de plusieurs crans (boucle while).
Complexité : O(N log N). Modifiez le programme précédent pour qu'il utilise
ce nouvel algorithme.
Pour aller plus loin
Écrivez une nouvelle fonction qui permette de saisir les points avec la
souris au lieu de les tirer au hasard.
This document was translated from LATEX by
HEVEA.