marche de Jarvis

Imaginez cinq punaises sur une planche et un élastique qui doit les entourer. Depuis une punaise située au bord, faites pivoter une règle jusqu'à rencontrer la prochaine punaise extérieure. Recommencez à partir de celle-ci.

La marche de Jarvis reproduit ce geste : elle avance de sommet en sommet autour des points, comme un papier cadeau que l'on enroule. Les points intérieurs ne sont jamais retenus. Lorsque le parcours revient au point de départ, le contour obtenu est l'enveloppe convexe.

La marche de Jarvis est un algorithme incrémental appliqué à un ensemble fini de points du plan. Elle construit l'enveloppe convexe, c'est-à-dire le plus petit ensemble convexe qui contient tous les points. On part d'un point extrême, souvent le point le plus à gauche, puis on choisit successivement le prochain sommet du contour jusqu'au retour au point initial.

Pour formaliser le pivot, soit P le sommet courant, Q un candidat et R tout autre point. Le déterminant orienté $\det (Q-P,R-P)\backslash operatorname\{det\}(Q-P,R-P)$ indique de quel côté de la droite orientée de P vers Q se trouve R. Pour un parcours dans le sens trigonométrique, on retient un point Q tel que ce déterminant soit positif ou nul pour tout point R : tous les points sont alors à gauche de la droite orientée ou alignés. Si plusieurs candidats sont alignés dans la direction retenue, le plus éloigné de P évite de s'arrêter sur un point intérieur du segment.

Si n désigne le nombre total de points et h le nombre de sommets de l'enveloppe, chaque nouveau sommet demande un balayage des n points. Le coût est donc en O(nh). Il est avantageux lorsque h est petit devant n, mais perd cet avantage lorsque presque tous les points appartiennent au contour. L'algorithme, proposé par R. A. Jarvis en 1973, est aussi nommé emballage cadeau ou gift wrapping.

Considérons cinq points : A(0 ; 0), B(2 ; 0), C(2 ; 2), D(0 ; 2) et I(1 ; 1). Le départ choisi est A, le plus bas des deux points les plus à gauche. Nous parcourons le contour dans le sens trigonométrique.

1. Depuis A, le pivot retient B. Par exemple, le point intérieur I reste du bon côté car $\det (B-A,I-A)=\det ((2,0),(1,1))=2\backslash operatorname\{det\}(B-A,I-A)=\backslash operatorname\{det\}((2,0),(1,1))=2$.

2. Depuis B, le même test retient C ; depuis C, il retient D. À chaque fois, un balayage des cinq points confirme qu'aucun point ne se trouve à l'extérieur du côté orienté choisi.

3. Depuis D, le prochain sommet est A. Le retour au départ arrête l'algorithme. L'ordre des sommets est donc A, B, C, D, puis A ; le point I n'appartient pas au contour.

4. Le contrôle est visuel et calculable : chacun des cinq points est dans le carré délimité par 0 ≤ x ≤ 2 et 0 ≤ y ≤ 2, tandis que ses quatre coins sont présents. Le carré ABCD est bien le plus petit ensemble convexe contenant les cinq points.

Pour construire le contour d'un petit nuage de points, choisissez un point extrême et balayez tous les candidats à chaque pivot. La marche de Jarvis est particulièrement lisible lorsque peu de points se trouvent sur l'enveloppe.

Pour coder le choix du prochain sommet dans le sens trigonométrique, utilisez le signe d'un déterminant orienté plutôt qu'un angle calculé numériquement : retenez Q lorsque $\det (Q-P,R-P)\ge 0\backslash operatorname\{det\}(Q-P,R-P)\backslash geq\; 0$ pour tout autre point R. En cas d'alignement, comparez les distances au sommet courant et conservez le point le plus éloigné.

Pour anticiper le temps de calcul, observez la taille du contour. Si h reste petit devant le nombre n de points, les h balayages complets conviennent bien. Si h est proche de n, le coût en O(nh) se rapproche d'un coût quadratique et une autre méthode de calcul d'enveloppe convexe devient préférable.

Marche de Jarvis et enveloppe convexe. La marche de Jarvis est la procédure ; l'enveloppe convexe est le résultat géométrique recherché. Sur les cinq points A, B, C, D et I, l'algorithme effectue des pivots, tandis que le carré ABCD est l'enveloppe obtenue.

Point extrême et point le plus à gauche. Le point le plus à gauche est un choix commode de départ, mais l'algorithme peut partir d'un autre point extrême. Dans l'exemple, A et D ont la même abscisse minimale ; choisir A comme le plus bas règle seulement cette égalité.

Beaucoup de sommets sur le bord. Lorsque h est proche de n, le coût O(nh) devient proche de O(n²). Le symptôme est un contour qui retient presque tous les points ; il faut alors préférer une autre méthode de calcul d'enveloppe convexe si le volume de données rend les balayages trop coûteux.

Points alignés pendant un pivot. Le seul test du côté ne départage pas plusieurs points placés sur la même demi-droite. S'arrêter au plus proche ajouterait un faux sommet intermédiaire ; il faut retenir le plus éloigné du sommet courant.

Égalité au départ. Plusieurs points peuvent partager l'abscisse minimale, comme A et D dans l'exemple. Sans règle de départ, l'implémentation est ambiguë ; choisir systématiquement le plus bas ou le plus haut fixe le premier sommet, puis l'orientation choisie fixe le sens du parcours.

Ensemble entièrement aligné. L'élastique intuitif ne forme alors pas un polygone d'aire positive. Avec la convention qui écarte les points intermédiaires alignés, l'enveloppe se réduit au segment joignant les deux points extrêmes ; le critère de distance devient indispensable.

Enveloppe convexe — Approfondir l'objet géométrique que la marche de Jarvis construit sommet après sommet.