Jarvis Walk

Ve výpočetní geometrie je Jarvis chůze je algoritmus pro výpočet konvexní trup z konečné množiny bodů. Myšlenka algoritmu je „ zabalit “ sadu bodů do „ balicího papíru “: tento papír zavěsíme k jednomu z bodů, roztáhneme ho a pak se otočíme kolem mračna bodů.

Zásada

Nechť je počátečním bodem, kde je papír zavěšen. $p_ {0}$

První bod, se kterým se papír setká, bude , pak ... dokud nebude nalezen . $p_1$ $p_2$ $p_ {0}$

Formálněji pro každý nový vrchol nalezené konvexní obálky jde o nalezení dalšího výpočtem bodu minimálního polárního úhlu vzhledem k . $p_ {i}$ $p_ {i}$

V praxi rozdělíme trasu na dvě: od bodu minimální úsečky, potom od bodu maximální úsečky.

Algoritmus

fonction marcheJarvis(E) p := un point d'abscisse 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

Řádek (1) se provádí takto:

pour tout p' de E Si p'' = p' ou p' est à gauche de [pp') alors p'' = p' p := p

Tělo smyčky se opakuje - dokud se neprovádí tolikrát, kolik bodů je v konvexní obálce. Řádek (1) je v . Od této doby složitost v , kde představuje počet vrcholů na konvexní obálky. $My)$ ${\ displaystyle O (nh)}$ $h$

Externí odkaz

(fr) [1] , Kurz University of Montpellier 2

Poznámky a odkazy

RA Jarvis , „ O identifikaci konvexního trupu konečné sady bodů v rovině, “ Information Processing Letters , sv. 2,1 st 03. 1973, str. 18–21 ( DOI 10.1016 / 0020-0190 (73) 90020-3 , číst online , přistupováno 25. března 2016 )

Podívejte se také

Související články