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].
Enveloppe convexe
Un ensemble est convexe si, lorsque l'on prend deux points dans l'ensemble, le segment qui joint ces deux points est entièrement inclus dans l'ensemble. L'enveloppe convexe d'un ensemble est le plus petit ensemble (pour l'inclusion) convexe qui contient les points. L'ensemble convexe d'un ensemble fini de points est un polygone. Le problème du calcul de l'enveloppe convexe est défini comme suit :
- entrée : un ensemble de n points du plan, chacun représenté par ses coordonnées (abscisse et ordonnée)
- sortie : une liste de points qui sont les sommets du polygone qui entoure l'enveloppe convexe, dans l'ordre d'apparition sur ce polygone.
Les sommets de l'enveloppe sont parmi les n points données en entrée. On suppose dans la suite que l'on souhaite que les sommets données en sortie sont dans le sens trigonométrique (anti-horaire, autrement dit dans le sens contraire des aiguilles d'une montre).
Algorithme
L'algorithme prend en entrée un tableau de n points, comme montré sur la figure suivante :
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. On échange le pivot avec le point numéro 1, de sorte que le pivot devienne maintenant le point numéro 1.
Tri des points
L'ensemble des points est ensuite trié en fonction de l'angle que chacun d'entre eux fait avec l'axe des abscisses relativement au pivot ; le pivot garde sa première position dans le tableau. 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)). À 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.
On remarque qu'il n'y a pas besoin de calculer effectivement l'angle réel entre l'axe des abscisses et une droite (1i) pour un point i = 2..n. On peut par exemple calculer la pente de la droite (1i), ou alors 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.
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.
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.
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]
Complexité algorithmique
La complexité en temps pour trouver 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 ». En effet, les boucles pour i = 3 à n et tant que sont imbriquées.
Mais, en fait la boucle est bien en O(n). En effet, chaque point est empilé au plus une fois. Ainsi, tous les calculs réalisés dans la boucle "tant que" est au plus en O(n).
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.
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
- « Code source pour créer les illustrations. »
- « Cours à l'université de Grenoble »
- (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.
- 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)
- (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)
- 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).
- 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)
- 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
- 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
- (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press et McGraw-Hill, , 2e éd. [détail de l’édition]. Pages 949–955 de la section 33.3: Finding the convex hull.
- (en) Implémentations du parcours de Graham en C++ et en Pascal Objet.
- [PDF] Présentation d'algorithmes pour calculer l'envelopper convexe d'un nuage de points