Post ten składa się z dwóch części. Część pierwsza jest wytłumaczeniem samego algorytmu do obliczenia otoczki wypukłej Quick Hull. Częścią drugą będzie ubranie poniższego w kod JS.
Otoczka wypukła - definicja
Otoczka wypukła (ang: convex hull) jest takim wielokątem, że każdy punkt ze zbioru leży albo w jego wętrzu, albo na jego brzegu. Zakładając, że mamy punkty o numerach od 0 do 13 należące do zbioru Q, jak na poniższym schemacie - otoczką H będzie wielokąt wyznaczony przez punkty [0, 2, 4, 6, 3, 5]
Otoczka wypukła dla zbioru punktów - krok po kroku
Jest dość dużo algorytmów, które pomagają wyznaczyć otoczkę wypukłą 1. Jedne są mniej skomplikowane inne trochę bardziej. Ich złożoność obliczeniowa O waha się od O(n log n) do O(n²) w najgorszych przypadkach.
Zastosowanie praktyczne jakie mi przychodzi na myśl dla otoczki wypukłej to gry choć pewnie nie tylko
Zauważyłam, że najczęściej wykorzystywany jest Algorytm Grahama do omawiania zagadnień algorytmu wyznaczania otoczki wypukłej - choć ciężko mi powiedzieć dlaczego. Do mnie on nie “przemówił”. Natomiast bardzo podszedł mi algorytm QuickHull, na którym właśnie skupię się w moim wpisie.
Quick Hull - na czym polega
Algorytm Quick Hull polega na wyznaczaniu w zbiorze skrajnych punktów, łączeniu ich ze sobą, dzieleniu przestrzeni na dwie częsci, sprawdzeniu maksymalnej odległości od granicy części i tak rekursywnie, aż nie zostanie nam żaden punkt do sprawdzenia.
Otoczka wypukła dla zbioru punktów - krok po kroku
Krok 1 - Quick hullKrok 1- Wyznaczamy dwa skrajne punkty w przestrzeni (takie które będą miały min x i max(x)). Na moim przykładzie są to punkty `3` i `2` i łączymy je prostą dzielącą nasz zbiór na dwie części (jak na obrazku powyżej).
Krok 2 - Quick hullKrok 2 - Sprawdzamy, który punkt jest najdalej oddalony od naszej prostej - w moim przypadku jest to `6`.
Krok 3 - Quick hullKrok 3 - Tworzymy z tych punktów trójkąt. Wszystkie punkty wewnątrz trójkąta - zaznaczone na niebiesko NIE NALEŻĄ do otoczki `[1, 8, 12]`- możemy je wykluczyć. Te leżące na skraju - zaznaczone na żółto `[7, 4]` - są kandydatami do otoczki.
Krok 4 - Quick hullKrok 4 - Sprawdzamy i wybieramy max odległość od lini pomiędzy punktami `6` i `2` - w tym wypadku jest to punkt `4`.
Krok 5 - Quick hullKrok 5 - Między punktami `6`, `2` i `4` znów wyznaczamy trójkąt. Punkt `7` leży w wyzanczonym trójkącie - możemy więc go wykluczyć ze zbioru otoczki. Natomiast punkt `4` zaliczamy do otoczki. Po tej stronie skończyły się nam już punkty.
Krok 6 - Quick hullKrok 6 - wracamy do linii 3->2 i sprawdzamy punkty w drugą stronę.
Krok 7 - Quick hullKrok 7 - Sprawdzamy punkty w drugą stronę. Szukamy tego, który ma max odległość od lini `3` i `2`. W moim przypadku jest to `0`.
Krok 8 - Quick hullKrok 8 - Łączymy ze sobą punkty `3`, `2` i `0` w trójkąt. Wszystkie punkty wewnątrz wykluczamy z otoczki, czyli, mamy pewność, że `[9, 13, 11]` NIE NALEŻĄ do otoczki (są to punkty zaznaczone na niebiesko). Te zaznaczone na żółto `[5, 10]` są kandydatami do otoczki.
Krok 9 - Quick hullKrok 9 - Sprawdzamy odległości tych dwóch punktów od lini `3`->`0` i wybieramy ten, który jest od niej najdalej. W moim przypadku jest to punkt `5`.
Krok 10 - Quick hullKrok 10 - Łączymy ze sobą `[3, 0, 5]` w trójkąt. Wszystkie punkty wewnątrz - zaznaczone na niebiesko NIE NALEŻĄ do otoczki - `10`.
W tym momecie nie zostało nam więcej punktów do sprawdzenia. Przejdźmy więc do wypisania wyniku.
Krok 11 - Quick hullFINALNY Krok 11 W naszym algorytmie wyznaczyliśmy sobie dwa zbiory punktów - te, które należą do otoczki i te które nie należą do otoczki. W moim przypadku punktami otoczki są `[0, 5, 3, 6, 4, 2]`.
Całkiem sprawnie poszło - tyle, że rozpisywanie tego zajeło trochę czasu. Na szczęście mamy programowanie i rekursję, która powyżej rozpisane kroki wykona nam znacznie, znacznie szybciej . Ale o tym będzie w częsci drugiej.
Pisanie kodu jest moją pasją. Zajmuję się tym od przeszło 10 lat, z większą lub mniejszą intensywnością. Piszę kod w PHP, JS, SCSS i Python. Nie stronię też od poznawania nowych, lub jak kto woli starych rozwiązań jak Jekyll oraz innych języków
np. Java.
