TD 1 - Enveloppes convexes dans le plan

1. Convex Hull: l'algorithme de Andrew

Maintenant on va calculer l'enveloppe convexe d'un ensemble de points en 2D.
On a vu en cours plusieurs algorithmes: certains ayant complexité O(n log n). Habituellement c'est le balayage de Graham qui est illustré, mais nous allons implanter aujourd'hui une variante: l'algorithme de Andrew (esquissé en amphi), qui évite l'utilisation de fonctions trigonométriques et un tri sophistiqué (mais qui par contre doit manipuler deux listes).
L'algorithme calcule séparément les parties supérieure et inférieure de l'enveloppe convexe. Elles seront concaténées dans un deuxième temps.

Comme il s'agit de la première séance de TD, et vous ne connaissez pas encore de structures de donnés géométriques, on met à votre disposition:

le squelette de la classe ConvexHull dans le fichier ConvexHull.java, qui contient les signatures des méthodes à compléter,
une classe TestConvexHull qui permet de tester votre code (une fois écrit).
une classe EditorTD1 qui permet de manipuler et tester votre code de manière interactive.

Conseil: on vous suggère de commencer cet exercice en jetant un coup d'oeuil rapide à la classe ConvexHull: elle contient un certain nombre de types et structures qui pourraient vous faciliter l'accès à la librairie Jcg.

Voici quelques unes des classes et méthodes dont vous aurez besoin dans cet exercice:

Point_2 (dans le package Jcg.geometry): implémente les fonctions necessaires à manipuler des points en 2D (à coordonnées réelles, double)
Fenetre: pour visualiser un ensemble de points et segments
GeometricOperations_2 et GeometricPredicates_2 (dans Jcg.geometry.kernel): qui fournit un certain nombre de predicats géométriques approchés et exacts (par exemple un prédicat pour tester l'orientation d'un triangle)

Pour le tri des points, on peut utiliser des algorithmes déjà fournis par Java, par exemple à l'aide d'une class comparator, qui permet de personnaliser l'ordre sur les points dont on a besoin :

 class SortPointsByCoordinates
implements Comparator<Point_2> {
 
 public int
compare(Point_2 p1, Point_2 p2) {
 return p1.compareTo(p2);

}
 }

On pourra ensuite utiliser la méthode sort de la classe Collections, qui agit sur des structures implémentant l'interface Collection : par exemple, on peut utiliser un objet de type ArrayList<Point_2> pour stoquer une liste de points en 2D. Le tri de la liste l se fait ensuite par un appel à Collections.sort(l, new SortPointsByCoordinates()).

1a. Enveloppe convexe supérieure

Concentrons nous pour l'instant sur le calcul de la partie supérieure de l'enveloppe convexe, et appelons U la liste qui constituera cette partie.
Comme déjà vu en amphi aujourd'hui, il faut enlever les points de maniere incrementale pour le rendre convexe.Pour cela on va parcourir la liste de points de gauche à droite, et avant d'ajouter un nouveau point considéré v à la liste U, on fait la vérification suivante.
Tant que la liste

contient au moins deux eléments et
que le triangle formé par (v, u[1], u[2]) est orienté en sens horaire, on enlève le premier élément de la liste.

Ecrivez une méthode computeUpperHull(Liste points), qui permet de calculer l'enveloppe convexe supérieure.

1B. Enveloppe convexe inférieure

Ecrivez une méthode computeLowerHull(Liste points), qui permet de calculer l'enveloppe convexe inférieure: il suffit de modifier legerement le code précédent.

1C. Fusion des deux enveloppes

Et pour terminer, il reste juste à écrire une méthode permettant de fusionner les deux listes de points: ce qui termine le calcul de l'enveloppe convexe.
Tester avec la classe TestConvexHull.

2. Cas dégénérés (Facultatif)

Maintenant il reste à vérifier si votre code est robuste est permet de traiter les cas dégénérés et les erreurs provenant de problèmes liés aux arrondis (qui provoquent une perte de précision).

Tester votre code en modifiant la fonction main de la classe TestConvexHull, de manière à générer un nouveau nuage de points (cas dégénéré)

    	int n=100; // number of input points
    	// create input points at random
    	//ArrayList<Point_2> vertices=pointsInCircle(n); 
    	ArrayList<Point_2> vertices=degeneratePoints(n);

Que se passe-t-il?

Question: Modifier votre code de manière à rendre votre code robuste et capable de calculer les enveloppes convexes de manière correcte.