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 gdzie to całkowita liczba punktów, natomiast to liczba punktów należących do otoczki. Zwykle w praktyce jednak w pesymistycznym przypadku złożoność czasowa może wynieść
Wariant 1 thumb|400px|Przebieg algorytmu Jarvisa dla przykładowych danych Algorytm przebiega następująco: – 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), – 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):
powtarzaj:
– punkt dla którego kąt między wektorem a wektorem jest najmniejszy; należy do otoczki, jeśli koniec iterowania,
wyznaczanie lewego łańcucha otoczki (czerwony):
powtarzaj:
– punkt dla którego kąt między wektorem a wektorem jest najmniejszy; należy do otoczki, jeśli koniec iterowania,
ostatecznie otoczkę wypukłą określają punkty i (z pominięciem tych powtarzających się na granicach łańcuchów)
Wariant 2 thumb|400px|Przebieg algorytmu Jarvisa dla przykładowych danych Zamiast rozpatrywać dwa osobne łańcuchy, można od razu utworzyć całą otoczkę. – 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),
powtarzaj: – punkt dla którego kąt jest największy, jeśli koniec iterowania,
ostatecznie otoczkę tworzą punkty
Implementację można usprawnić, odrzucając w każdej iteracji punkty znajdujące się po prawej stronie wektora 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.
Zrzutuj punkty na płaszczyznę (np. XY) i wykonaj dwa pierwsze kroki algorytmu dla płaszczyzny: znajdź dolny punkt otoczki oraz kolejny punkt na otoczce Dodaj krawędź do kolejki. Dopóki kolejka nie pusta, powtarzaj: weź krawędź z kolejki, znajdź taki punkt aby wszystkie pozostałe punkty znalazły się po lewej stronie trójkąta trójkąt należy do otoczki, dodaj do kolejki dwie krawędzie nowego trójkąta: i (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
Przypisy
Bibliografia
Jarvisa