Grejamovo skeniranje

Grejamovo skeniranje je metod kojim se određuje konveksni omotač od zadatog skupa tačaka u ravni sa vremenskom složenošću O(n log n). Algoritam je dobio ime po Ronaldu Grejamu, koji ga je prvi put objavio 1972. godine.

Algoritam

Prvi korak ovog algoritma predstavlja nalaženje tačke sa najmanjom y-koordinatom. Ukoliko postoji više takvih tačaka onda se bira ona koja ima najmanju x-koordinatu. Neka je to tačka P. Vremenska složenost ovog koraka je O(n), gde je n broj tačaka.

Zatim je potrebno sortirati tačke u rastućem redosledu ugla kojim prava koja prolazi kroz datu tačku i tačku P zaklapa sa x-osom. Za ovo se može uzeti bilo koji algoritam za sortiranje, na primer quicksort (vremenska složenost iznosi O(n log n)). Kako bi ubrzali proces izračunavanja nije potrebno određivati pravu veličinu pomenutog ugla; dovoljno je naći njegov tangens.

Algoritam se nastavlja kroz dalje razmatranje tačaka u sortiranom nizu. Za svaku tačku je potrebno odrediti da li od dve prethodno razmatrane tačke prave levi ili desni zaokret. Ako je u pitanju desni zaokret, onda tačku, koja se nalazila dva mesta ispred poslednje u sortiranom nizu, treba izbaciti iz daljeg razmatranja, jer ona ne može biti deo konveksnog omotača. Proces se nastavlja sve dok poslednje tri tačke obrazuju desni zaokret. Čim se naiđe na levi zaokret, potrebno je prebaciti se na sledeću tačku u sortiranom nizu. (Ukoliko su u bilo kom koraku razmatrane tri tačke bile kolinearne, nevažno je da li će se srednja tačka izbaciti iz daljeg razmatranja.)

Za tri tačke (x₁, y₁), (x₂, y₂) i (x₃, y₃), dovljno je naći vektorski proizvod (x₂ - x₁) (y₃ - y₁) - (y₂ - y₁) (x₃ - x₁) dva vektora određenih tačkama (x₁,y₁), (x₂,y₁) i (x₂,y₁), (x₃,y₃). Ako je njegova vrednost 0, tačke su kolinearne, ako je pozitivna, tačke obrazuju „levi“, a u suprotnom „desni zaokret“.

Proces će se završiti upravo na onoj tački koja je prvo razmatrana, i tu se prekida izvršavanje algoritma, jer su u novom nizu sada sačuvane tačke koje pripadaju konveksnom omotaču, i to u smeru suprotnom od smera kretanja kazaljke na satu.

Vremenska složenost

Sortiranje tačaka zahteva složenost O(n log n). Iako se na prvi pogled čini da je složenost petlje O(n²), jer se za svaku tačku vraća unazad kako bi se proverilo da li ona sa nekim od prethodnih obrazuje desni zaokret, vremenska složenost je zapravo O(n), jer se svaka tačka razmatra samo jednom (ili se kod njom prekida izvršavanje unutrašnje petlje ili se izbacuje iz daljeg razmatranja). Prema tome, ukupna vremenska složenost iznosi O(n log n), što je zapravo vreme potrebno za sortiranje.

Pseudokod

Algoritam možemo prikazati na sledeći način:

Наћи тачку P;
Сортирати тачке по величини датог угла;
 
# Points[1] is the pivot
Stack.push(Points[1]);
Stack.push(Points[2]);
FOR i = 3 TO Points.length
        o <- Cross_product(Stack.second, Stack.top, Points[i]);
        IF o == 0 THEN
                Stack.pop;
                Stack.push(Points[i]);
        ELSEIF o > 0 THEN
                Stack.push(Points[i]);
        ELSE
                WHILE o <= 0 and Stack.length > 2
                        Stack.pop;
                        o <- Cross_product(Stack.second, Stack.top, Points[i]);
                ENDWHILE
                Stack.push(Points[i]);
        ENDIF
NEXT i
 
FUNCTION Cross_product(p1, p2, p3)
        RETURN (p2.x - p1.x)*(p3.y - p1.y) - (p3.x - p1.x)*(p2.y - p1.y);
ENDFUNCTION

Spoljašnje veze

• Implementacije algoritma u C++-u Object Pascal-u