Loading AI tools
Z Wikipedii, wolnej encyklopedii
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ść natomiast pesymistyczna
Algorytm został niezależnie odkryty przez Williama Eddy’ego (1977) i Alexa Bykata (1978) oraz Greena i Silvermana (1979).
Przygotowanie danych:
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:
QuickHull(A, C, S1)
oraz QuickHull(B, C, S2)
.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;
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.