TD-10, Enveloppe convexe




Ce document est disponible à l'URL http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/TC/TD-10

Envoyez vos programmes à Luc.Maranget@inria.fr. Les solutions sont ici.

1 Méthode incrémentale
Le but de cet exercice est la présentation d'une méthode finalement simple pour construire l'enveloppe convexe d'un ensemble de points donnés au fur et à mesure.

1.1 Principe
On s'abstient de parler d'enveloppe convexe de zéro, un ou deux points et on suppose que les points sont en position générale (ils sont tous distincts deux à deux et aucun triplet n'est aligné si j'ose dire).

Les polygones (convexes) seront représentés par la liste de leurs points pris dans le sens trigonométrique. On note Cn un polygone à n côtés. Voici par exemple le polygone C5 = A0, A1, A2, A3, A4 :
On remarquera que chaque vecteur (AiAi+1) divise le plan en deux demi-plans caractérisés par le signe du déterminant det((AiP), (AiAi+1)) (on considère aussi la dernière arête (An-1A0)). Grâce à la convention sur l'ordre des sommets l'intérieur du polygone est défini par les déterminant positifs. Soit, si on considère un point P on peut facilement situer P par rapport à chaque face orientée (AiAi+1) en calculant un déterminant. Au passage, ce calcul nous permet de savoir si P est à l'intérieur de Cn ou pas (tous les déterminants positifs ou pas). Au passage encore, on ignore le cas des déterminants nuls (trois points alignés), exclu par hypothèse.

Il nous permet également de savoir si une arête est visible du point P ou pas. En effet, la convexité de Cn entraîne que l'arête (AiAi+1) est visible de P, si et seulement si le déterminant det((AiAi+1), (AiP)) est négatif. Intuitivement, un rayon lumineux partant de P et frappant l'arête pointe alors vers l'intérieur de Cn. Un sommets est éclairé lorsqu'une au moins des arêtes qui le touchent est visible. Il existe alors deux sommets importants, le premier sommet visible et le dernier en suivant le sens positif de rotation (sur la figure A2 et A4).
Or, on peut fabriquer l'enveloppe convexe de Cn union {P} en supprimant toutes les arêtes visibles de Cn et en ajoutant une arête du permier sommet visible à P suivie d'une arête de P au dernier sommet visible. On obtient alors le polygone :

Le principe de l'algorithme est donc d'attendre d'avoir trois points, de les ordonner selon le sens positif. Puis, pour chaque nouveau point, on étend le polygone convexe créé à l'étape précédent selon la méthode exposée ci-dessus. Vous trouverez ici un exemple d'application de l'algorithme.

1.2 Environnement de programmation
Les enveloppes convexes sont représentées par des listes de points, définies par la classe PointList. Les points sont la classe Point de la MacLib. Outre les habituels constructeur et méthode toString(). Il existe une méthode draw() qui dessine le polygone dans le fenêtre graphique.

La classe Anim définit l'animation graphique elle possède les méthodes suivantes :
  1. Une méthode d'initialisation : 
      static void init()
  2. Deux methodes de tracé, pour les points et les lignes. 
      static void point(Point p)
  static void line (Point p, Point q)
  3. Des méthodes pour changer la couleur du tracé. 
      static void white() // Pour effacer.
  static void black() // Normal
  static void red()   // Visible
  static void blue()  // Caché
  4. Enfin deux méthodes de contrôle. 
      static void pause (int ms)
  static void await()
    Pour faire une pause de ms milisecondes ou attendre un clic de souris.
Pour lire les points, on utilise une classe abstraite PointReader. Cette classe déclare une unique méthode next() qui renvoie le prochain point. Elle est sous-classée par deux classes concrètes, PointWindowReader et PointFileReader pour, respectivement, prendre les points à la souris, ou les lire dans un fichier. Dans ce dernier cas next renvoie null à la fin du fichier.

1.3 Un exemple
Pour voir un peu comment fonctionne le tout, récupérez les classes PointList, Anim, PointReader, PointWindowReader et PointFileReader. Ainsi que le source Demo. Compmilez tout et lancez ``java Demo'' Vous devriez pouvoir tracer un chemin quelconque dans la fenêtre graphique. En lançant ``java Demo a.points'', les points sont lus dans le fichier a.points, le dernier point est connu et le chemin affiché est fermé.

1.4 À vous de jouer
Écrire la classe Convexe qui calcule l'enveloppe convexe selon la méthode incrémentale.

Les difficultés à prévoir sont relatives à des questions de signe (dedans/dehors, positif/négatif ?), et à la gestion de la liste de points (identifier les premiers et derniers sommets visibles, enlever des points, ajouter des points, maintenir l'ordre trigonométrique). La règle de jeu est d'écrire un code de coût au pire linéaire en la taille de l'enveloppe convexe à augmenter, afin de garantir une complexité au pire quadratique en le nombre de points traités.

Il est vivement conseillé de developper une animation graphique en parallèle avec le code de l'algorithme. Ça aide beaucoup à comprendre ce qui se passe.

Pour les tests, vous pouvez répéter des scénarios, car dans le cas de la lecture à la souris, les coordonnées des points entrés s'affichent. Vous pouvez ensuite mettre ces coordonnées dans un fichier et lancer votre programme avec le nom du fichier en argument. Voici également deux tests ex.points (exemple d'application de l'algorithme) et a.points.

Lorsque votre programme fonctionne réflechissez au cas des points alignés (exemple biz.points), ou confondus (exemple violent.points).

Solution.

2 Faire mieux
Il existe des méthodes de calcul de l'enveloppe convexe en O(nlog(n)) (qui sont plutôt linéaires en un nombre de points triés, voir la planche 10 du cours). Il est possible d'atteindre cette complexité à partir du principe incrémental de l'exercice précédent. Il y a deux voies, qui ne s'appliquent évidemment que si tous les points sont connus avant de commencer à calculer l'enveloppe convexe.

2.1 Trier les points
Suposons une liste de points triés selon l'ordre lexicographique. On se place ensuite à une étape donnée, enveloppe convexe Ck, point Ak+1. En raison de l'ordre lexicographique, le point Ak appartient à C(k) et est visible de Ak+1. Or, la construction de C(k+1) demande en fait la seule connaissance des premiers et derniers sommets visibles, que l'on peut atteindre à partir de n'importe quel sommet visible en reculant et avançant dans la liste des points. À l'aide d'une structure de données adaptée pour les polygones (typiquement une liste doublement chaînée, pour pouvoir tourner dans les deux sens), on pourra identifier ces sommets importants en en coût proportionel au nombre de faces visibles à chaque étape, c'est à dire proportionel au nombre de points enlevés de C(k) à chaque étape. Soit un coût au pire linéaire (c'est rapide, mais c'est le même argument que pour la marche de Graham).

Le fonctionnement de Convexe sur un ensemble de points préalablement triés, donne une idée de ce qu'il faut faire.

2.2 Diviser pour regner
À chaque étape récursive, diviser l'ensemble des points en deux (à gauche et à droite d'un axe vertical par exemple). Recurser pour chacun des sous-ensemble de points et fusionner les deux enveloppes convexes ainsi créés. La fusion demande simplement (!) d'identifier le premier et dernier point visible de chaque polygone par rapport à l'autre, une opération linéaire en la somme des nombre de points des polygones, si l'on s'y prend bien.

Une technique est de trier les points au préalable selon l'ordre lexicographique. On considère ensuite le point maximal du polygone de gauche et minimal du polygone de droite (mutuellement visibles, si j'ose dire). On fait ensuite monter une droite, tant que son extrêmité gauche (droite) est visible de l'arête précédant son extrêmité droite (suivant son extrêmité gauche). La recherche s'arrête lorsque l'on a trouvé le dernier point visible du polygone de gauche et le premier point visible du polygone de droite.
On trouve les deux autres points par une procédure symétrique (faire descendre la droite). Dans certains cas, un des polygones est entièrement visible de l'autre et il faudra faire un peu attention :

On notera qu'il n'est pas besoin en fait de trier les points au préalable, mais alors la séparation équitable des deux ensembles de points devient un cauchemar. En fait on notera l'analogie entre calcul de l'enveloppe convexe et tri, la méthode incrémentale simple ressemblant à un tri par insertion/selection (comparer un élément aux eléments triés précédamment), la méthode ci-dessus ressemblant à quicksort. Les methodes qui commencent par trier les points obscurcissent un peu l'analogie.

3 Méthode analogique peu coûteuse
Prendre une planchette et planter un clou pour chaque point (coût en n, avec un bon marteau). Prendre un élastique, entourer tous les clous et relacher l'élastique (temps constant, ou proportionel à l'allongement de l'élastique, plus le temps de rétraction de l'élastique, négligé). Noter les clous qui touchent l'élastique en tournant dans le sens inverse des aiguilles d'une montre (proportionnel au nombre de points de l'enveloppe convexe). Résultat, un algorithme plus ou moins linéaire, usant d'un matériel anodin disponible pour un prix dérisoire dans toute bonne quincaillerie (hardware shop ?).
Dernière modification : 2002-11-27
Ce document a été traduit de LATEX par HEVEA.