Algorytm Jarvisa

Algorytm Jarvisa, marsz Jarvisa lub owijanie prezentów (ang. gift wrapping algorithm) – metoda wyznaczania otoczki wypukłej zbioru punktów umieszczonych na płaszczyźnie lub przestrzeni o większej liczbie wymiarów.

Algorytm został niezależnie opracowany przez Donalda Chanda oraz Shama Kapura (1970) oraz R. Jarvisa (1973, przypadek na płaszczyźnie).

Algorytm na płaszczyźnie

Algorytm działa w czasie $O(kn),$ gdzie $n$ to całkowita liczba punktów, natomiast $k$ to liczba punktów należących do otoczki. Zwykle w praktyce $k\ll n,$ jednak w pesymistycznym przypadku złożoność czasowa może wynieść $O(n^{2}).$

Wariant 1

Przebieg algorytmu Jarvisa dla przykładowych danych

Algorytm przebiega następująco:

• $P_{1}$ – punkt na otoczce wypukłej o najmniejszej współrzędnej y (jeśli jest więcej niż jeden, wybierany jest ten o najmniejszej współrzędnej x),
• $Q_{1}$ – punkt na otoczce wypukłej o największej współrzędnej y (jeśli jest więcej niż jeden, wybierany jest ten o największej współrzędnej x),
• wyznaczanie prawego łańcucha otoczki (niebieski):
  1. $i:=1,$
  2. powtarzaj:
     • $S:=P_{i},$
     • $P_{i+1}$ – punkt $N,$ dla którego kąt między wektorem $SN$ a wektorem $[1,0]$ jest najmniejszy; $N$ należy do otoczki,
     • jeśli $N=Q_{1},$ koniec iterowania,
     • $i:=i+1,$
• wyznaczanie lewego łańcucha otoczki (czerwony):
  1. $i:=1,$
  2. powtarzaj:
     • $S:=Q_{i},$
     • $Q_{i+1}$ – punkt $N,$ dla którego kąt między wektorem $SN$ a wektorem $[-1,0]$ jest najmniejszy; $N$ należy do otoczki,
     • jeśli $N=P_{1},$ koniec iterowania,
     • $i:=i+1,$
• ostatecznie otoczkę wypukłą określają punkty $P$ i $Q$ (z pominięciem tych powtarzających się na granicach łańcuchów)

Wariant 2

Przebieg algorytmu Jarvisa dla przykładowych danych

Zamiast rozpatrywać dwa osobne łańcuchy, można od razu utworzyć całą otoczkę.

• $P_{1}$ – punkt na otoczce wypukłej o najmniejszej współrzędnej y (jeśli jest więcej niż jeden, wybierany jest ten o najmniejszej współrzędnej x),
• $P_{0}:=[-\infty ,y(P_{1})],$
• $i:=1,$
• powtarzaj:
  • $P_{i+1}$ – punkt $N,$ dla którego kąt $P_{i-1}P_{i}N$ jest największy,
  • jeśli $N=P_{1},$ koniec iterowania,
  • $i:=i+1,$
• ostatecznie otoczkę tworzą punkty $P_{1\dots i}.$

Implementację można usprawnić, odrzucając w każdej iteracji punkty znajdujące się po prawej stronie wektora $P_{1}P_{i},$ ponieważ na pewno nie będą należały do otoczki. Zabieg ten nie wpływa jednak na asymptotyczną złożoność obliczeniową algorytmu.

Algorytm w przestrzeni

Algorytm w przestrzeni znajduje wielościan wypukły, którego ścianami są trójkąty.

1. Zrzutuj punkty na płaszczyznę (np. XY) i wykonaj dwa pierwsze kroki algorytmu dla płaszczyzny:
   • znajdź dolny punkt otoczki $P_{1},$
   • oraz kolejny punkt na otoczce $P_{2}.$
2. Dodaj krawędź $P_{1}P_{2}$ do kolejki.
3. Dopóki kolejka nie pusta, powtarzaj:
   • weź krawędź $AB$ z kolejki,
   • znajdź taki punkt $C,$ aby wszystkie pozostałe punkty znalazły się po lewej stronie trójkąta $ABC,$
   • trójkąt $ABC$ należy do otoczki,
   • dodaj do kolejki dwie krawędzie nowego trójkąta: $AC$ i $BC$ (o ile nie były wcześniej przetwarzane).

Algorytm w wyższych wymiarach

Algorytm dla danych trójwymiarowych można uogólnić na przestrzenie o większej liczbie wymiarów.

Zobacz też

• algorytm Grahama
• quickhull

Bibliografia

• Lech Banachowski, Krzysztof Diks, Wojciech Rytter: Algorytmy i struktury danych. Warszawa: Wydawnictwa Naukowo-Techniczne, 2003, s. 267–268. ISBN 83-204-2796-7.