Marche de Jarvis
Ce calculateur en ligne calcule l'enveloppe convexe d'un ensemble de points données en utilisant l'algorithme de la marche de Jarvis, connu comme l'algorithme d'enveloppement dans un papier cadeau.
Ce calculateur implémente l'algorithme de la Marche de Jarvis, introduit par R. A. Jarvis en 1973 (également connu comme l'algorithme d'enveloppement dans un papier cadeau) pour calculer l'enveloppe convexe d'un ensemble de points en 2d. Il a la complexité de , où n est le nombre de points, et h est le nombre de sommets de l'enveloppe, donc, c'est un algorithme au résultat sensible. Il y a d'autres algorithmes avec des complexités de
et
, mais la Marche de Jarvis est très simple à implémenter.
L'algorithme commence avec un point connu étant sur l'enveloppe convexe, par exemple le point le plus à gauche, et sélectionne le point suivant en comparant les angles polaires de tous les points par rapport au point précédent considéré comme le centre des coordonnées polaires. Le point avec l'angle minimum gagne. Le processus continue jusqu'à ce qu'il retourne au point de départ en h étapes. Le processus est similaire à l'enroulement d'un fil (ou à l'enveloppement dans un papier) autour de l'ensemble de points, d'où le nom algorithme d'enveloppement dans un papier cadeau.
Saisissez l'ensemble des points dans le calculateur ci-dessous - un point par ligne, avec les coordonnées x et y séparées par un point-virgule. Le calculateur construit une enveloppe convexe, l'affiche comme un ensemble de points et la trace.
commentaires