Algorithme de Graham

Parcours de Graham

Le parcours de Graham est un algorithme déterminant l'enveloppe convexe d'un ensemble de points. Son principal intérêt est sa complexité algorithmique en O(n log n). Cet algorithme doit son nom à Ronald Graham, qui a publié l'algorithme original en 1972[1].

Sommaire

Algorithme

Illustration

Graham scan.png

Comme on peut le voir, passer de A à B ou de B à C se fait dans le sens opposé aux aiguilles d'une montre, mais ce n'est pas le cas pour passer de C à D. L'algorithme détecte cette situation et rejette les segments précédemment choisis jusqu'à ce que le tournant pris soit dans le sens opposé aux aiguilles d'une montre (B à D dans ce cas).

La première étape de cet algorithme consiste à rechercher le point de plus petite ordonnée. S'il y a égalité entre un ou plusieurs points, l'algorithme choisit parmi eux le point de plus petite abscisse. Nommons P ce point. La complexité en temps de cette étape est en O(n), n étant le nombre de points de l'ensemble.

L'ensemble des points (P compris) est ensuite trié en fonction de l'angle que chacun d'entre eux et le point P font avec l'axe des abscisses. N'importe quel algorithme de tri convient pour cela, par exemple le tri par tas (qui a une complexité de O(n log n)). Dans le but d'accélérer les calculs, on peut se dispenser de calculer l'angle réel que ces points font avec l'axe des abscisses. Il suffit en effet de calculer la tangente de cet angle, ce qui est réalisable par arithmétique simple. À l'issue de cette étape, on dispose d'un tableau T contenant les points ainsi triés.

L'algorithme considère ensuite successivement les séquences de trois points contigus dans le tableau T, vus comme deux couples successifs. Pour chacun de ces paires de couples, il décide si passer du premier couple au second constitue un « tournant à gauche » ou un « tournant à droite ». Si c'est un « tournant à droite », cela signifie que l'avant dernier point considéré (le deuxième des trois) ne fait pas partie de l'enveloppe convexe, et qu'il doit être rejeté de T. Cette analyse se répète ensuite, tant que l'ensemble des trois derniers points est un « tournant à droite ». Dès que l'on rencontre un « tournant à gauche », l'algorithme passe au point suivant de T. (Si l'on rencontre trois points colinéaires, à 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).

Ici encore, 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 colinéaires. 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 T contiendra alors les points formant l'enveloppe convexe, dans l'ordre inverse des aiguilles d'une montre.

Complexité algorithmique

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(n²), 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 Points l'ensemble de points à examiner, sous la forme d'un tableau indexé à partir de un, et Pile une pile qui contiendra le résultat final.


Trouver le pivot P;
Trier les points par angle (les points d'angle égal seront triés par rapport à leur abscisse);
 
# Points[1] est le pivot, Points[longueur] aussi (fin du circuit)
Pile.empiler(Points[1]);
Pile.empiler(Points[2]);
POUR i = 3 A Points.longueur
        TANT QUE (Pile.hauteur >= 2) ET (Produit_vectoriel(Pile.second, Pile.haut, Points[i]) <= 0)
                Pile.dépiler;
        FIN TANT QUE
        Pile.empiler(Points[i]);
FIN POUR
 
FONCTION Produit_vectoriel(p1, p2, p3)
        RENVOYER(p2.x - p1.x)*(p3.y - p1.y) - (p3.x - p1.x)*(p2.y - p1.y);
FIN FONCTION


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 haut 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 :

Pile.hauteur >= 2 ? Produit_vectoriel(Pile.second, Pile.haut, Points[i]<= 0  : Pile.haut == Points[i].

Notes et références

  1. (en) Graham, R.L. (1972). An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Information Processing Letters 1, 132-133
  • (en) Cet article est partiellement ou en totalité issu d’une traduction de l’article de Wikipédia en anglais intitulé « Graham scan ».


Voir aussi

Liens et documents externes

  • Portail de la géométrie Portail de la géométrie
  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Parcours de Graham ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Graham de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Parcours de graham — Le parcours de Graham est un algorithme déterminant l enveloppe convexe d un ensemble de points. Son principal intérêt est sa complexité algorithmique en O(n log n). Cet algorithme doit son nom à Ronald Graham, qui a publié l algorithme original… …   Wikipédia en Français

  • Parcours de Graham — Le parcours de Graham est un algorithme déterminant l enveloppe convexe d un ensemble de points. Son principal intérêt est sa complexité algorithmique en O(n log n). Cet algorithme doit son nom à Ronald Graham, qui a publié l algorithme original… …   Wikipédia en Français

  • Algorithme Du Simplexe — L algorithme du simplexe de George Dantzig est une technique à la fois fondamentale et très populaire pour les problèmes de programmation linéaire. Ainsi, étant donné un ensemble d inégalités linéaires sur n variables réelles, l …   Wikipédia en Français

  • Algorithme du simplexe — L algorithme du simplexe de George Dantzig est une technique à la fois fondamentale et très populaire pour les problèmes d optimisation linéaire. Ainsi, étant donné un ensemble d inégalités linéaires sur n variables réelles, l algorithme permet… …   Wikipédia en Français

  • Algorithme diviser pour régner — Diviser pour régner (informatique) Pour les articles homonymes, voir Diviser pour régner. Diviser pour régner est une technique algorithmique consistant à diviser un problème de grande taille en plusieurs sous problèmes analogues. L étape de… …   Wikipédia en Français

  • Graham — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.  Pour l’article homophone, voir Grahame. Graham peut faire référence à : Sommaire …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Fouille de flots de données — Exploration de données Articles principaux Exploration de données Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes …   Wikipédia en Français

  • Théorème de Robertson-Seymour — En mathématiques, et plus précisément en théorie des graphes, le théorème de Robertson–Seymour (parfois également appelé le théorème des mineurs, et connu, avant qu il soit démontré, sous le nom de conjecture de Wagner), est un théorème démontré… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”