Parcours de Graham

En informatique, et en géométrie algorithmique, le parcours de Graham (aussi appelé algorithme de Graham[2]) est un algorithme pour le calcul de l'enveloppe convexe d'un ensemble de points dans le plan. Son principal intérêt est sa complexité algorithmique en O(n log n) où n est le nombre de points. Cet algorithme doit son nom à Ronald Graham, qui a publié l'algorithme original en 1972[3].

Animation de l'algorithme de Graham[1].

Algorithme

L'algorithme prend en entrée un tableau de points, comme montré sur la figure suivante :

Entrée du problème : un tableau de points[1].

Calcul d'un point pivot

La première étape de cet algorithme consiste à rechercher le point de plus petite ordonnée, appelé pivot. Si plusieurs points ont la même plus petite ordonnée, l'algorithme choisit parmi eux le point de plus petite abscisse. Comme montré dans la figure suivante, le pivot est le point le plus en bas à gauche. Le pivot devient maintenant le point numéro 1.

Choix du pivot, le point le plus en bas à gauche[1].

Tri des points

L'ensemble des points (le pivot compris) est ensuite trié en fonction de l'angle que chacun d'entre eux fait avec l'axe des abscisses relativement au pivot. N'importe quel algorithme de tri par comparaison convient pour cela, par exemple le tri par tas ou le tri fusion (qui sont optimaux et ont une complexité de O(n log n)). Pour cela, il n'est pas nécessaire de calculer l'angle réel ; on peut se limiter à la comparaison des tangentes, ou bien même utiliser le produit en croix des coordonnées pour connaître les positions relatives des points. À l'issue de cette étape, on dispose d'un tableau T contenant les points ainsi triés. La figure suivante montre les points qui ont été renumérotés afin de respecter l'ordre du tri.

Points triés selon l'angle par rapport au pivot[1].

Itérations

L'algorithme construit itérativement l'enveloppe convexe (en vert sur la figure suivante). On débute avec le pivot. Puis on examine les points dans l'ordre du tableau trié (le point à examiner est représenté en noir). À chaque étape, on regarde s'il y a un « tournant à gauche » (comme dans les étapes 2, 5, 13, 15 sur l'exemple donné dans la figure) ou un « tournant à droite » (comme dans les étapes 10, 17, 18 de l'exemple).

  • Si l'algorithme rencontre un « tournant à droite », cela signifie que le point qui finissait le polygone en création (le point en rouge) est à gauche du segment formé par l'avant-dernier point du polygone en création et le point considéré (point en noir). Dans ce cas, le dernier point (celui en rouge) ne fait pas partie de l'enveloppe convexe et doit donc être rejeté. Ces rejets se répètent tant qu'il y a un « tournant à droite » (comme montré par les étapes 17 et 18).
  • Si l'algorithme rencontre un « tournant à gauche », l'algorithme passe au point suivant dans le tableau trié. (Cas limite : si l'on rencontre trois points alignés, à quelque étape que ce soit, on peut choisir de conserver ou de rejeter le point considéré, au choix, suivant la définition que l'on choisit pour l'enveloppe convexe : en effet certaines applications requièrent que tous les points sur l'enveloppe soient compris dans l'enveloppe).

À la fin (étape 19 puis 20), l'algorithme a calculé l'enveloppe convexe.

Exemple d'itérations de l'algorithme de Graham[1].

Déterminer si trois points constituent un « tournant à gauche » ou un « tournant à droite » ne requiert pas de calculer l'angle réel entre les deux segments, et peut être réalisé par simple arithmétique. Pour trois points (x1, y1), (x2, y2) et (x3, y3), il suffit de calculer le sens du produit vectoriel des deux vecteurs définis par les points (x1, y1), (x2, y2) et (x1, y1), (x3, y3), donné par le signe de l'expression (x2 – x1)(y3 – y1) – (y2 – y1)(x3 – x1). Si le résultat est nul, les points sont alignés. S'il est positif, les trois points constituent un « tournant à gauche ». Dans le cas contraire, c'est un « tournant à droite ».

Ce processus retournera finalement au point auquel il a commencé, auquel cas l'algorithme sera terminé, et retourne les points formant l'enveloppe convexe, dans l'ordre inverse des aiguilles d'une montre : sur l'exemple, les points numéro 1, 2, 3, 6 et 9.

Complexité algorithmique

La complexité en temps du choix du pivot est en O(n), n étant le nombre de points de l'ensemble. Le tri des points peut se faire avec une complexité en temps en O(n log n). La complexité de la boucle principale peut sembler être O(n2), parce que l'algorithme revient en arrière à chaque point pour évaluer si l'un des points précédents est un « tournant à droite ». Mais elle est en fait en O(n), parce que chaque point n'est considéré qu'une seule fois. Ainsi, chaque point analysé ou bien termine la sous-boucle, ou bien est retiré de T et n'est donc plus jamais considéré. La complexité globale de l'algorithme est donc en O(n log n), puisque la complexité du tri domine la complexité du calcul effectif de l'enveloppe convexe.

Pseudo-code

Soit T un ensemble de points à examiner, représenté sous la forme d'un tableau indexé à partir de un. Au cours de l'algorithme, le polygone en cours de construction est stocké dans une pile.

 fonction parcours_de_Graham(T[1,.., n])
     trouver le pivot et le placer en T[1];
     trier le tableau T[2..n] par angle croissant par rapport au pivot (les points d'angle égal seront triés par abscisse croissante)
     pile.empiler(T[1]);
     pile.empiler(T[2]);
     pour i = 3 à n
         tant que (pile.hauteur >= 2) et (T[i] à droite du segment [pile.second, pile.sommet])
                 pile.dépiler;
         pile.empiler(T[i]); 
     retourner pile

où pile.sommet désigne le point qui est sur le sommet de la pile et pile.second désigne le point sous le sommet de la pile. Pour tester qu'un point A est à gauche d'un segment [BC], on vérifie que le produit vectoriel est négatif, c'est-à-dire on vérifie que produitVectoriel(A, B, C) ≤ 0 où produitVectoriel est défini par :

 fonction produit_vectoriel(A, B, C)
       retourner (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);

Note : pour gérer les cas dégénérés où l'enveloppe convexe a moins de trois points, un seul point devrait être entré dans la pile au départ, et si jamais la pile a moins de deux points (elle en aura au moins toujours un), alors le sommet de la pile devrait être également sorti si le nouveau point est le point considéré. En d'autres termes, la condition du « tant que » devrait être comme suit.

pile.hauteur >= 2  et produit_vectoriel(pile.second, pile.sommet, T[i]) <= 0
     ou  pile.sommet == T[i]

Discussions

Comparaison avec d'autres algorithmes

Au lieu de trier selon l'angle, on peut trier selon les abscisses, puis on construit l'enveloppe convexe en deux étapes : la partie supérieure puis la partie inférieure. Cette modification a été créé par A. M. Andrew[4] et s'appelle le Andrew's Monotone Chain Algorithm. Ce nouvel algorithme a les mêmes propriétés que l'algorithme de Graham[5].

L'utilisation d'une pile dans l'algorithme de Graham est similaire à celle faite dans l'algorithme pour le problème all nearest smaller values. D'ailleurs, il y a des algorithmes parallèles pour ce problème qui peuvent être utilisés pour calculer l'enveloppe convexe plus efficacement[6].

Robustesse numérique

La robustesse numérique concerne le comportement d'un algorithme par rapport à la précision des nombres flottants. Un article de 2004 étudie comment et pourquoi l'algorithme de Graham peut mal se comporter à cause d'une mauvaise précision[7]. L'article[8] propose une solution. Une extension de l'algorithme Graham, appelée algorithme Graham-Fortune[9] est plus stable.

Notes et références
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Graham scan » (voir la liste des auteurs).
  1. « Code source pour créer les illustrations. »
  2. « Cours à l'université de Grenoble »
  3. (en) R. L. Graham, An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set', Information Processing Letters 1, 1972, p. 132-133.
  4. A. M. Andrew, « Another efficient algorithm for convex hulls in two dimensions », Information Processing Letters, vol. 9, no 5,‎ , p. 216–219 (DOI 10.1016/0020-0190(79)90072-3)
  5. (en) Mark De Berg, Otfried Cheong, Marc Van Kreveld et Mark Overmars, Computational geometry : algorithms and applications, Berlin, Springer, , 2–14 p. (ISBN 978-3-540-77973-5, DOI 10.1007/978-3-540-77974-2, lire en ligne)
  6. Omer Berkman, Baruch Schieber et Uzi Vishkin, « Optimal double logarithmic parallel algorithms based on finding all nearest smaller values », Journal of Algorithms, vol. 14, no 3,‎ , p. 344–370 (DOI 10.1006/jagm.1993.1018).
  7. Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra et Chee Yap, « Classroom examples of robustness problems in geometric computations », Computational Geometry, vol. 40, no 1,‎ , p. 61–78 (DOI 10.1016/j.comgeo.2007.06.003, lire en ligne) (An earlier version was reported in 2004 at ESA'2004)
  8. D. Jiang and N. F. Stewart, Backward error analysis in computational geometry, Computational Science and Its Applications - ICCSA 2006 Volume 3980 of the series Lecture Notes in Computer Science, pp 50-59
  9. Fortune, S. Stable maintenance of point set triangulations in two dimensions. Proceedings of the 30th annual IEEE Symposium on Foundations of Computer Science Vol. 30, 494-499, 1989.

Voir aussi

Articles connexes

Liens externes
  • Portail de la géométrie
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.