Marche de Jarvis

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La marche de Jarvis est un algorithme qui « enveloppe » un ensemble de points dans un « papier cadeau » : on accroche ce papier à un point initial p_0, puis on le tend, et on tourne autour du nuage de point.

Diagramme de l'algorithme

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

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

En pratique, on divise le parcours en deux : à partir du point d'ordonnée minimal, puis à partir du point d'ordonnée maximal.

La complexité est en O(nh), où h représente le nombre de sommets de l'enveloppe convexe.


L'algorithme[modifier | modifier le code]

Données : Points = un ensemble fini de points du plan.

Sorties : Enveloppe = la liste des sommets de l'enveloppe convexe.

1 début

2 pmin ← le sommet le plus bas

3 pcourant ← pmin

4 Insérer(pcourant,L)

5 répéter

6 Choisir p ≠ pcourant

7 Prendre psuivant le point le plus à droite de [pcourant, p)

8 pcourant ← psuivant

9 Insérer(pcourant,L)

10 jusqu’à pcourant = pmin

11 retourner L

12 fin

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