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:=[-\mathrm{\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. Szablon:Clear

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

• Szablon:Cytuj książkę