Quickhull

Quickhull – algorytm 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ść ${\displaystyle O(n\log n),}$ natomiast pesymistyczna ${\displaystyle O(n^{2}).}$

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

Algorytm na płaszczyźnie

Przygotowanie danych:

1. Znajdź w zbiorze punktów dwa skrajne punkty o minimalnej i maksymalnej współrzędnej x (${\displaystyle A}$ i ${\displaystyle B}$).
   
2. Podziel zbiór punktów na dwa podzbiory S1 i S2 znajdujące się nad i pod prostą ${\displaystyle AB.}$
   
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 ${\displaystyle A}$ i ${\displaystyle B}$ wyznaczające prostą oraz zbiór ${\displaystyle P}$ rozpatrywanych punktów:

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

Pseudokod

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;

Animacja

Zobacz też

• algorytm Grahama
• algorytm Jarvisa

Bibliografia

• 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.).