Calcul rapide d'enveloppe convexe

Sujet proposé par David Monniaux. Pale machine X2005.

On se propose ici de calculer, en fonction d'un ensemble P de n points du plan, un sous-ensemble E de ces points formant les sommets de l'enveloppe convexe de P ; c'est-à-dire que le polygone convexe délimité par E englobe tout P. Dans le cours, vous avez vu un algorithme dont le temps d'exécution peut être, dans le pire cas, proportionnel à n² ; nous nous proposons ici d'utiliser un algorithme dont le temps d'exécution dans le pire cas est proportionnel à n log n.

1. Calcul vectoriel

1.1 Définissez une classe Vecteur représentant des points du plan. Afin d'éviter les problèmes d'arrondis dans les calculs, on prendra des coordonnées entières pour l'abscisse et l'ordonnée, respectivement dans les champs x et y.

1.2 Définissez des méthodes dynamiques Vecteur moins(Vecteur p) et int det(Vecteur p), calculant respectivement t-p et det(t,p) où t est le vecteur représenté par this et p est le vecteur représenté par l'argument p. Nous vous rappelons que det(t,p)=t_x.p_y-t_y.p_x.

Testez votre code avec le programme suivant, à ajouter dans la classe Vecteur et à exécuter par java Vecteur :

    public String toString() {
	return("(" + x + "," + y + ")");
    }

    public static void main(String[] args) {
	Vecteur a = new Vecteur(3, 5), b = new Vecteur(4, 9),
	    c = new Vecteur(1, 4);
	System.out.println(a.moins(c));
	System.out.println(a.moins(c).det(b.moins(c)));
    }

Vous devez obtenir l'affichage :

(2,1)
7

2. Affichage

Téléchargez le fichier AffichageConvexe.java. Dans votre fichier Convexe.java, copiez la classe suivante :

class ListeVecteur {
		Vecteur valeur;
		ListeVecteur suivant;

		ListeVecteur(Vecteur valeur, ListeVecteur suivant) {
				this.valeur = valeur;
				this.suivant = suivant;
		}
		static int longueur(ListeVecteur l) {
				int i=0;
				for(; l!=null; l=l.suivant) i++;
				return i;
		}
}

2.1 Dans la classe Vecteur, ajoutez une méthode static Vecteur random(Random rng, int maxX, int maxY) qui devra rendre un vecteur aléatoire d'abscisse comprise entre 0 inclus et maxX exclu, d'ordonnée comprise entre 0 inclus et maxY exclu, uniformément distribué. rng.nextInt(n) permet d'obtenir un entier uniformément distribué entre 0 inclus et n exclu.

2.2 Dans la classe ListeVecteur, ajoutez une méthode static ListeVecteur random(Random rng, int largeur, int hauteur, int nbPoints) qui retournera une liste de nbPoints vecteurs aléatoires d'abscisses entre 0 inclus et largeur exclu et d'ordonnée entre 0 inclus et hauteur exclu.

2.3 Ajoutez également une méthode static int[] getX(ListeVecteur l, int delta) (respectivement, getY) donnant le tableau des abscisses+delta (respectivement, des ordonnées+delta) des vecteurs de l, dans le même ordre que dans l ; c'est-à-dire qu'on doit obtenir un tableau { l₁.x+delta, ..., t_n.x+delta } si l₁,...,l_n est la suite des vecteurs contenus dans la liste l.

Compilez Convexe.java et AffichageConvexe.java et lancez le programme par java AffichageConvexe ; vous devez obtenir un affichage d'un polygone aléatoire comme dans la figure suivante.

3. Tri des sommets

Nous proposons l'algorithme suivant de calcul de l'enveloppe convexe, en trois temps :

1. Trouver un point P d'ordonnée minimale et l'intervertir avec le premier élément de la liste de points.
2. Trier les autres points S suivant l'angle que PS fait avec l'axe des abscisses. On peut remarquer que cela revient à décider que S₁ est <, > ou = à S₂ suivant le signe de det(PS₁,PS₂).
3. Ne garder que les points faisant partie de l'enveloppe convexe, voir plus loin pour les détails.

Dans cette question, nous nous occuperons des deux premiers points. Le troisième point sera traité dans la question suivante.

Toutes les fonctions de cette question seront à insérer dans la classe ListeVecteur.

3.1 Programmez une fonction static Vecteur minimumY(ListeVecteur l) qui retourne un vecteur d'ordonnée minimale dans la liste.

Dans AffichageConvexe.java, vous trouverez une classe ListeLong (listes d'entiers longs) et des fonctions de tri fusion sur ces listes. Notez que la séparation en deux sous-liste procède en mettant un élément sur deux dans chaque sous-liste (ceux d'indice pair d'un côté, ceux d'indice impair de l'autre).

Nous vous proposons d'adapter ces fonctions de tri à des listes de vecteurs, avec le critère de comparaison : a < b (respectivement, = et >) si et seulement si det(a-p₀,b-p₀)<0 (respectivement, = et >).

3.2 Copiez/coller dans la classe ListeVecteur la procédure de tri des entiers que nous vous avons fournie, et modifiez la, afin d'obtenir static ListeVecteur trier(Vecteur p0, ListeVecteur l). Vous devez donc obtenir des fonctions :

• static ListeVecteur decoupe2(ListeVecteur l),
• static ListeVecteur decoupe1(ListeVecteur l),
• static ListeVecteur fusionner(Vecteur p0, ListeVecteur l1, ListeVecteur l2),
• static ListeVecteur trier(Vecteur p0, ListeVecteur l).

3.3 Programmez une fonction static ListeVecteur oter(Vecteur v, ListeVecteur l) qui, de façon non destructrice, va retourner une liste contenant tous les éléments de l dans le même ordre à l'exception de la première occurrence de v.

3.4 Programmez une fonction static ListeVecteur rearrange(ListeVecteur listePoints) qui retourne une liste avec les mêmes points que son paramètre, mais dans un ordre tel que :

• le premier vecteur p₀ de la liste est d'ordonnée minimale ;
• les vecteurs suivants sont triés suivant le critère vu ci-dessus.

4. Calcul de l'enveloppe convexe

Dans AffichageConvexe, décommentez AffichageConvexe.rearrange(points); avant enveloppe = points;. Si vous avez pu faire la question précédente, remplacez AffichageConvexe.rearrange par ListeVecteur.rearrange. Vous devez maintenant obtenir un polygone trié avec le point numéro 0 tout en haut de la figure, comme dans l'exemple suivant :

Nous allons calculer des enveloppes convexes de points[0], points[1], ..., points[k] pour k croissant, de sorte qu'à la fin nous avons l'enveloppe convexe de tous les points. À chaque étape, nous aurons une enveloppe convexe triée, que nous stockerons dans une pile, points[0] étant au fond de la pile et le dernier point ajouté étant au sommet.

Par souci de simplicité, on utilisera la classe Stack de la bibliothèque standard de Java :

• Stack<Vecteur> pile = new Stack<Vecteur>(); crée une pile de Vecteur et la met dans la variable pile.
• pile.push(a) pousse le Vecteur a dans la pile.
• pile.pop() retourne le Vecteur au sommet de la pile et l'ôte de la pile.
• pile.peek() retourne le Vecteur au sommet de la pile sans l'ôter de la pile.
• pile.empty() retourne true si et seulement si la pile est vide.

4.1 Programmez une fonction static ListeVecteur enveloppeConvexe(ListeVecteur points) qui va calculer l'enveloppe convexe des points, en utilisant une pile dans laquelle vous aurez mis initialement points[0] puis points[1] (en notant par abus de langage points[i] pour le i-ème élément de la liste), suivant l'algorithme suivant :

Si vous prenez b le point au sommet de la pile, a le point dans la pile juste sous le sommet, et p=points[i], alors vous avez les deux cas suivants :

• soit det(b-a,p-b) ≤ 0 et alors il faut rajouter points[i] dans la pile et passer à l'élément suivant de la liste (attention, nous avons bien écrit ≤ et pas <) ;
• sinon, il faut ôter b de la pile et reste sur le même élément de la liste.

Itérez cet algorithme jusqu'à la fin de la liste.

Dans AffichageConvexe, remplacez enveloppe = points; par enveloppe = Convexe.enveloppeConvexe(points); et testez votre programme.

4.2 Quelle est la complexité de la fonction enveloppeConvexe ? Vous pourrez, pour la déterminer, vous intéresser aux évolutions possibles du couple formé par le nombre d'éléments de la liste points restant à parcourir et par le nombre d'éléments dans la pile. Justifiez votre réponse. (Mettez la réponse en commentaire dans le programme.)

Explication de l'algorithme

Voici, pour les curieux, l'explication de l'algorithme, appelé marche de Graham.

Supposons maintenant que nous ayons calculé une enveloppe convexe triée E_n de points[0] à points[n], avec n>0. Regardons le point points[n+1]. De deux choses l'une :

• soit les points points[n-1], points[n], points[n+1] forment une « forme convexe » et alors E_n+1 est E_n avec points[n+1] rajouté au bout ;
• soit ces points forment une « forme concave » et alors on ôte le dernier point de E_n et on recommence.

Enveloppe de points[0] à points[6].

En examinant points[7], on s'aperçoit qu'il faut supprimer points[6] de la pile.

Après avoir examiné points[7], on l'ajoute à la pile.