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)^[1] oraz R. Jarvisa (1973, przypadek na płaszczyźnie)^[2].

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

Algorytm przebiega następująco:

• ${\displaystyle 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),
• ${\displaystyle 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. ${\displaystyle i:=1,}$
  2. powtarzaj:
     • ${\displaystyle S:=P_{i},}$
     • ${\displaystyle P_{i+1}}$ – punkt ${\displaystyle N,}$ dla którego kąt między wektorem ${\displaystyle SN}$ a wektorem ${\displaystyle [1,0]}$ jest najmniejszy; ${\displaystyle N}$ należy do otoczki,
     • jeśli ${\displaystyle N=Q_{1},}$ koniec iterowania,
     • ${\displaystyle i:=i+1,}$
• wyznaczanie lewego łańcucha otoczki (czerwony):
  1. ${\displaystyle i:=1,}$
  2. powtarzaj:
     • ${\displaystyle S:=Q_{i},}$
     • ${\displaystyle Q_{i+1}}$ – punkt ${\displaystyle N,}$ dla którego kąt między wektorem ${\displaystyle SN}$ a wektorem ${\displaystyle [-1,0]}$ jest najmniejszy; ${\displaystyle N}$ należy do otoczki,
     • jeśli ${\displaystyle N=P_{1},}$ koniec iterowania,
     • ${\displaystyle i:=i+1,}$
• ostatecznie otoczkę wypukłą określają punkty ${\displaystyle P}$ i ${\displaystyle Q}$ (z pominięciem tych powtarzających się na granicach łańcuchów)

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

• ${\displaystyle 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),
• ${\displaystyle P_{0}:=[-\infty ,y(P_{1})],}$
• ${\displaystyle i:=1,}$
• powtarzaj:
  • ${\displaystyle P_{i+1}}$ – punkt ${\displaystyle N,}$ dla którego kąt ${\displaystyle P_{i-1}P_{i}N}$ jest największy,
  • jeśli ${\displaystyle N=P_{1},}$ koniec iterowania,
  • ${\displaystyle i:=i+1,}$
• ostatecznie otoczkę tworzą punkty ${\displaystyle P_{1\dots i}.}$

Implementację można usprawnić, odrzucając w każdej iteracji punkty znajdujące się po prawej stronie wektora ${\displaystyle 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 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 ${\displaystyle P_{1},}$
   • oraz kolejny punkt na otoczce ${\displaystyle P_{2}.}$
2. Dodaj krawędź ${\displaystyle P_{1}P_{2}}$ do kolejki.
3. Dopóki kolejka nie pusta, powtarzaj:
   • weź krawędź ${\displaystyle AB}$ z kolejki,
   • znajdź taki punkt ${\displaystyle C,}$ aby wszystkie pozostałe punkty znalazły się po lewej stronie trójkąta ${\displaystyle ABC,}$
   • trójkąt ${\displaystyle ABC}$ należy do otoczki,
   • dodaj do kolejki dwie krawędzie nowego trójkąta: ${\displaystyle AC}$ i ${\displaystyle BC}$ (o ile nie były wcześniej przetwarzane).

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

• algorytm Grahama
• quickhull

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