Algorytm przesuwania linii: Rozwiązywanie problemów geometrycznych poprzez przesuwanie linii po płaszczyźnie

Kluczowe Idea: Przesuwająca się Linia i Aktywna Zbiór

Serce algorytmu przesuwania linii to piękna i prosta wizja mentalna: wyobraźnia pionowej linii przenoszącej się od lewej do prawej po płaszczyźnie zawierającej punkty, odcinki, prostokąty lub inne kształty. Zamiast badania, jak każdy obiekt interaguje z każdym innym obiektem, algorytm zajmuje się tylko tymi małym zbiorami obiektów, które obecnie dotyka linia przesuwająca się. Ten mały zestaw nazywany jest aktywnym zbiorem i stanowi całe tajemnice szybkości tego technikum. Podczas przemieszczania się linii, aktywny zbiór nie ulega ciągłemu zmianom; zmienia się tylko w określonych chwilach zwanych punktami wydarzeń, takimi jak miejsca rozpoczęcia odcinka, jego kończenia lub przecięcia dwóch odcinków. Miedzy wydarzeniami nic istotnego nie dzieje się, więc algorytm może skoczyć bezpośrednio z jednego wydarzenia do drugiego. Wydarzenia są obyczajowo przetwarzane w porządku od lewej do prawej za pomocą kolejki priorytetowej, podczas gdy sam aktywny zbiór jest utrzymywany w strukturze danych wspierającej szybkie dodawanie, usuwanie i pytania o sąsiadów, najczęściej drzewo binarne równoważne. Ta kombinacja — kolejka wydarzeń sterująca aktualizacjami aktywnego zbioru — stanowi szkielet podziemny prawie każdego algorytmu przesuwania linii, niezależnie od konkretnego problemu geometrycznego rozwiązujemy.

Klasyczny przykład: znalezienie wszystkich przecięć odcinków

Podstawowym demonstracją przetwarzania linii jest wykrywanie wszystkich przecięć między zestawem odcinków. Przy poruszaniu się linii przetwarzającej od lewej do prawej, ona utrzymuje w drzewie binarnym równoważnym odcinki, które obecnie przecinają ją, uporządkowane według ich pozycji w poziomie, czyli ich współrzędnej y na aktualnej lokalizacji linii przetwarzającej. Trzy rodzaje zdarzeń są istotne: lewy koniec odcinka, który go wprowadza do drzewa; prawy koniec odcinka, który go usuwa; i punkt przecięcia, w którym dwa odcinki wymieniają się miejscami w uporządkowaniu poziomym. Kluczowe zrozumienie polega na tym, że dwa odcinki mogą nowo przecinać się tylko jeśli były sąsiednimi w uporządkowaniu poziomym dokładnie przed momentem ich przecięcia. Odcinek leżący daleko wyżej od innego nie może nagle przecinać go bez najpierw stania się jego sąsiadem, ponieważ ścieżki przecinające muszą przechodzić przez każde uporządkowanie między nimi. To oznacza, że algorytm nigdy nie musi przetestować każdej pary odcinków na przecięcie. Musi sprawdzić tylko pary, które stają się sąsiednimi w drzewie, kiedy odcinek jest wprowadzony, usunięty lub wymienia się miejscami z jego sąsiadem. Każda taka sprawdzenie sąsiedztwa jest ekonomiczne, a cała liczba sprawdzeń pozostaje proporcjonalna do liczby odcinków plus liczby rzeczywistych przecięć znalezionych, co czyni cały proces zaskakująco efektywnym nawet na dużych, zamieszanych wejściach.

Dlaczego to przewyższa proste sprawdzanie par

Naiwnym podejściem do znalezienia przecięć odcinków jest porównywanie każdego odcinka z każdym innym, co prowadzi do czasu wykonania proporcjonalnego do kwadratu liczby odcinków n. Podwójne zwiększenie liczby wejść spowoduje około czterokrotny wzrost pracy; przy tysiącach odcinków to staje się ponięciośnie wolne. Zamiast tego podejście przekąsek osiąga czas wykonania proporcjonalny do n log n dla wielu praktycznych przypadków, z dodatkowym czasem proporcjonalnym do liczby rzeczywistych przecięć. Powodem tak dramatycznego poprawy jest to, że przekąska porównuje tylko lokalnie siedzące obiekty, a nie każdą możliwą parę. Zachowanie aktywnego zestawu w równoważnym drzewie poszukiwań kosztuje czas proporcjonalny do log n na każdą operację wstawienia, usunięcia lub zamiany siedzącego obok, a takich zdarzeń jest tylko rzędem n dla samych końców odcinków, plus jedno zdarzenie na każdy przecinek. Zamiast pytać n kwadrat niepotrzebnych pytań, jak te dwa odległe odcinki się przecinają, algorytm pyta o znacznie mniejszą liczbę istotnych pytań, które można szybko odpowiedzieć, dokładnie dlatego, że wykorzystuje geometryczny fakt, że odległe i nie siedzące obok odcinki nie mogą się przecinać bez najpierw stania się siedzącymi obok.

Inne klasyczne problemy rozwiązywane za pomocą przeskanowania linii

Intersekcja odcinków jest tylko najbardziej znanej zastosowaniu techniki; przeskanowanie linii pojawia się w całym spektrum geometrii obliczeniowej. Problem najbliższego parady punktów, czyli znalezienie dwóch punktów w zbiorze najbliższych sobie, można rozwiązać poprzez przeskanywanie linią przez uporządkowane punkty, jednocześnie utrzymując małą pionową strukturę z bliskimi kandydatami w aktywnym zbiorze, unikając pełnej porównania par. Obliczanie pola połączenia się nawiązujących prostokątów wykorzystuje przeskanowanie liniowe, które zatrzymuje się na każdym boku prostokąta, utrzymując strukturę, która śledzi, jakie pionowe interwały są obecnie pokryte, aby można było pomiar długości pokrywanej przy każdym wydarzeniu i pomnożyć ją przez poziomą odległość do następnego wydarzenia. Najbardziej eleganckim zastosowaniem jest algorytm Fortune do tworzenia diagramu Voronoi, który podzielić plane na regiony najbliższe każdemu ze zbioru wejściowych punktów. Algorytm Fortune przeskania linię poziomą przez plane, jednocześnie utrzymując tak zwany pas morski – łańcuch parabolicznych łuków reprezentujących granicę między punktami już przekroczonymi przez skanowanie a nieprzekroczoną obsługą, z nowymi łukami pojawiającymi się i starymi znikającymi w dokładnie określonych wydarzeniach.

Dlaczego ta technika generalnie działa tak dobrze

Technika przekątniowego skanowania nie jest ograniczona do kilku konkretnych problemów; to ogólny podejście, które powoduje sukces ze względu na głębokie strukturalne prawo dotyczące geometrii. Najbardziej użyteczne relacje geometryczne są lokalne, co oznacza, że zależą tylko od bliskich obiektów, a zmiany występują tylko w określonych, dyskretnych momentach, a nie ciągłe i niespodziewane. Sąsiedzi segmentu w porządku pionowym nie przemieszczają się przypadkowo; zamieniają się tylko podczas well-defined zdarzeń przecięć. Wnętrze prostokąta w zakresie pokrytej powierzchni nie ulega niespodziewanemu fluctuowaniu; zmienia się tylko na lewej i prawej krawędzi prostokąta. Granica regionu Voronoi nie przemieszcza się przypadkowo; reorganizuje się tylko podczas określonych zdarzeń parabolicznego charakteru. Ponieważ zmiany są ograniczone do dyskretnych zdarzeń, algorytm nigdy nie musi odzyskać całego obrazu ze scratcha podczas skanowania płaszczyzny. Musi tylko reagować na każde zdarzenie, gdy przychodzi, aktualizując mały zestaw aktywny i przekraczając do kolejnego. To dlaczego technika przekątniowego skanowania przenosi się tak łatwo od przecięcia segmentów do sumy obszarów prostokątów, przez diagramy Voronoi i wiele innych problemów: kiedy geometryczny problem może być zasymilowany jako ciąg lokalnych, dyskretnych zdarzeń przekraczających koordynat, technika przekątniowego skanowania jest prawdopodobnie w stanie zamienić wolne i ekspansywne podejście na szybkie i eleganckie.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz The Line Sweep Algorithm: Solving Geometry Problems by Sweeping a Line Across the Plane i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.