Obłok Konwexowy: Owijanie Punktu w Najmniejszej Możliwej Licbie Obrótów

Najmniejszy worek, który mieści wszystkie punkty

Rozważmy zbiór punktów. Ich obłukowa оболочка (convex hull) to najmniejszy wypukły wielokąt, który zawiera wszystkie te punkty – wyobraź sobie rozciągniętego gumowego paska wokół całego zbioru punktów i mocno go napnij. Każdy punkt leży albo na granicy obłukowej оболочки (convex hull), albo ściśle wewnątrz niej, a wierzchołki obłukowej оболочки to dokładnie punkty, do których faktycznie dotknąłby gumowy pasek. Jest to jedno z najstarszych i najczęściej wykorzystywanych problemów w geometrii obliczeniowej, a trzy naprawdę różne algorytmy rozwiązują go, każdy z innym kompromisem.

Jedynowy test, którego potrzebuje każdy algorytm obróbki brzegów

Wszystkie trzy algorytmy opierają się na tym samym podstawowym elemencie: jeśli mamy dane trzy punkty a, b i c, w którym kierunku należy skręcić przy b podczas chodzenia z a do c? Znak iloczynu wektorowego 2D odpowiada na to w jednym mnożeniu i odejmowaniu:

cross(a, b, c) = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) cross > 0 → skręć w lewo przy b (przeciwnie do ruchu) cross < 0 → skręć w prawo przy b (w kierunku ruchu) cross == 0 → punkty a, b i c są współliniowe Każdy z poniższych algorytmów obróbki brzegów jest strukturalnie sposobem na wybór punktów do testowania za pomocą tego jednego sprawdzenia znaku oraz w jakiej kolejności – różnice między nimi dotyczą wyłącznie wydajności, a nie poprawności.

cross(a, b, c) = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)

cross > 0   →  counter-clockwise (left) turn at b
cross < 0   →  clockwise (right) turn at b
cross == 0  →  a, b, c are collinear

Skan Grahama: posortuj raz, przesuwaj się raz

Algorytm Ronald Grahama z 1972 roku najpierw wybiera punkt o najniższym współrzędnej y (rozwiązując ewentualne kolizyje przez najniższą współrzędną x) jako nieruchomy punkt odniesienia, a następnie sortuje wszystkie pozostałe punkty według kąta polarnego wokół tego punktu odniesienia. Następnie przesuwa się po posortowanych punktach raz, utrzymując stos kandydatów do obwodu i usuwając z góry stos, gdy dodanie następnego punktu spowodowałoby łuk skierowany zgodnie z ruchem wskazówek zegara (nielewy) obrót:

punkt_odniesienia = punkt o najniższej y (w razie kolizji, o najniższym x) punkty = wszystkie pozostałe punkty, posortowane według kąta polarnego wokół punktu odniesienia stos = [punkt_odniesienia, punkty[0]] for p in punkty[1:]: while cross(stack[-2], stack[-1], p) <= 0: # nie jest to obrót w lewo stack.pop() stack.append(p) return stack // obwód, w kolejności

Koszt sortowania wynosi O(n log n), a sam przesuw się O(n) — każdy punkt jest dodawany raz i usuwany z góry stos najwyżej raz — więc cały algorytm ma złożoność O(n log n), całkowicie dominowaną przez początkowe sortowanie, niezależnie od liczby punktów znajdujących się na ostatecznym obwodzie.

pivot = point with lowest y (then lowest x)
points = all other points, sorted by polar angle around pivot
stack = [pivot, points[0]]
for p in points[1:]:
    while cross(stack[-2], stack[-1], p) <= 0:   // not a left turn
        stack.pop()
    stack.push(p)
return stack                                     // the hull, in order

Marsz Jarvis: Opakowywanie prezentów, krok po kroku do jednej osłony

Algorytm opakowywania prezentów (R. A. Jarvis, 1973) działa zupełnie inaczej: zaczynając od lewego punktu, powtarza się, znajdując jeden punkt taki, że każdy inny leży przeciwnie do ruchu wskazówek zegara względem odcinka od aktualnego punktu do niego – dosłownie owijać wstążkę wokół zewnątrz zbioru, krok po kroku do jednej osłony – aż wróci do punktu początkowego.

aktualny = lewy punkt warstwa = [aktualny] powtarzaj: kandydat = inny punkt dla każdego punktu p: jeżeli cross(aktualny, kandydat, p) < 0: // p jest bardziej zgodnie z ruchem wskazówek zegara kandydat = p // → kandydat staje się p warstwa.dodaj(kandydat) aktualny = kandydat ponoć aktualny == warstwa[0]

current = leftmost point
hull = [current]
repeat:
    candidate = any other point
    for each point p:
        if cross(current, candidate, p) < 0:      // p is more clockwise
            candidate = p                          // → candidate becomes p
    hull.push(candidate)
    current = candidate
until current == hull[0]

Szybkiłas: dziel i podbij, odrzucaj

Szybkiłas (niezależnie opracowany przez kilku autorów, popularyzowany przez Barbera, Dobkina i Huhdanpaaa w 1996 roku) czerpie swoją strukturę bezpośrednio z algorytmu quicksorta. Rozpocznij od dwóch punktów najbardziej skrajnych (lewej i prawej krawędzi), które są gwarantowane jako leżące na obwoluce, i podziel pozostałe punkty na dwa zbiory: lewe i prawe względem tej linii. Dla każdej ze stron znajdź punkt najdalej oddalony od tej linii – musi również leżeć na obwoluce – a rekurencyjnie wykonaj algorytm na dwóch mniejszych obszarach trójkątnych, które to utworzy, odrzucając każdy punkt, który znajduje się wewnątrz do tego stopnia wyznaczonego trójkąta, ponieważ punkt znajdujący się wewnątrz trójkąta zdefiniowanego przez znaną krawędź obwoluce nigdy nie może leżeć na samej obwoluce.

Średnia wydajność szybkiłasa wynosi O(n log n), a agresywne wczesne odrzucanie punktów wewnętrznych często sprawia, że jest on najszybszym z trzech algorytmów w praktyce na typowych, nieprzeciwnych danych – ale jak zwykły quicksort, jego najgorszy przypadek (starannie ułożona, przeciwnościowa dystrybucja punktów) pogarsza się do O(n²).

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Convex Hull i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.