Marche de Jarvis

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Construction itérative de l'enveloppe convexe d'un nuage de points, par marche de Jarvis.

En géométrie algorithmique, la marche de Jarvis[1] est un algorithme pour calculer l'enveloppe convexe d'un ensemble fini de points. L'idée de l'algorithme est d' « envelopper » l'ensemble de points dans un « papier cadeau » : on accroche ce papier à l'un des points, on le tend, puis on tourne autour du nuage de point.

Principe[modifier | modifier le code]

Diagramme de l'algorithme

Soit le point initial où l'on accroche le papier.

Le premier point rencontré par le papier sera , puis ... jusqu'à retrouver .

Plus formellement, il s'agit pour chaque nouveau sommet de l'enveloppe convexe trouvé, de chercher le suivant en calculant le point d'angle polaire minimal par rapport à .

En pratique, on divise le parcours en deux : à partir du point d'abscisse minimale, puis à partir du point d'abscisse maximale.

L'algorithme[modifier | modifier le code]

 fonction marcheJarvis(E)
     p ː= un point d'abscisse minimale dans E
     L ː= liste vide
     répéter
           insérer p dans L
           p ː= point p' de E tel que [pp') est le plus incliné vers la gauche (1)
     jusqu’à p = p0
    retourner L

La ligne (1) s'effectue de la manière suivante ː

    p ː= p 
    pour tout p' de E
          Si p = p ou p' est à gauche de [pp) alors
                 p = p'
    p ː= p

Le corps de la boucle répéter - jusqu'à est exécuté autant de fois qu'il y a de points dans l'enveloppe convexe. La ligne (1) est en . D'où une complexité en , où représente le nombre de sommets de l'enveloppe convexe.

Lien externe[modifier | modifier le code]

(fr) [1], Cours de l'université de Montpellier 2

Notes et références[modifier | modifier le code]

  1. R. A. Jarvis, « On the identification of the convex hull of a finite set of points in the plane », Information Processing Letters, vol. 2,‎ , p. 18–21 (DOI 10.1016/0020-0190(73)90020-3, lire en ligne)

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]