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

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

Wariant 1[edytuj | edytuj kod]

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

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 := [-\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 \ldots 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.

Algorytm w przestrzeni[edytuj | edytuj kod]

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

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

Zobacz też[edytuj | edytuj kod]

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

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