Грејамово скенирање

Грејамово скенирање је метод којим се одређује конвексни омотач од задатог скупа тачака у равни са временском сложеношћу O(n log n). Алгоритам је добио име по Роналду Грејаму, који га је први пут објавио 1972. године.

Алгоритам

Први корак овог алгоритма представља налажење тачке са најмањом y-координатом. Уколико постоји више таквих тачака онда се бира она која има најмању x-координату. Нека је то тачка P. Временска сложеност овог корака је O(n), где је n број тачака.

Затим је потребно сортирати тачке у растућем редоследу угла којим права која пролази кроз дату тачку и тачку P заклапа са x-осом. За ово се може узети било који алгоритам за сортирање, на пример quicksort (временска сложеност износи O(n log n)). Како би убрзали процес израчунавања није потребно одређивати праву величину поменутог угла; довољно је наћи његов тангенс.

Алгоритам се наставља кроз даље разматрање тачака у сортираном низу. За сваку тачку је потребно одредити да ли од две претходно разматране тачке праве леви или десни заокрет. Ако је у питању десни заокрет, онда тачку, која се налазила два места испред последње у сортираном низу, треба избацити из даљег разматрања, јер она не може бити део конвексног омотача. Процес се наставља све док последње три тачке образују десни заокрет. Чим се наиђе на леви заокрет, потребно је пребацити се на следећу тачку у сортираном низу. (Уколико су у било ком кораку разматране три тачке биле колинеарне, неважно је да ли ће се средња тачка избацити из даљег разматрања.)

За три тачке (x₁, y₁), (x₂, y₂) и (x₃, y₃), довљно је наћи векторски производ (x₂ - x₁) (y₃ - y₁) - (y₂ - y₁) (x₃ - x₁) два вектора одређених тачкама (x₁,y₁), (x₂,y₁) и (x₂,y₁), (x₃,y₃). Ако је његова вредност 0, тачке су колинеарне, ако је позитивна, тачке образују „леви“, а у супротном „десни заокрет“.

Процес ће се завршити управо на оној тачки која је прво разматрана, и ту се прекида извршавање алгоритма, јер су у новом низу сада сачуване тачке које припадају конвексном омотачу, и то у смеру супротном од смера кретања казаљке на сату.

Временска сложеност

Сортирање тачака захтева сложеност O(n log n). Иако се на први поглед чини да је сложеност петље O(n²), јер се за сваку тачку враћа уназад како би се проверило да ли она са неким од претходних образује десни заокрет, временска сложеност је заправо O(n), јер се свака тачка разматра само једном (или се код њом прекида извршавање унутрашње петље или се избацује из даљег разматрања). Према томе, укупна временска сложеност износи O(n log n), што је заправо време потребно за сортирање.

Псеудокод

Алгоритам можемо приказати на следећи начин:

Наћи тачку 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

Спољашње везе

• Имплементације алгоритма у C++-у Object Pascal-у