TD 16 - Algorithmes géométriques


Ce TD est une suite d'exercices indépendants. Il est recommandé de les traiter dans l'ordre.

À la fin du TD, vous devrez déposer vos programmes en entrant dans une fenêtre terminal une commande :

/users/profs/info/Depot/INF_431/deposer [pgm] TD_16 [gpe]
[pgm] doit être remplacé par la liste des noms des fichiers contenant vos programmes et [gpe] doit être remplacé par votre numéro de groupe.

Éléments fournis

Le fichier Geometrie.java fournit de quoi démarrer ce TD. La classe Geometrie est exécutable en l'état pour un exemple.
Chaque sommet sera un objet de la classe Sommet, défini par ses coordonnées et ayant une couleur de dessin initialement noire.

La fonction static Sommet[] construire(int n, char mode, long seed) permet de construire un ensemble "aléatoire" de n sommets, le paramètre mode sera 'R', 'C', 'P' pour obtenir une distribution respectivement uniforme dans un rectangle, uniforme dans un cercle ou uniforme en polaire. Le paramètre seed sert à déterminer la séquence aléatoire. Deux appels avec les mêmes paramètres donneront des tableaux de sommets identiques, c'est ce qui est recommandé pour la mise au point. Les illustrations ci-dessous ont été obtenues pour les paramètres 20 'C' 0.
Pour avoir du "vrai"aléatoire, on pourra passer System.currentTimeMillis() pour valeur de seed.

Les dessins pour illustrer le fonctionnement des programmes seront réalisés avec MacLib, en utilisant ce qui est donné dans la classe Graphique.

Un graphique utilisant directement l'AWT est réalisable sur la base des TD précédents mais cela demande plus de travail. Il faut notamment gérer un ensemble de segments à dessiner. Cela pourra se faire après l'exercice 3.

On n'oubliera pas que pour les coordonnées graphiques, l'axe des y est orienté vers le bas. Une conséquence est que le sens trigonométrique correspond au sens des aiguilles d'une montre.

Exercice 1. Enveloppe convexe par l'algorithme de Jarvis

1.1 Sommet de départ

On part d'un sommet pour lequel il est facile de dire qu'il est sur l'enveloppe. On prendra, par exemple, le plus petit pour l'ordre lexicographique sur y puis x.
On marquera ce sommet en rouge (affecter son champ c = Color.red avant de le redessiner par Graphique.marquer).

1.2 Tour de l'enveloppe

Étant donné un sommet Pi de l'enveloppe, le sommet suivant sur l'enveloppe est le plus petit pour la relation d'ordre <i  définie par :
Pj <i Pk   <=>   angle(Pi Pj , Pi Pk) > 0

Cette définition a un sens car, vus d'un sommet de l'enveloppe, tous les autres sont dans un même demi-plan. On remarquera que seul le signe de l'angle est utile. Rappelons que cela se calcule comme le signe du produit vectoriel PiPj x PiPk.
En cas d'angle nul (3 sommets alignés), on prendra pour sommet suivant le plus éloigné de Pi.
On marquera ce sommet en rouge et on le reliera au précédent par un segment vert (appel de Graphique.relier avec Color.green). En faisant des appels à Graphique.attendre, on peut visualiser la construction pas à pas.

après 3 itérations à la fin

Le coût de cet algorithme est en O(N.n), avec N le nombre total de sommets et n le nombre de sommets sur l'enveloppe.

Exercice 2. Enveloppe convexe par l'algorithme de Graham

2.1 Étape préliminaire

On commence par trier les sommets par abcisses croissantes. Pour trier, on utilisera la procédure java.util.Arrays.sort(Object[] a) qui met en oeuvre un tri fusion (tri en O(N.log N), c'est l'étape la plus coûteuse de l'algorithme de Graham).
On passera donc le tableau de sommets à cette procédure et, au retour, ce tableau est trié. Cela demande que la classe Sommet implémente l'interface Comparable avec une méthode d'objet public int compareTo(Object o) qui retourne une valeur strictement négative, nulle ou strictement positive, selon que l'objet est strictement inférieur, égal ou strictement supérieur à l'argument o.

2.2 Marche de Graham

L'étape suivante est la "marche" de Graham. On va construire successivement les deux demi-enveloppes de part et d'autre de la droite qui joint les sommets d'abcisses extrêmes, P0 et PN-1.

Pour cela, on reclasse les sommets comme suit :
On conserve P0 comme premier sommet. On place ensuite, dans l'ordre du tri, les sommets Pi qui vérifient angle(Pi P0 , Pi PN-1) < 0, puis PN-1 et enfin, dans l'ordre inverse du tri, les sommets qui vérifient angle(Pi P0 , Pi PN-1) > 0.
Rappelons que la marche de Graham consiste à prendre les sommets un par un et, pour chaque nouveau point considéré, à retirer les précédents qui forment un angle concave. Cette marche se fait en O(N).

Voici ce que l'on obtient en traçant en vert quand on avance et en rouge quand on recule. Le trait bleu matérialise le segment P0 PN-1.

après 5 sommets à la fin

Exercice 3. Arbre couvrant minimal

Il s'agit de construire une arborescence qui couvre tous les sommets et telle que la somme des longueurs des segments soit minimale.

On procédera selon l'algorithme de Kruskal, en deux phases.

3.1 Préliminaires

On va commencer par définir une classe Segment dont chaque objet aura pour champs :
- les références sur ses 2 sommets extrémités,
- pour le graphique, une couleur (class Color) qui servira à tracer ce segment.
On construit ensuite l'ensemble exhaustif des N(N-1)/2 segments entre sommets distincts et on les trie par longueur croissante. Pour cela, on se servira de Arrays.sort comme pour l'exercice précédent.

Dans l'état initial, chaque sommet constitue une composante à lui tout seul.

3.2 Fusion des composantes

On prend les segments un par un, dans l'ordre du tri, et deux cas se présentent :
- soit les deux extrémités d'un segment sont dans la même composante, alors on ne fait rien,
- soit ce segment relie deux composantes distinctes, alors il appartient à l'arbre couvrant minimal et on réalise la fusion des deux composantes.

Pour déterminer si deux sommets sont dans la même composante, on ajoute à chaque objet Sommet un champ référence vers un autre Sommet, le "père". Cela détermine des arborescences, à ne pas confondre avec celle recherchée. Deux sommets sont alors dans la même composante s'ils ont la même racine en suivant les liens "père". La fusion de deux composantes se fait en disant que la racine de l'une prend pour père la racine de l'autre.

On pourra se contenter de dessiner l'arborescence recherchée en traçant les segments retenus au fur et à mesure. Si l'on veut mémoriser l'arborescence, on peut le faire sous la forme d'une liste de segments. Une structure plus exploitable serait de construire explicitement le graphe non orienté défini par ces segments.

Dans cet algorithme, c'est le coût du tri qui domine, soit O(N2.log N).

Pour faire plus efficace
Au lieu de partir des N(N-1)/2 segments, on peut partir des O(N) segments de la triangulation de Delaunay. La construction de cette triangulation et la preuve qu'elle contient l'arbre couvrant minimal seront vus en majeure 1 (d'informatique bien sûr). Pub !
On a ainsi une première phase en O(N.log N).
Pour éviter une dégénérescence quadratique de la gestion des composantes, on procède à des réductions de chemins en remplaçant à chaque occasion le père par la racine. C'est l'algorithme d'union-find qui permet d'avoir un coût très proche de O(N) pour la deuxième phase.

Exercice 4. Test d'appartenance d'un point à un polygone

4.1 Test par calcul d'angles

On commence par une méthode relativement simple qui s'applique à un polygone quelconque.

Soient Q le point à tester et Pi et Pi+1 deux sommets consécutifs du polygone. Notons ci le produit scalaire QPi . QPi+1 et si le produit vectoriel QPi x QPi+1. Alors l'angle de vision du segment PiPi+1 depuis Q, exprimé entre et , peut se calculer par Math.atan2(si, ci).
En sommant ces angles pour tous les segments du polygone, on trouve une valeur de la forme k.2&pi, où l'entier k donne le nombre de tours autour de Q. On dira que Q est à l'intérieur du polygone si et seulement si k est impair. Voici un morceau de code permettant de tester une fonction estDedans à écrire :

public static void main(String[] args) {
  Graphique.initialiser(Geometrie.TAILLE+2*Geometrie.MARGE);
  Sommet[] p = Geometrie.construire(20, 'C', 0);
  Graphique.remplir(p, Color.black);
  while ( true ) {
    Sommet q = Graphique.saisirPoint();
    if ( estDedans(p, q) )
      q.c = Color.green;
    else
      q.c = Color.red;
    Graphique.marquer(q);
  }
}
et le résultat attendu :

le polygone après quelques clics

Dans cet exemple, les valeurs de k, en suivant les clics de bas en haut, sont -1, 0, 1, 2 et 3.

Cette méthode est en O(N) mais avec des calculs coûteux et elle pose des problèmes de précision numérique.
On va maintenant s'intéresser à un algorithme basé sur un balayage. Dans le cas de polygones quelconques, on doit utiliser une adaptation de l'algorithme de Bentley et Ottmann pour gérer proprement les intersections. Pour simplifier, on va considérer ici le cas de polygones simples, c'est-à-dire dont les segments ne s'intersectent pas.

4.2 Construction d'un polygone simple

Pour construire un polygone simple à partir d'un ensemble de sommets, on peut reprendre la technique utilisée pour préparer la marche de Graham (cf. ex. 2). On obtient ainsi :

Par construction, ce polygone est monotone en x, mais on n'utilisera pas cette propriété.

4.3 Préparation du balayage

On va utiliser un balayage vertical en s'intéressant aux évènements particuliers que sont les débuts et les fins de segments. Il s'agit de reprendre les idées de l'algorithme de Bentley et Ottmann mais en tenant compte des simplifications possibles du fait qu'il n'y a pas d'intersection. En particulier, tous les évènements sont connus à l'avance et il suffit de les trier.

Pour décrire chaque évènements on va définir une classe YEvent qui devra implémenter l'interface Comparable. Dans la méthode compareTo on doit tenir compte de l'ordre des sommets directement concernés et des types des évènements. Pour l'ordre sur les sommets, on prendra l'ordre lexicographique sur y puis x. La méthode compareTo ne doit retourner 0 que lorsqu'on lui demande de comparer la même extrémité d'un même segment.
Un sommet peut être la fin d'un segment et le début d'un autre. Les deux évènements seront triés dans cet ordre.
Dans le cas d'un sommet de forme \/ ou /\, on peut se servir du prédicat d'orientation de 3 sommets (signe de l'angle).
Enfin, dans le cas d'un segment horizontal, le début sera le sommet de plus petite abscisse de manière à ce qu'il soit traité en premier.

Pour décrire l'état de la ligne de balayage, on va utiliser un objet de la classe java.util.TreeSet (basé sur un arbre rouge-noir) avec les 2 méthodes :

boolean add(Object o);
boolean remove(Object o);
Ces méthodes retournent false en cas d'opération erronée, add d'un objet qui est déjà dans l'arbre ou remove d'un objet qui n'est pas dans l'arbre. Il est conseillé de vérifier ces codes de retour, les incohérences éventuelles peuvent provenir d'une mauvaise relation d'ordre (transitivité non assurée).
Les objets de cet arbre seront des segments avec une relation d'ordre qui dit si un segment se trouve à gauche ou à droite d'un autre. Comme il n'y a pas d'intersection, cet ordre est bien défini pour tout couple de segments d'un polygone simple.
Pour éviter de modifier la fonction compareTo de la classe Segment, écrite pour l'ex. 3, on va utiliser un comparateur externe. Pour cela, on définit une classe CompareSegments implements Comparator avec une méthode public int compare(Object o1, Object o2) qui retourne une valeur strictement négative, nulle ou strictement positive, selon que l'objet o1 est strictement inférieur, égal ou strictement supérieur à l'argument o2.
Pour utiliser ce comparateur externe, on construira l'arbre par new TreeSet(new CompareSegments()).

4.4 Test d'un point

Pour tester l'appartenance d'un point (x,y), on effectue le balayage du polygone jusqu'à atteindre ou dépasser l'ordonnée y. L'objet TreeSet contient alors les segments intersectés par la ligne d'ordonnée y. Il reste à compter combien de ces segments se trouvent à gauche du point testé.
Pour obtenir les segments à tester, on utilisera la méthode Iterator iterator() de notre objet TreeSet qui retourne un objet de la classe Iterator dont les deux méthodes :
boolean hasNext();
Object next();
permettent d'itérer sur les objets de l'arbre (nos segments) selon leur ordre. La méthode next permet de les accéder séquentiellement et hasNext dit s'il en reste. Chaque itérateur ne peut être parcouru qu'une seule fois.

Cet algorithme est en O(N.log N), du fait du tri initial et des O(N) insertions et suppressions dans l'arbre. On va voir maintenant comment le coût du balayage peut être rentabilisé dans le cas où l'on doit tester l'appartenance pour un nombre important de points.

4.5 Tests consécutifs de plusieurs points

En préliminaire, on procède à un balayage complet et, pour chaque tranche, on conserve les segments obtenus par un Iterator dans un nouveau tableau. Pour dimensionner ce tableau, on peut utiliser la méthode size() de l'objet TreeSet qui retourne le nombre d'objets dans l'arbre.
Ainsi, en notant (yi) la suite strictement croissante des ordonnées distinctes de l'échéancier, on peut associer à chaque yi l'ensemble ordonné des segments qui sont coupés par toute ligne horizontale dont l'ordonnée est dans l'intervalle semi-ouvert [yi,yi+1[.
Cet phase préparatoire est en O(N2).

Pour tester un point, on commence par rechercher dans quelle tranche [yi,yi+1[ il se trouve, par une recherche dichotomique sur y. Le calcul du nombre de segments à gauche du point testé se fait ensuite par une autre recherche dichotomique dans le tableau associé à yi.
Le test d'appartenance d'un point au polygone est ainsi en O(log N).


URL: https://www.enseignement.polytechnique.fr/profs/informatique/Philippe.Chassignet/03-04/INF_431/td_16.html

Pour toutes suggestions, commentaires ou remarques, email : Philippe.Chassignet@polytechnique.fr