Jarvisův algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 19. ledna 2015; kontroly vyžadují 9 úprav .

Jarvisův algoritmus (nebo Jarvisův traversální algoritmus nebo algoritmus balení dárků) určuje sekvenci prvků sady , které tvoří konvexní obal této sady. Metodu si lze představit jako omotání sady hřebíků zaražených do prkna lanem. Algoritmus běží v čase , kde je celkový počet bodů na rovině, je počet bodů v konvexním trupu. $O(nh)$ $n$ $h$

Popis algoritmu

Nechť je dána sada bodů . Spodní bod zcela vlevo je brán jako počáteční bod (lze jej nalézt za obvyklým průchodem všemi body), je to přesně vršek konvexního trupu. Další bod ( ) je bod, který má nejmenší kladný polární úhel vzhledem k bodu jako počátku. Poté se pro každý bod (2<i<=|P|) proti směru hodinových ručiček hledá takový bod tak , že se mezi zbývajícími body najde dále (+ vlevo dole), ve kterém bude největší úhel mezi úsečkami a tvořil . Bude to další vrchol konvexního trupu. V tomto případě se nehledá úhel samotný, ale hledá se pouze jeho kosinus přes skalární součin mezi paprsky a , kde je poslední nalezené minimum, je předchozí minimum a je kandidátem na další minimum. Nové minimum bude bod, ve kterém bude kosinus nabývat nejmenší hodnoty (čím menší je kosinus, tím větší je jeho úhel). Hledání vrcholů konvexního trupu pokračuje až do . V tom okamžiku, kdy se další bod v konvexním trupu shoduje s prvním, algoritmus se zastaví – konvexní trup je postaven. $P=\{\,p_{1},p_{2},\ldots ,p_{n}\,\}$ $p_{1}$ $Na)$ $p_{2}$ $p_{1}$ $p_{i}$ $p_{{i+1}}$ $Na)$ $p_{{i-1}}p_{{i}}$ $p_{{i}}p_{{i+1}}$ $p_{{i-1}}p_{{i}}$ $p_{{i}}p'_{{i+1}}$ $p_{{i}}$ $p_{{i-1}}$ $p'_{{i+1}}$ $p_{{i+1}}\neq p_{1}$

Pseudokód

Jarvis (P) 1) p[1] = krajní levý spodní bod množiny P; 2) p[2] = sousední bod od p[1] doprava (umístěný v minimálním kladném polárním úhlu) 3) i = 2; 4) udělat : a) pro každý bod j od 1 do |P|, kromě těch, které jsou již v konvexním trupu, ale včetně p[1] p[i+1] = bod_s_min_cos(p[i-1], p[i], P[j]); //bod tvořící minimální kosinus s přímkou p[i-1]p[i], (b)i = i + 1; zatímco p[i] != p[1] 5) vrátit p;

Analýza

Smyčka (4) se provede jednou, zatímco smyčka (a) se provede pokaždé pro . Všechny ostatní operace se provádějí v . Algoritmus tedy funguje pro nebo v nejhorším případě, kdy všechny body spadají do konvexního trupu. $h$ $\Opalování)$ $O(1)$ $\Theta (hn)$ $\Theta (n^{2})$

Viz také

Grahamův algoritmus
Chanův algoritmus

Literatura

Preparata F., Shaimos M. Computational Geometry Úvod. — M .: Mir, 1989. — 478 s.
Laszlo M. Výpočetní geometrie a počítačová grafika v C++. - M. : BINOM, 1997. - 304 s.
T. Kormen, C. Leizerson, R. Rivest, K. Stein. Algoritmy. Konstrukce a analýza = Úvod do algoritmů. - 2. vyd. - "Williams", 2005. - 1296 s.

Odkazy

c++ implementace