Wypukła otoczka zbioru punktów Q to najmniejszy wypukły wielokąt taki, że każdy punkt ze zbioru Q leży albo na brzegu wielokąta albo w jego wnętrzu.
Oto przykład:
Jak widać otoczka składa się z 6 wierzchołków, jest to najmniejszy podzbiór zbioru Q taki że ich ciąg tworzy otoczkę zbioru Q.
Przeanalizujemy teraz algorytm Grahama, zakładamy przy tym, że zbiór Q jest uporządkowany w następujący sposób:

1. wierzchołek o najmniejszym indeksie (u nas a) ma najmniejszą wartość y (jeśli jest kilka wierzchołków o najmniejszej wartości y, wybieramy skrajnie lewy)
2. kolejne wierzchołki (u nas b do j) są posortowane ze względu na kąt nachylenia ich wektorów wodzących do osi X

Takie uporządkowanie możemy otrzymać za pomocą algorytmu porządkowania wierzchołków.
Na poniższym rysunku widać proste zawierające wektory wodzące punktów, z kątów których wynika przyjęty porządek:
Punkt a ze względu na swe położenie jest oczywiście pierwszym wierzchołkiem otoczki. Algorytm Grahama polega na przechodzeniu do kolejnych wierzchołków z posortowanej listy, umieszczaniu ich na stosie i sprawdzaniu kierunku, w którym nastąpiło to przejście:

1. jeżeli odchylenie nastąpiło w prawą stronę, zdejmowany jest wierzchołek ze stosu
2. jeżeli odchylenie nastąpiło w stronę lewą, wierzchołek pozostaje na stosie

Oto algorytm zapisany w pseudokodzie:
Niech S₁ oznacza element na szczycie stosu a S₂ element pod nim
m- liczba punktów
p_i (i=0...m) oznacza i-ty punkt z uporządkowanej listy (w analogii do rysunku: p₀=a, p₁=b itd...) K oznacza kąt między punktami S₂, S₁ oraz p_i

1. Umieść na stosie punkty p₀, p₁ i p₂
2. for i=3 to m do {
3.   while K oznacza skręt w prawo
4.       do Usuń punkt ze stosu
5.   Dodaj na stos punkt p_i
6. }

Jak widać kluczową czynnością w algorytmie jest określanie kierunku, w którym przechodzimy do następnego punktu. Można do tego celu wykorzystać metodę wyznaczników (opisaną w algorytmie współliniowości trzech punktów). Będziemy brać pod uwagę dwa wektory zaczepione we wspólnym punkcie.

Np. zał. że na szczycie stosu mamy punkt b a tuż pod nim punkt a. Kolejnym punktem do przeanalizowania jest punkt c, chcemy sprawdzić, czy przechodząc do tego punktu (z punktu b) skręcimy w lewo, czy w prawo. Tworzymy więc dwa wektory AB oraz AC (zob. rysunek). Następnie za pomocą wyznaczników sprawdzamy po której stronie wektora AB leży punkt c. W przykładzie z rysunku wyznacznik det(a,b,c)>0 (gdyż punkt c leży po lewej stronie wektora). A zatem przechodząc z punktu b do punktu c skręcimy w lewo.




Przeanalizujemy teraz kilka kroków algorytmu, dany jest uporządkowany ciąg punktów:
Wykonujemy pierwszy punkt algorytmy S={a, b, c} (zawartość stosu na rysunku jest oznaczona jako ciąg wierzchołków wyznaczający łamaną) i inicjujemy zmienną i=3 (m=9): sprawdzamy, po której stronie wektora BC znajduje się punkt wskazany przez zmienną i=3 (pamiętajmy, że liczymy od 0) a więc det(b,c,d). Z rysunku widać, że punkt ten leży po prawej stronie, więc obliczony wyznacznik będzie miał wartość ujemną. A zatem przechodząc przez ten punkt skręcimy w prawo. zgodnie z punktem 4. algorytmu usuwamy jeden punkt ze stosu: S={a,b}
Sprawdzamy więc, po której stronie wektora AB (gdyż C usunęliśmy) leży punkt d (zmienna i nadal ma wartość 3). Obliczymy, że det(a,b,d)>0, a więc skręcamy w lewo zatem dodajemy punkt d na stos i inkrementujemy zmienną (i++).
Zmienna i wskazuje na punkt e, na szczycie stosu mamy punkty d i b, zatem obliczamy det(b,d,e), otrzymujemy wartość ujemną, co oznacza skręt w prawo. Zdejmujemy więc wierzchołek ze stosu, czyli S={a, b}: badamy det(a,b,e) i otrzymujemy wartość dodatnią, dodajemy wierzchołek e na stos (S={a,b,e}) i inkrementujemy zmienną i. Postępując tak aż do momentu, gdy m osiągnie wartość 9 otrzymamy na stosie ciąg wierzchołków tworzących wypukłą otoczkę. Dla pełnej jasności przedstawię jeszcze na rysunku przebieg kolejnych kroków:

Komentarze