Marche de Jarvis
- Marche de Jarvis
-
La marche de Jarvis est un algorithme qui « enveloppe » un ensemble de points dans un « papier cadeau » : on accroche ce papier à un point initial p0, puis on le tend, et on tourne autour du nuage de point.
Diagramme de l'algorithme
Le premier point rencontré par le papier sera p1, puis p2... jusqu'à retrouver p0.
Plus formellement, il s'agit pour chaque nouveau sommet pi de l'enveloppe convexe trouvé, de chercher le suivant en calculant le point d'angle polaire minimal par rapport à pi.
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.
|
|
| Interactions géométrie-analyse |
|
| Analyse convexe |
|
| Utilisations de la convexité |
|
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Marche de Jarvis de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Marche De Jarvis — La marche de Jarvis est un algorithme qui « enveloppe » un ensemble de points dans un « papier cadeau » : on accroche ce papier à un point initial p0, puis on le tend, et on tourne autour du nuage de point. Diagramme de l … Wikipédia en Français
Marche de jarvis — La marche de Jarvis est un algorithme qui « enveloppe » un ensemble de points dans un « papier cadeau » : on accroche ce papier à un point initial p0, puis on le tend, et on tourne autour du nuage de point. Diagramme de l … Wikipédia en Français
Jarvis — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Jarvis peut désigner : Patronyme Jarvis est un nom de famille notamment porté par : Aaron Jarvis (né en 1986), joueur anglais de rugby à… … Wikipédia en Français
Eugene Jarvis — EugeneJarvis Eugene Jarvis en 2006. Naissance 1955 Palo Alto, Californie … Wikipédia en Français
Rebecca Jarvis — (14 décembre 1981 à Minneapolis dans l état du Minnesota aux États Unis ) est une journaliste spécialisée dans la finance, et finaliste de la saison 4 de la série télévisée américaineThe Apprentice. Elle a été diplômée de l université de Chicago… … Wikipédia en Français
Enveloppe Convexe — Analogie avec un élastique entourant des points dans le plan, l enveloppe convexe est la région délimitée par la ligne bleue. L enveloppe convexe d un objet ou d un regroupement d objets géométriques est l ensemble convexe le plus petit parmi… … Wikipédia en Français
Enveloppe convexe — Analogie avec un élastique entourant des points dans le plan, l enveloppe convexe est la région délimitée par la ligne bleue. L enveloppe convexe d un objet ou d un regroupement d objets géométriques est l ensemble convexe le plus petit parmi… … Wikipédia en Français
Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants … Wikipédia en Français
Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… … Wikipédia en Français
Adherence, interieur et frontiere d'un convexe — Adhérence, intérieur et frontière d un convexe Dans le cas particulier de parties convexes d un espace vectoriel topologique, les opérateurs topologiques élémentaires d adhérence ou intérieur préservent la convexité. Sous une réserve technique… … Wikipédia en Français
