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ść $O(n\log n),$ natomiast pesymistyczna $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:

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

Jeśli $P$ jest pusty – koniec.
Jeśli $P$ ma jeden element, ten punkt należy do otoczki – koniec.
W przeciwnym razie:
1. Znajdź w $P$ punkt $C$ najbardziej oddalony od prostej $AB.$ Ten punkt należy do otoczki wypukłej.
2. Odrzuć wszystkie punkty z wnętrza trójkąta $ABC,$ nie mogą należeć do otoczki.
3. Znajdź zbiór S1 punktów znajdujących się po prawej stronie prostej $AC$ oraz analogiczny zbiór S2 dla prostej $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;

Zobacz też

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