Marche de Jarvis

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant les mathématiques
Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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'ordonnée minimal, puis à partir du point d'ordonnée maximal.

L'algorithme[modifier | modifier le code]

 fonction marcheJarvis(E)
     p ː= un point d'ordonnée 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]