Algorytm Jarvisa

Algorytm Jarvisa

Algorytm Jarvisa, znany również jako marsz Jarvisa lub metoda owijania prezentów (ang. gift wrapping algorithm), to technika służąca do wyznaczania otoczki wypukłej dla zbioru punktów rozmieszczonych na płaszczyźnie lub w przestrzeni wyższych wymiarów.

Algorytm ten został niezależnie opracowany przez Donalda Chanda oraz Shama Kapura w 1970 roku, a także przez R. Jarvisa w 1973 roku, który skupił się na przypadku płaskim.

Algorytm na płaszczyźnie

Algorytm działa w czasie O(kn), gdzie n oznacza całkowitą liczbę punktów, a k to liczba punktów należących do otoczki. W praktyce zazwyczaj k jest znacznie mniejsze od n (k << n), jednak w najgorszym przypadku złożoność czasowa może wynosić O(n2).

Wariant 1

Algorytm przebiega według następujących kroków:

  • P1 – 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),
  • Q1 – 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 (w kolorze niebieskim):

  • i := 1,
  • powtarzaj:
    • S := Pi,
    • Pi + 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 = Q1, koniec iterowania,
    • i := i + 1,

Wyznaczanie lewego łańcucha otoczki (w kolorze czerwonym):

  • i := 1,
  • powtarzaj:
    • S := Qi,
    • Qi + 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 = P1, koniec iterowania,
    • i := i + 1,

Ostatecznie otoczkę wypukłą określają punkty P i Q (pomijając te powtarzające się na granicach łańcuchów).

Wariant 2

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

  • P1 – 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),
  • P0 := [-∞, y(P1)],
  • i := 1,
  • powtarzaj:
    • Pi + 1 – punkt N, dla którego kąt Pi-1PiN jest największy;
    • jeśli N = P1, koniec iterowania,
    • i := i + 1.

Ostatecznie otoczkę tworzą punkty P1…i.

Implementację można usprawnić, odrzucając w każdej iteracji punkty znajdujące się po prawej stronie wektora P1Pi, ponieważ na pewno nie będą należały do otoczki. Ta operacja 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. Aby go zrealizować, zrzutuj punkty na płaszczyznę (np. XY) i wykonaj dwa początkowe kroki algorytmu dla płaszczyzny:

  • znajdź dolny punkt otoczki P1,
  • oraz kolejny punkt na otoczce P2.

Dodaj krawędź P1P2 do kolejki. Dopóki kolejka nie jest pusta, powtarzaj:

  • weź krawędź AB z kolejki,
  • znajdź taki punkt C, aby wszystkie pozostałe punkty były 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

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

Zobacz też

Przypisy

Bibliografia

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

Przeczytaj u przyjaciół: