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 na płaszczyźnieEdytuj

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 1Edytuj

 
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):
    1.  
    2. 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):
    1.  
    2. 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 2Edytuj

 
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 przestrzeniEdytuj

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  
    • oraz kolejny punkt na otoczce  
  2. Dodaj krawędź   do kolejki.
  3. 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 wymiarachEdytuj

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

Zobacz teżEdytuj

PrzypisyEdytuj

  1. Donald R. Chand, Sham Kupur. An algorithm for convex polytypes. „JACM”, s. 78–86, 1970 (ang.). 
  2. R.A. Jarvis. On the identification of the convex hull of a finite set of points in the plane. „Information Processing Letters”, s. 18–21, 1973. DOI: 10.1016/0020-0190(73)90020-3 (ang.). 

BibliografiaEdytuj

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