Quickhull

Quickhullalgorytm dziel i zwyciężaj z dziedziny geometrii obliczeniowej, który wyznacza otoczkę wypukłą zbioru punktów umieszczonych w przestrzeni o dowolnej liczbie wymiarów (dwa, trzy i więcej). Algorytm jest wzorowany na metodzie sortowania szybkiego (ang. quicksort) i podobnie charakteryzuje go średnia złożoność natomiast pesymistyczna

Algorytm został niezależnie odkryty przez Williama Eddy’ego (1977) i Alexa Bykata (1978) oraz Greena i Silvermana (1979).

Algorytm na płaszczyźnieEdytuj

Przygotowanie danych:

  1. Znajdź w zbiorze punktów dwa skrajne punkty o minimalnej i maksymalnej współrzędnej x (  i  ).
     
  2. Podziel zbiór punktów na dwa podzbiory S1 i S2 znajdujące się nad i pod prostą  
     
  3. Wywołaj rekurencyjnie QuickHull(A, B, S1) i QuickHull(B, A, S2).

Zamiast wyznaczać dwa skrajne punkty, można uwzględnić trzy lub cztery skrajne, otrzymując odpowiednio trójkąt lub czworokąt wypukły i od razu odrzucić wszystkie punkty należące do wnętrza figur. Wówczas procedurę QuickHull należy wywołać dla każdego boku figury, uprzednio dzieląc odpowiednio zbiór punktów.

Procedura QuickHull jako argumenty przyjmuje dwa punkty   i   wyznaczające prostą oraz zbiór   rozpatrywanych punktów:

  • Jeśli   jest pusty – koniec.
  • Jeśli   ma jeden element, ten punkt należy do otoczki – koniec.
  • W przeciwnym razie:
    1. Znajdź w   punkt   najbardziej oddalony od prostej   Ten punkt należy do otoczki wypukłej.
    2. Odrzuć wszystkie punkty z wnętrza trójkąta   nie mogą należeć do otoczki.
       
    3. Znajdź zbiór S1 punktów znajdujących się po prawej stronie prostej   oraz analogiczny zbiór S2 dla prostej   (Stronę określa znak równania ogólnego prostej).
       
    4. Wywołaj rekurencyjnie QuickHull(A, C, S1) oraz QuickHull(B, C, S2).

PseudokodEdytuj

procedure otoczka(punkty)
	begin
		A := skrajny lewy punkt
		B := skrajny prawy punkt
		s1 := zbiór punktów po prawej stronie AB
		s2 := zbiór punktów po lewej stronie AB

		return [A] + QuickHull(A, B, s1) + [B] + QuickHull(B, A, s2);
	end;

procedure QuickHull(A, B, punkty)
	begin
		C := najbardziej odległy punkt od prostej AB
		s1 := zbiór punktów znajdujących się na prawo od prostej AC
		s2 := zbiór punktów znajdujących się na prawo od prostej CB

		return QuickHull(A, C, s1) + [C] + QuickHull(C, B, s2);
	end;


Zobacz teżEdytuj

BibliografiaEdytuj

  • William F. Eddy. A New convex Hull Algorithm for Planar Sets. „ACM Transactions on Mathematical Software”. 3, s. 393–403, 1977 (ang.). 
  • Alex Bykat. Convex Hull of a Finite Set of Points in Two Dimensions. „Information Processing Letters”. 7, s. 296–298, 1978 (ang.). 
  • P.J. Green, B.W. Silverman. Constructing the Convex Hull of a Set of Points in the Plane. „Computer Journal”. 22, s. 262–266, 1979 (ang.).