Algorytm Bentleya-Ottmanna

W geometrii obliczeniowej algorytm Bentleya-Ottmanna jest algorytmem linii wymiatania , służącym do wyświetlania wszystkich przecięć w zbiorze odcinków linii , tj. znajduje punkty przecięcia (lub po prostu przecięcia ) odcinków linii. Rozszerza algorytm Shamosa-Hoeya, podobny poprzedni algorytm do testowania, czy zestaw segmentów linii ma jakiekolwiek przecięcia. Dla danych wejściowych składających się z ${$ $\ Displaystyle {\ mathcal {O}}((n+k)\log n)}$ z $k$ (lub przecięciami) algorytm Bentleya-Ottmanna wymaga czasu . W przypadkach, w których ${\ Displaystyle k = {\ mathcal {o}} \ lewo ({\ Frac {n ^ {2}} {\ log n}} \ prawej)$ } jest ulepszeniem naiwnego algorytmu, który testuje każdą parę segmentów, co zajmuje ${\ Displaystyle \ Theta (n ^ {2})}$ .

Algorytm został początkowo opracowany przez Jona Bentleya i Thomasa Ottmanna ( 1979 ); jest to opisane bardziej szczegółowo w podręcznikach Preparata & Shamos (1985) , O'Rourke (1998) i de Berg et al. (2000) . Chociaż asymptotycznie szybsze algorytmy są obecnie znane przez Chazelle i Edelsbrunner (1992) i Balaban (1995) , algorytm Bentleya-Ottmanna pozostaje praktycznym wyborem ze względu na jego prostotę i niskie wymagania dotyczące pamięci ^{[ potrzebne źródło ]} .

Ogólna strategia

Główną ideą algorytmu Bentleya-Ottmanna jest zastosowanie metody przemiatania , w której pionowa linia L porusza się od lewej do prawej (lub np. od góry do dołu) w poprzek płaszczyzny, przecinając segmenty linii wejściowej w sekwencji przemieszcza. Algorytm najłatwiej opisać w pozycji ogólnej , czyli:

Żadne dwa punkty końcowe lub przecięcia segmentów linii nie mają tej samej współrzędnej x
Żaden punkt końcowy segmentu linii nie leży na innym segmencie linii
Żadne trzy odcinki linii nie przecinają się w jednym punkcie.

W takim przypadku L zawsze będzie przecinać odcinki linii wejściowej w zbiorze punktów, których pionowe uporządkowanie zmienia się tylko przy skończonym zbiorze dyskretnych zdarzeń . W szczególności zdarzenie dyskretne może być powiązane z punktem końcowym (lewym lub prawym) odcinka linii lub punktem przecięcia dwóch odcinków linii. W ten sposób ciągły ruch L można podzielić na skończoną sekwencję kroków i symulować za pomocą algorytmu działającego w skończonym czasie.

W trakcie tej symulacji mogą wystąpić dwa rodzaje zdarzeń. Kiedy L przechodzi przez punkt końcowy segmentu linii s , przecięcie L z s jest dodawane lub usuwane z uporządkowanego pionowo zestawu punktów przecięcia. Zdarzenia te są łatwe do przewidzenia, ponieważ punkty końcowe są znane już z danych wejściowych do algorytmu. Pozostałe zdarzenia występują, gdy L przechodzi przez skrzyżowanie (lub przecięcie) dwóch odcinków s i t . Zdarzenia te można również przewidzieć na podstawie faktu, że tuż przed zdarzeniem punkty przecięcia L z s i t sąsiadują ze sobą w pionowej kolejności punktów przecięcia ^{[ wymagane wyjaśnienie ]} .

Algorytm Bentleya-Ottmanna sam utrzymuje struktury danych reprezentujące bieżące pionowe uporządkowanie punktów przecięcia linii przeciągnięcia z wejściowymi segmentami linii oraz zbiór potencjalnych przyszłych zdarzeń utworzonych przez sąsiednie pary punktów przecięcia. Przetwarza każde zdarzenie po kolei, aktualizując swoje struktury danych, aby reprezentowały nowy zestaw punktów przecięcia.

Struktury danych

Aby skutecznie utrzymać punkty przecięcia linii przemiatania L z wejściowymi segmentami linii i sekwencją przyszłych zdarzeń, algorytm Bentleya-Ottmanna utrzymuje dwie struktury danych :

Drzewo wyszukiwania binarnego („drzewo stanu linii przemiatania”), zawierające zestaw segmentów linii wejściowych przecinających L , uporządkowanych według współrzędnych y punktów, w których te segmenty przecinają L . Same punkty przecięcia nie są jawnie reprezentowane w drzewie wyszukiwania binarnego. Algorytm Bentleya- Ottmanna wstawi nowy segment s do tej struktury danych, gdy linia przeciągnięcia L przetnie lewy punkt końcowy p tego segmentu ( tj . po lewej stronie, jak wyjaśniono powyżej w tym artykule). Właściwą pozycję segmentu s w drzewie wyszukiwania binarnego można określić za pomocą wyszukiwania binarnego, którego każdy krok sprawdza, czy p znajduje się powyżej lub poniżej innego segmentu przecinanego przez L . Zatem wstawienie może być wykonane w czasie logarytmicznym. Algorytm Bentleya-Ottmanna usunie również segmenty z drzewa wyszukiwania binarnego i użyje drzewa wyszukiwania binarnego do określenia segmentów, które znajdują się bezpośrednio nad lub pod innymi segmentami; operacje te mogą być wykonywane wyłącznie przy użyciu samej struktury drzewa bez odniesienia do podstawowej geometrii segmentów.

Kolejka priorytetowa („kolejka zdarzeń”) używana do utrzymywania sekwencji potencjalnych przyszłych zdarzeń w algorytmie Bentleya – Ottmanna. Każde zdarzenie jest powiązane z punktem p na płaszczyźnie, albo punktem końcowym segmentu, albo punktem przecięcia, a zdarzenie ma miejsce, gdy linia L przechodzi przez p . W ten sposób zdarzeniom można nadać priorytet według x punktów powiązanych z każdym zdarzeniem. W algorytmie Bentleya-Ottmanna potencjalne przyszłe zdarzenia składają się z punktów końcowych odcinków linii, które nie zostały jeszcze przesunięte, oraz punktów przecięcia par linii zawierających pary odcinków, które znajdują się bezpośrednio nad lub pod sobą.

Algorytm nie musi jawnie zachowywać reprezentacji linii przeciągnięcia L lub jej położenia na płaszczyźnie. Pozycja L jest raczej reprezentowana pośrednio: jest to pionowa linia przechodząca przez punkt powiązany z ostatnio przetworzonym zdarzeniem.

Drzewo wyszukiwania binarnego może być dowolną zrównoważoną strukturą danych drzewa wyszukiwania binarnego , taką jak drzewo czerwono-czarne ; wystarczy, że wstawianie, usuwanie i wyszukiwanie zajmuje czas logarytmiczny. Podobnie kolejka priorytetowa może być stertą binarną lub dowolną inną kolejką priorytetową w czasie logarytmicznym; bardziej wyrafinowane kolejki priorytetowe, takie jak stos Fibonacciego, nie są konieczne. Należy zauważyć, że złożoność przestrzenna kolejki priorytetowej zależy od struktury danych użytej do jej implementacji.

Szczegółowy algorytm

Algorytm Bentleya-Ottmanna wykonuje następujące kroki.

Zainicjuj kolejkę priorytetową Q potencjalnych przyszłych zdarzeń, z których każde jest powiązane z punktem na płaszczyźnie i ma priorytet według współrzędnej x punktu. Tak więc początkowo Q zawiera zdarzenie dla każdego z punktów końcowych segmentów wejściowych.
Zainicjuj samobalansujące drzewo wyszukiwania binarnego T segmentów linii, które przecinają linię przemiatania L , uporządkowaną według współrzędnych y punktów przecięcia. Początkowo T jest puste. (Nawet jeśli przeciągnięcie linii L nie jest wyraźnie przedstawione, pomocne może być wyobrażenie go jako linii pionowej, która początkowo znajduje się po lewej stronie wszystkich segmentów wejściowych).
Gdy Q jest niepuste, znajdź i usuń zdarzenie z Q związane z punktem p o minimalnej współrzędnej x . Określ typ zdarzenia i przetwórz je zgodnie z następującą analizą przypadku:
- Jeśli p jest lewym końcem odcinka s , wstaw s do T . Znajdź odcinki linii r i t , które znajdują się odpowiednio bezpośrednio nad i pod s w T (jeśli istnieją); jeśli skrzyżowanie r i t (sąsiadów s w strukturze danych statusu) tworzy potencjalne przyszłe zdarzenie w kolejce zdarzeń, usuń to możliwe przyszłe zdarzenie z kolejki zdarzeń. Jeśli s przecina r lub t , dodaj te punkty przecięcia jako potencjalne przyszłe zdarzenia w kolejce zdarzeń.
- Jeśli p jest prawym końcem odcinka s , usuń s z T . Znajdź segmenty r i t , które (przed usunięciem s ) znajdowały się odpowiednio bezpośrednio nad i pod nim w T (jeśli istnieją). Jeśli r i t przecinają się, dodaj ten punkt przecięcia jako potencjalne przyszłe zdarzenie w kolejce zdarzeń.
- Jeśli p jest punktem przecięcia dwóch segmentów s i t (z s poniżej t na lewo od skrzyżowania), zamień miejscami s i t w T . Po zamianie znajdź segmenty r i u (jeśli istnieją), które znajdują się odpowiednio poniżej i powyżej t i s . Usuń wszystkie punkty przecięcia rs (tj. punkt przecięcia między r i s ) i tu (tj. punkt przecięcia między t i u ) z kolejki zdarzeń, a jeśli r i t przecinają się lub s i u przecinają się, dodaj te punkty przecięcia do kolejka zdarzeń.

Analiza

$.$ zdarzenie na punkt końcowy segmentu lub punkt przecięcia, w posortowanej kolejności współrzędnych tych punktów, co można udowodnić przez indukcję Wynika to z faktu, że po przetworzeniu zdarzenia, następne zdarzenie (jeśli jest to punkt przecięcia) musi być skrzyżowaniem dwóch sąsiednich segmentów w kolejności segmentów reprezentowanych przez T { $i$ $} displaystyle T}$ oraz ponieważ algorytm zachowuje wszystkie przejścia między sąsiednimi segmentami jako potencjalne przyszłe zdarzenia w kolejce zdarzeń; dlatego poprawne następne zdarzenie będzie zawsze obecne w kolejce zdarzeń. Dzięki temu poprawnie wyszukuje wszystkie przecięcia odcinków linii wejściowych, do rozwiązania którego został stworzony.

$. Każde zdarzenie jest przetwarzane przez stałą liczbę operacji w drzewie wyszukiwania binarnego i kolejce zdarzeń, a (ponieważ zawiera tylko punkty$ $Ottmanna$ przetwarza sekwencję zdarzeń , gdzie oznacza liczbę segmentów linii $wejściowej$ końcowe segmentów i skrzyżowania między sąsiednimi segmentami) kolejka zdarzeń nigdy nie zawiera więcej $zdarzeń$ Wszystkie operacje wymagają czasu ${\ Displaystyle {\ mathcal {O}} (\ log n)}$ . Stąd całkowity czas algorytmu wynosi ${\ Displaystyle {\ mathcal {O}} ((n + k) \ log n)}$ .

Jeśli skrzyżowania znalezione przez algorytm nie muszą być przechowywane po ich znalezieniu, przestrzeń używana przez algorytm w dowolnym momencie wynosi ${\ Displaystyle {\ mathcal {O}} (n)}: O ( n ) {\ Displaystyle {\ mathcal {O}} (n)$ } każdy z segmentów linii $wejściowej odpowiada co najwyżej$ $jednemu$ węzłowi drzewa wyszukiwania binarnego i jak stwierdzono powyżej, kolejka zdarzeń zawiera co . To ograniczenie przestrzenne jest spowodowane przez Browna (1981) ; oryginalna wersja algorytmu była nieco inna (nie usuwała zdarzeń przecinających się z, $gdy$ jakieś inne zdarzenie powoduje, że dwa przecinające się segmenty nie przylegają do siebie), co powoduje, że zajmuje więcej miejsca

Chen & Chan (2003) opisali wysoce wydajną przestrzennie wersję algorytmu Bentleya – Ottmanna, która koduje większość informacji w kolejności segmentów w tablicy reprezentującej dane wejściowe, wymagając jedynie ${\ Displaystyle {\mathcal {O}}(\log ^{2}n)}$ dodatkowe komórki pamięci. Aby jednak uzyskać dostęp do zakodowanych informacji, algorytm jest spowalniany o czynnik logarytmiczny.

Specjalna pozycja

Powyższy opis algorytmu zakłada, że odcinki linii nie są pionowe, że punkty końcowe odcinków linii nie leżą na innych odcinkach linii, że przecięcia są utworzone tylko przez dwa odcinki linii oraz że żadne dwa punkty zdarzeń nie mają tej samej współrzędnej x . Innymi słowy, nie uwzględnia przypadków narożnych, tj. przyjmuje ogólne położenie punktów końcowych segmentów wejściowych. Jednak te ogólne założenia dotyczące położenia nie są uzasadnione w przypadku większości zastosowań przecięcia odcinków linii. Bentley i Ottmann (1979) zasugerowali lekkie zakłócenie danych wejściowych, aby uniknąć tego rodzaju liczbowych zbiegów okoliczności, ale nie opisali szczegółowo, jak wykonać te zakłócenia. de Berga i in. (2000) opisują bardziej szczegółowo następujące środki postępowania z danymi wejściowymi pozycji specjalnych:

Rozwiąż powiązania między punktami zdarzeń o tej samej współrzędnej x , używając współrzędnej y . Zdarzenia o różnych y są obsługiwane jak poprzednio. Ta modyfikacja rozwiązuje zarówno problem wielu punktów zdarzeń o tej samej x , jak i problem segmentów linii pionowych: lewy punkt końcowy segmentu pionowego jest definiowany jako punkt o niższej współrzędnej y , a kroki potrzebne do przetwarzania takiego segmentu są zasadniczo takie same, jak te potrzebne do przetwarzania niepionowego segmentu o bardzo dużym nachyleniu.
Zdefiniuj segment linii jako zbiór domknięty zawierający jego punkty końcowe. W związku z tym dwa segmenty linii, które mają wspólny punkt końcowy, lub segment linii, który zawiera punkt końcowy innego segmentu, są liczone jako przecięcie dwóch segmentów linii.
Gdy wiele segmentów linii przecina się w tym samym punkcie, utwórz i przetwórz pojedynczy punkt zdarzenia dla tego przecięcia. Aktualizacje drzewa wyszukiwania binarnego spowodowane tym zdarzeniem mogą polegać na usunięciu wszystkich odcinków linii, dla których jest to prawy punkt końcowy, wstawieniu nowych odcinków linii, dla których jest to lewy punkt końcowy, oraz odwróceniu kolejności pozostałych odcinków linii zawierających ten punkt zdarzenia . Wyjście z wersji algorytmu opisanej przez de Berg et al. (2000) składa się z zestawu punktów przecięcia odcinków linii, oznaczonych segmentami, do których należą, a nie ze zbioru par odcinków linii, które się przecinają.

Podobne podejście do degeneracji zastosowano w implementacji LEDA algorytmu Bentleya-Ottmanna.

Kwestie precyzji numerycznej

Dla poprawności algorytmu konieczne jest wyznaczenie bez aproksymacji relacji góra-dół między punktem końcowym odcinka linii a innymi odcinkami linii oraz prawidłowe uszeregowanie różnych punktów zdarzeń. Z tego powodu standardem jest używanie współrzędnych całkowitych dla punktów końcowych segmentów linii wejściowych i dokładne przedstawianie współrzędnych liczb wymiernych punktów przecięcia dwóch segmentów za pomocą arytmetyki o dowolnej precyzji . Jednak może być możliwe przyspieszenie obliczeń i porównań tych współrzędnych, stosując zmiennoprzecinkowe i sprawdzając, czy obliczone w ten sposób wartości są wystarczająco dalekie od zera, aby można było z nich korzystać bez możliwości popełnienia błędu. Dokładne obliczenia arytmetyczne wymagane przez naiwną implementację algorytmu Bentleya-Ottmanna mogą wymagać pięciokrotnie większej liczby bitów precyzji niż współrzędne wejściowe, ale Boissonat i Preparata (2000) opisują modyfikacje algorytmu, które zmniejszają wymaganą dokładność do dwukrotności liczbę bitów jako współrzędne wejściowe.

Szybsze algorytmy

O ( n log n ) ograniczenia czasowego dla algorytmu Bentleya – Ottmanna jest konieczna, ponieważ istnieją pasujące dolne granice dla problemu wykrywania przecinających się segmentów linii w algebraicznych modelach drzew decyzyjnych obliczeń. Można jednak poprawić zależność od k , liczby skrzyżowań. Clarkson (1988) i Mulmuley (1988) dostarczyli losowych algorytmów konstruowania grafu planarnego , którego wierzchołki są punktami końcowymi i przecięciami odcinków linii, a krawędziami są części odcinków łączących te wierzchołki, w oczekiwanym czasie O( n log n + k ), a ten problem konstrukcji układu został rozwiązany deterministycznie w tym samym czasie O ( n log n + k ) ograniczonym przez Chazelle i Edelsbrunner (1992) . Jednak zbudowanie tego układu jako całości wymaga przestrzeni O ( n + k ), większej niż granica przestrzeni O ( n ) algorytmu Bentleya – Ottmanna; Balaban (1995) opisał inny algorytm, który wymienia wszystkie przecięcia w czasie O( n log n + k ) i przestrzeni O( n ).

Jeżeli segmenty linii wejściowych i ich punkty końcowe tworzą krawędzie i wierzchołki połączonego wykresu (ewentualnie z przecięciami), część czasu O ( n log n ) związana z algorytmem Bentleya – Ottmanna również może zostać zmniejszona. Jak pokazują Clarkson, Cole i Tarjan (1992) , w tym przypadku istnieje losowy algorytm rozwiązania problemu w oczekiwanym czasie O( n log* n + k ), gdzie log * oznacza logarytm iterowany , funkcję znacznie wolniej rosnącą niż logarytm. Ściśle spokrewniony losowy algorytm Eppsteina, Goodricha i Strasha (2009) rozwiązuje ten sam problem w czasie O( n + k log ^{( i )} n ) dla dowolnej stałej i , gdzie log ^{( i )} oznacza funkcję uzyskaną przez iterację funkcji logarytmicznej ja razy. Pierwszy z tych algorytmów przyjmuje czas liniowy, gdy k jest większe od n o współczynnik log ^{( i )} n dla dowolnej stałej i , podczas gdy drugi algorytm przyjmuje czas liniowy, gdy k jest mniejsze od n o współczynnik log ^{( i )} n . Oba te algorytmy obejmują zastosowanie algorytmu Bentleya-Ottmanna do małych losowych próbek danych wejściowych.

Notatki

Balaban, IJ (1995), „Optymalny algorytm znajdowania przecięć segmentów”, Proc. 11. Symp. ACM. Geometria obliczeniowa , s. 211–219, doi : 10.1145/220279.220302 , S2CID 6342118 .
Bartuschka, U.; Mehlhorn, K .; Näher, S. (1997), „Solidna i wydajna implementacja algorytmu linii przemiatania dla problemu przecięcia segmentu linii prostej” , w: Italiano, GF ; Orlando, S. (red.), Proc. praca. Algorithm Engineering , zarchiwizowane od oryginału w dniu 6.06.2017 , pobrane 27.05.2009 .
Bentley, JL ; Ottmann, TA (1979), „Algorytmy raportowania i liczenia przecięć geometrycznych”, IEEE Transactions on Computers , C-28 (9): 643–647, doi : 10.1109/TC.1979.1675432 , S2CID 1618521 .
de Berg, Marek; van Kreveld, Marc; Overmars, Marek ; Schwarzkopf, Otfried (2000), „Rozdział 2: Przecięcie odcinka linii” , Computational Geometry (wyd. 2), Springer-Verlag, s. 19–44 , ISBN 978-3-540-65620-3 .
Boissonat, J.-D.; Preparata, FP (2000), „Solidne przeciągnięcie płaszczyzny dla przecinających się segmentów” (PDF) , SIAM Journal on Computing , 29 (5): 1401–1421, doi : 10.1137 / S0097539797329373 .
Brown, KQ (1981), „Komentarze dotyczące„ Algorytmów raportowania i liczenia przecięć geometrycznych ” , IEEE Transactions on Computers , C-30 (2): 147, doi : 10.1109/tc.1981.6312179 , S2CID 206622367 .
Chazelle, Bernard ; Edelsbrunner, Herbert (1992), „Optymalny algorytm przecinania odcinków linii w płaszczyźnie”, Journal of the ACM , 39 (1): 1–54, doi : 10.1145/147508.147511 , S2CID 785741 .
Chen, EY; Chan, TM (2003), „Wydajny przestrzennie algorytm przecięcia segmentów”, Proc. 15. kanadyjska konferencja na temat geometrii obliczeniowej (PDF) .
Clarkson, KL (1988), „Zastosowania losowego próbkowania w geometrii obliczeniowej, II”, Proc. 4. Symp. ACM. Geometria obliczeniowa , s. 1–11, doi : 10.1145/73393.73394 , S2CID 15134654 .
Clarkson, KL ; Cole, R.; Tarjan, RE (1992), „Randomizowane algorytmy równoległe dla diagramów trapezowych”, International Journal of Computational Geometry and Applications , 2 (2): 117–133, doi : 10.1142 / S0218195992000081 . Sprostowanie, 2 (3): 341–343.
Eppstein, D .; Goodrich, M .; Strash, D. (2009), „Algorytmy czasu liniowego dla grafów geometrycznych z podliniowo wieloma przecięciami”, Proc. XX ACM-SIAM Symp. Dyskretne algorytmy (SODA 2009) , s. 150–159, arXiv : 0812.0893 , Bibcode : 2008arXiv0812.0893E , doi : 10.1137/090759112 , S2CID 13044724 .
Mulmuley, K. (1988), „Szybki algorytm partycji planarnej, I”, Proc. 29. symp. IEEE Podstawy informatyki (FOCS 1988) , s. 580–589, doi : 10.1109/SFCS.1988.21974 , S2CID 34582594 .
O'Rourke, J. (1998), „Sekcja 7.7: Przecięcie segmentów”, Computational Geometry in C (wyd. 2), Cambridge University Press, s. 263–265, ISBN 978-0-521-64976-6 .
Preparata, FP ; Shamos, MI (1985), „Sekcja 7.2.3: Przecięcie odcinków linii”, Geometria obliczeniowa: wprowadzenie , Springer-Verlag, s. 278–287, Bibcode : 1985cgai.book.....P .
Pach, J .; Sharir, M. (1991), „O pionowej widoczności w układach segmentów i wielkości kolejki w algorytmie zamiatania linii Bentleya – Ottmanna”, SIAM Journal on Computing , 20 (3): 460–470, doi : 10.1137/0220029 , MR 1094525 .
Shamos, MI ; Hoey, Dan (1976), „Problemy przecięcia geometrycznego”, 17. konferencja IEEE. Podstawy informatyki (FOCS 1976) , s. 208–215, doi : 10.1109/SFCS.1976.16 , S2CID 124804 .

Linki zewnętrzne

Smid, Michiel (2003), Obliczanie przecięć w zbiorze odcinków linii: algorytm Bentleya – Ottmanna (PDF) .