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: Znajdź w punkt najbardziej oddalony od prostej Ten punkt należy do otoczki wypukłej. Odrzuć wszystkie punkty z wnętrza trójkąta nie mogą należeć do otoczki.Plik:Quickhull example5.svg 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).Plik:Quickhull example6.svg 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;
left|Animacja
Zobacz też algorytm Grahama algorytm Jarvisa
Bibliografia
Kategoria:Algorytmy