PL 
EnglishDomyślny
Українська🟦 Otoczka wypukła
Wyznacz najmniejszy wielokąt wypukły zawierający zbiór punktów metodą Grahama, marszem Jarvisa albo algorytmem Quickhull — animowane krok po kroku, z wykrywaniem zwrotu iloczynem wektorowym i porównaniem liczby operacji.
O otoczce wypukłej
Otoczka wypukła zbioru punktów to najmniejszy wielokąt wypukły zawierający je wszystkie — równoważnie, kształt utworzony przez naciągnięcie gumki wokół najbardziej zewnętrznych punktów. Efektywne obliczanie otoczek wypukłych to fundamentalny problem geometrii obliczeniowej, z zastosowaniami w wykrywaniu kolizji (otoczka wypukła sztywnego ciała to jego najprostsza bryła otaczająca), analizie kształtów, wyszukiwaniu ścieżek oraz planowaniu ruchu robotów. Optymalna złożoność czasowa w najgorszym przypadku wynosi O(n log n) dla n punktów wejściowych, osiągalna przez algorytm Grahama (1972) i kilka innych algorytmów; dla zbiorów punktów, w których otoczka ma h wierzchołków, algorytmy czułe na wyjście, takie jak marsz Jarvisa, osiągają O(nh), co jest szybsze, gdy h jest małe.
Ten symulator implementuje i animuje trzy klasyczne algorytmy obok siebie. Algorytm Grahama sortuje wszystkie punkty według kąta biegunowego wokół najniższego punktu, a następnie przechodzi przez nie za pomocą stosu, odrzucając każdy punkt tworzący skręt w prawo (nielewy iloczyn wektorowy). Marsz Jarvisa (owijanie prezentu) wielokrotnie wybiera punkt tworzący najmniejszy kąt przeciwny do ruchu wskazówek zegara od bieżącej krawędzi. Quickhull rekurencyjnie dzieli zbiór punktów, używając najdalszego punktu powyżej każdej krawędzi, podobnie do kroku partycjonowania w quicksort. Możesz klikać, by dodawać punkty, przeciągać, by je przemieszczać, oraz przechodzić krok po kroku przez każdy algorytm, by porównać stany pośrednie i liczby operacji.
Najczęściej zadawane pytania
Jaka jest złożoność czasowa algorytmu Grahama, marszu Jarvisa i Quickhull?
Algorytm Grahama działa w czasie O(n log n) ze względu na wstępne sortowanie kątowe; przejście stosu ma złożoność O(n). Marsz Jarvisa (owijanie prezentu) działa w czasie O(nh), gdzie h to liczba wierzchołków otoczki: w najgorszym przypadku (wszystkie punkty na otoczce) jest to O(n²), ale dla typowych zbiorów punktów z h = O(log n) jest to O(n log n). Quickhull ma średni czas O(n log n) (jak quicksort), ale najgorszy przypadek O(n²), gdy wszystkie punkty leżą na otoczce i są przetwarzane pojedynczo. Algorytm Chana (1996) osiąga optymalne O(n log h) we wszystkich przypadkach.
Jak test iloczynu wektorowego określa skręt w lewo czy w prawo?
Dla trzech punktów A, B, C oblicz dwuwymiarowy iloczyn wektorowy (B − A) × (C − A) = (Bx−Ax)(Cy−Ay) − (By−Ay)(Cx−Ax). Wartość dodatnia oznacza, że C leży na lewo od skierowanej linii A→B (skręt przeciwny do ruchu wskazówek zegara), ujemna oznacza prawo (zgodnie z ruchem wskazówek zegara, do odrzucenia w algorytmie Grahama), a zero oznacza współliniowość. Ten test orientacji O(1) jest fundamentalną operacją we wszystkich algorytmach otoczki wypukłej — a także w wielu innych algorytmach geometrii obliczeniowej, takich jak triangulacja wielokątów i przecięcie odcinków.
Jaka jest dolna granica obliczania otoczki wypukłej?
Problem otoczki wypukłej ma dolną granicę Ω(n log n) w modelu algebraicznego drzewa decyzyjnego, dowiedzioną przez redukcję z sortowania: mając n liczb x₁, …, xn, umieść punkty (xᵢ, xᵢ²) na paraboli — ich otoczka wypukła to cały zbiór, zwrócony w kolejności posortowanej. Ponieważ sortowanie wymaga Ω(n log n) porównań, każdy algorytm rozwiązujący oba problemy musi również zająć Ω(n log n). Czyni to algorytm Grahama i algorytmy typu merge-hull asymptotycznie optymalnymi dla ogólnych zbiorów punktów.
Jak otoczka wypukła jest wykorzystywana w wykrywaniu kolizji?
W dwuwymiarowej fizyce gier otoczka wypukła wielokąta jest jego minimalną wypukłą otuliną. Dwa wielokąty wypukłe można sprawdzić pod kątem przecięcia za pomocą twierdzenia o osi rozdzielającej (SAT): jeśli istnieje linia rozdzielająca obie otoczki, nie zachodzą one na siebie — a testowaniu podlega tylko O(h₁ + h₂) kandydujących osi rozdzielających (po jednej na krawędź). Algorytm GJK (Gilbert-Johnson-Keerthi) rozszerza to na 3D i obsługuje obiekty zakrzywione, obliczając różnicę Minkowskiego, osiągając w praktyce O(1) iteracji dla prostych kształtów. Zarówno SAT, jak i GJK są fundamentalnymi narzędziami w Unity, Bullet i innych silnikach fizyki.
Co się dzieje, gdy punkty są współliniowe na granicy otoczki?
Punkty leżące na krawędzi otoczki, ale niebędące wierzchołkami (są współliniowe między dwoma wierzchołkami otoczki), mogą być uwzględniane lub pomijane w zależności od wariantu algorytmu. Standardowy algorytm Grahama wyklucza współliniowe punkty wewnętrzne (usuwa je podczas kroku deduplikacji sortowania), dając minimalny zbiór wierzchołków. Niektóre zastosowania (np. obliczanie powierzchni wielokąta) preferują uwzględnianie wszystkich punktów granicznych. Wybór wpływa na h (rozmiar otoczki), czas działania oraz zachowanie testu orientacji iloczynu wektorowego (zerowy iloczyn wektorowy musi być obsłużony ostrożnie, by uniknąć nieskończonych pętli w marszu Jarvisa).
Czym jest algorytm Chana i dlaczego jest optymalny?
Algorytm Chana (Timothy Chan, 1996) osiąga czas O(n log h), gdzie h to liczba wierzchołków otoczki — jest to optymalne, ponieważ wypisanie h wierzchołków zajmuje czas Ω(h), a sortowanie n punktów zajmuje Ω(n log n). Podejście Chana zgaduje h w fazach podwajania (próbuje h = 2, 4, 8, …), uruchamiając mini-marsz Jarvisa, który zatrzymuje się po h krokach, wykorzystując wstępnie obliczony algorytm Grahama na n/h grupach punktów jako wewnętrzne wyrocznie. Gdy zgadnięta wartość równa się prawdziwemu h, algorytm kończy działanie z poprawną otoczką. Każda faza kosztuje O(n log h); podwajanie dodaje jedynie stały czynnik, dając łącznie O(n log h).
Jak otoczka wypukła jest wykorzystywana w programowaniu liniowym?
W dwuwymiarowym programowaniu liniowym region dopuszczalny zdefiniowany przez m ograniczeń nierównościowych jest wielokątem wypukłym — otoczką wypukłą punktów przecięcia ograniczeń. Optymalne rozwiązanie programu liniowego zawsze leży w wierzchołku dopuszczalnego wielotopu. Metoda simpleks przechodzi przez wierzchołki tego wielotopu; metody punktu wewnętrznego przechodzą przez wnętrze. W wyższych wymiarach (d zmiennych, m ograniczeń) obliczanie wyliczenia wierzchołków dopuszczalnego wielotopu jest równoważne obliczeniu otoczki wypukłej w d wymiarach — problemowi rozwiązywanemu przez algorytmy podwójnego opisu i beneath-beyond.
Czym jest trójwymiarowa otoczka wypukła i jakie algorytmy ją obliczają?
W 3D otoczka wypukła n punktów jest wielościanem wypukłym o co najwyżej O(n) wierzchołkach, krawędziach i ścianach (zgodnie ze wzorem Eulera: V − E + F = 2, a dla wielościanów wypukłych F ≤ 2n − 4). Algorytmy obejmują trójwymiarowy algorytm Grahama (wstawianie przyrostowe), dziel i zwyciężaj (O(n log n)) oraz wariant owijania prezentu (marsz Jarvisa w 3D). Algorytm QuickHull3D autorstwa Barbera, Dobkina i Huhdanpaa (1996, biblioteka qhull) jest praktycznym standardem — używanym w ConvexHull z SciPy, MATLAB-ie i narzędziach fizyki silników gier.
Czy algorytmy otoczki wypukłej obsługują duplikaty punktów?
Zduplikowane punkty (identyczne współrzędne) muszą być obsłużone jawnie; większość implementacji deduplikuje dane wejściowe przed uruchomieniem algorytmu otoczki. W algorytmie Grahama zduplikowane punkty wytwarzałyby zerowe iloczyny wektorowe, powodując niejednoznaczność w sortowaniu kątowym. W marszu Jarvisa wybranie duplikatu jako następnego wierzchołka otoczki mogłoby spowodować nieskończoną pętlę. Solidna implementacja albo usuwa duplikaty w preprocessingu O(n log n), albo używa dokładnej arytmetyki z perturbacją (perturbacja symboliczna / SOS — symulacja prostoty), by spójnie obsłużyć wszystkie zdegenerowane konfiguracje.
Jaki jest związek między otoczką wypukłą a diagramami Woronoja?
Istnieje klasyczna dualność: dwuwymiarowy diagram Woronoja n punktów jest równoważny rzutowi trójwymiarowej otoczki wypukłej tych samych punktów podniesionych na paraboloidę z = x² + y². Konkretnie, podnieś każdy punkt (xᵢ, yᵢ) do (xᵢ, yᵢ, xᵢ² + yᵢ²), oblicz trójwymiarową otoczkę wypukłą, a następnie rzutuj ściany dolnej otoczki z powrotem do 2D — wynikiem jest triangulacja Delaunaya, a jej graf dualny to diagram Woronoja. Oznacza to, że dowolny algorytm trójwymiarowej otoczki wypukłej O(n log n) natychmiast daje algorytm Woronoja O(n log n), pasujący do klasycznego algorytmu zamiatania Fortune'a.
Jak otoczka wypukła jest zastosowana w uczeniu maszynowym?
W maszynach wektorów nośnych (SVM) klasyfikator o maksymalnym marginesie między dwiema klasami punktów odpowiada znalezieniu najbliższych punktów na otoczkach wypukłych obu klas — dualnej „minimalnej otaczającej kuli”. Wektory nośne SVM to dokładnie punkty otoczki najbliższe hiperpłaszczyźnie rozdzielającej. Otoczki wypukłe pojawiają się też w głębokości danych (głębokość Tukeya, algorytm „obierania cebuli”), wykrywaniu anomalii (punkty danych poza otoczką to wartości odstające) oraz w optymalizacji wielokryterialnej, gdzie front Pareto jest częścią otoczki wypukłej dopuszczalnych wektorów celu.