Algorytm Jarvisa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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źnie[edytuj]

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[edytuj]

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. 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. 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[edytuj]

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[edytuj]

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 wymiarach[edytuj]

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

Zobacz też[edytuj]

Przypisy

  1. Donald R. Chand, Sham Kupur. An algorithm for convex polytypes. „JACM”, s. 78-86, 1970 (ang.). 
  2. Jarvis, R. A.. 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.). 

Bibliografia[edytuj]

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