Algoritmul Jarvis

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 19 ianuarie 2015; verificările necesită 9 modificări .

Algoritmul Jarvis (sau algoritmul de traversare Jarvis, sau algoritmul de împachetare cadou) determină o secvență de elemente ale mulțimii care formează o carcasă convexă pentru acest set. Metoda poate fi imaginată ca înfășurarea unui set de cuie înfipte într-o scândură cu o frânghie. Algoritmul rulează în timp , unde este numărul total de puncte de pe plan, este numărul de puncte din carcasa convexă. $O(nh)$ $n$ $h$

Descrierea algoritmului

Să fie dat un set de puncte . Punctul de jos din stânga este luat ca punct inițial (poate fi găsit în spatele trecerii obișnuite prin toate punctele), este exact partea de sus a carcasei convexe. Următorul punct ( ) este punctul care are cel mai mic unghi polar pozitiv în raport cu punctul ca origine. După aceea, pentru fiecare punct (2<i<=|P|) în sens invers acelor de ceasornic, se caută un astfel de punct găsind dincolo printre punctele rămase (+ cel mai jos din stânga), în care unghiul cel mai mare dintre linii și va fi format . Va fi următorul vârf al carcasei convexe. În acest caz, unghiul în sine nu este căutat, ci numai cosinusul său este căutat prin produsul scalar dintre raze și , unde este ultimul minim găsit, este minimul anterior și este candidatul pentru următorul minim. Noul minim va fi punctul în care cosinusul va lua cea mai mică valoare (cu cât cosinusul este mai mic, cu atât unghiul său este mai mare). Găsirea vârfurilor învelișului convex continuă până la . În acel moment, când următorul punct din carcasa convexă coincide cu primul, algoritmul se oprește - se construiește carcasa convexă. $P=\{\,p_{1},p_{2},\ldots,p_{n}\,\}$ $p_{1}$ $Pe)$ $p_{2}$ $p_{1}$ $p_{i}$ $p_{{i+1}}$ $Pe)$ $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}$

Pseudocod

Jarvis (P) 1) p[1] = punctul cel mai din stânga inferior al mulțimii P; 2) p[2] = punctul vecin de la p[1] la dreapta (situat prin unghiul polar pozitiv minim) 3) i = 2; 4) face : (a) pentru fiecare punct j de la 1 la |P|, cu excepția celor deja în carcasa convexă, dar incluzând p[1] p[i+1] = punct_cu_min_cos(p[i-1], p[i], P[j]); //punct care formează cosinusul minim cu linia p[i-1]p[i], (b)i = i + 1; în timp ce p[i] != p[1] 5) întoarcere p;

Analiză

Bucla (4) va fi executată o dată, în timp ce bucla (a) este executată de fiecare dată pentru . Toate celelalte operațiuni sunt efectuate în . Prin urmare, algoritmul funcționează pentru sau în cel mai rău caz, atunci când toate punctele cad în carcasa convexă. $h$ $\Theta(n)$ $O(1)$ $\Theta (hn)$ $\Theta (n^{2})$

Vezi și

algoritmul lui Graham
algoritmul lui Chan

Literatură

Preparata F., Shaimos M. Computational Geometry O introducere. — M .: Mir, 1989. — 478 p.
Laszlo M. Geometrie computațională și grafică pe computer în C++. - M. : BIOM, 1997. - 304 p.
T. Kormen, C. Leizerson, R. Rivest, K. Stein. Algoritmi. Construcție și analiză = Introducere în algoritmi. - Ed. a II-a. - „Williams”, 2005. - 1296 p.

Link -uri

implementare c++