« poprzedni punkt   następny punkt »


5. Algorytm Jarvisa

Metoda użyta w algorytmie Jarwisa jest zupełnie inna niż metoda Grahama. Wyobraźmy sobie kartkę papieru, której róg przykładamy najpierw w najniżej położonym punkcie zbioru Q, a następnie obracamy względem tego punktu, w kierunku przeciwnym do  ruchu wskazówek zegara tak długo,  aż brzeg kartki napotka jakimś inny punkt zbioru Q. Ten właśnie punkt przyjmujemy za następny wierzchołek szukanej otoczki. Teraz przykładamy kartkę w nowym punkcie i znów obracamy  ją względem tego punktu, tak długo aż spotkamy następny punkt zbioru itd. Takie postępowanie  przypomina owijanie  zbioru punktów paskiem papieru lub sznurkiem i stąd jego angielska nazwa package wrapping.

Zauważmy jeszcze, że jeśli początek układu współrzędnych umieścimy w punkcie p, wybranym zgodnie z opisaną zasadą, to następny "wykryty" metodą obracania kartki papieru, punkt, to ten punkt q zbioru Q, dla którego kąt jaki tworzy wektor pq z dodatnim kierunkiem osi X  jest najmniejszy, tzn. dla którego kąt biegunowy ze względu na p jest najmniejszy licząc od dodatniej półosi OX.   Jeśli jednak osiągniemy punkt położony najwyżej w zbiorze Q, to następny wybrany punkt to ten o najmniejszej współrzędnej kątowej w biegunowym układzie współrzędnych,  licząc od ujemnej półosi OX.

Na rysunku 13.10  zaznaczono wybrane punkty i kąty, które badamy. Punkt p[1] jest następnym wybranym po punkcie p[0], bo kąt jaki tworzy dodatni kierunek osi OX z wektorem p[0]p[1] jest najmniejszy  (kartkę obracamy w lewo). Podobnie dla punktów p[2] i p[m]. Punkt p[m] jest najwyżej położonym punktem. Umieśćmy początek układu w tym punkcie i przyłóżmy kartkę w punkcie q[0]=p[m], tak, by jej brzeg pokrywał się z ujemnym kierunkiem osi OX. Obracamy kartkę w dół w prawo. Znaleziony punkt q[1] tworzy najmniejszy kąt biegunowy z ujemną półosią OX.


W algorytmie Jarvisa, podobnie jak w algorytmie Grahama, nie musimy liczyć kątów. Wystarczy umieć je porównywać.  Zgodnie z tym co było powiedziane w punkcie drugim tego wykładu, wymaga to obliczenia iloczynu wektorowego, a dokładniej zbadania znaku pewnego wyznacznika.

Szkic algorytmu Jarvisa

Krok 1. Znaleźć punkty p[0], q[0] : p[0] o najmniejszej, a q[0] o największej współrzędnej y:
p[0].y = min {p.y : p Î Q};  q[0].y = max{p.y : p Î Q}.

Krok 2. Konstruujemy dwa ciągi 
         - lewy ciąg : p[0],..., p[m] i
         - prawy ciąg :q[0],... ,q[l],
takie że p[m] =q[0], q[l] = p[0] oraz
p[i+1] jest tym punktem zbioru Q, który ma najmniejszy kąt biegunowy ze względu na p[i], licząc od dodatniej półosi OX w lewo,
q[i+1] jest tym punktem zbioru Q, który ma najmniejszy kąt biegunowy ze względu na p[i], licząc od ujemnej półosi OX w prawo.

Zbiór punktów p[0],...,p[m], q[1],...., q[l-1] jest ciągiem wierzchołków otoczki wypukłej w porządku  ich występowania na obwodzie wielokąta, w kierunku przeciwnym do ruchu wskazówek zegara.

Koszt algorytmu Jarvisa

Niech k będzie liczbą wierzchołków szukanej otoczki wypukłej  zbioru n punktów Q. Każdy krok pętli znajdującej kolejne punkty ciągu lewego i prawego kosztuje O(n) (szukamy minimum kąta biegunowego w n elementowym zbiorze).  Zatem ostatecznie koszt ocenimy na O(nk). 


Lemat 5.1 Algorytm Jarvisa poprawnie rozwiązuje problem znajdowania otoczki wypukłej danego skończonego zbioru punktów na płaszczyźnie.

Przykład 5.1
Rozważmy zbiór punktów przedstawiony na rysunku 13.11(a). W tabeli obok zaznaczono kolorem czerwonym punkty wybrane w kolejnych krokach algorytmu (dla których kąt biegunowy był aktualnie najmniejszy). Punktem początkowym jest B, gdyż  jego współrzędna y ma najmniejszą wartość. Wybrane punkty są wstawiane na kolejne początkowe pozycje tablicy punktów podobnie, jak to się dzieje w algorytmie SelectionSort. Jeśli znaleziony punkt jest identyczny z punktem początkowym, to proces tworzenia otoczki jest zakończony.
A
 B
 C D
 E
 F
 G
 H
 I
 J
 K
B
 A
 C
 D
 E
 F
 G
 H
 I
 J
 K
 B
B
 K
 C
 D
 E
 F
 G
 H
 I
 J
 A
 B
B
 K
 J
 D
 E
 F
 G
 H
 I
 C
 A
 B
B
 K
 J
 F
 E
 D
 G
 H
 I
 C
 A
 B
B
 K
 J
 F
 A
 D
 G
 H
 I
 C
 E
 B















Rysunek 13.11(b)


Uwaga Eddy i Floyd zaproponowali, by proces konstrukcji otoczki wypukłej (dowolnym algorytmem) zawsze rozpoczynać od usunięcia wszystkich punktów leżących wewnątrz czworokąta  zbudowanego z punktów ekstremalnych: p1- o najmniejszej współrzędnej x, p2 - o najmniejszej współrzędnej y, p3 - o największej współrzędnej x i p4 - o największej współrzędnej y. Jest dość duża szansa, że w tym pierwszym kroku usuniemy z dalszych rozważań znaczną liczbę niepotrzebnych punktów.

Pytanie 5:  Jaki jest w najgorszym przypadku koszt algorytmu Jarvisa zastosowanego do zbioru n punktów ? 

« poprzedni punkt   następny punkt »