Przecięcie wielu segmentów linii

W przypadku dwóch segmentów zobacz sekcję Przecięcie segmentu linii . Aby uzyskać informacje o nieskończonych liniach, zobacz Przecięcie linii z liniami .

W geometrii obliczeniowej problem przecięcia wielu odcinków linii dostarcza listę odcinków linii na płaszczyźnie euklidesowej i pyta, czy dowolne dwa z nich przecinają się (przecinają).

Proste algorytmy badają każdą parę segmentów. Jednakże, jeśli ma być sprawdzona duża liczba potencjalnie przecinających się segmentów, staje się to coraz bardziej nieefektywne, ponieważ większość par segmentów nie znajduje się blisko siebie w typowej sekwencji wejściowej. Najbardziej powszechnym i skuteczniejszym sposobem rozwiązania tego problemu dla dużej liczby segmentów jest użycie algorytmu linii wymiatania , w którym wyobrażamy sobie linię przesuwającą się po segmentach linii i śledzimy, które segmenty linii przecina w każdym punkcie czasu z wykorzystaniem dynamicznej struktury danych opartej na binarnych drzewach wyszukiwania . Algorytm Shamosa – Hoeya stosuje tę zasadę do rozwiązania problemu wykrywania przecięć odcinków linii, jak stwierdzono powyżej, polegającego na określeniu, czy zbiór odcinków linii ma przecięcie; algorytm Bentleya-Ottmanna działa na tej samej zasadzie, aby wyświetlić listę wszystkich skrzyżowań w czasie logarytmicznym na skrzyżowanie.

Zobacz też

• Algorytm Bentleya-Ottmanna

Dalsza lektura

•   Marka de Berga; Marca van Krevelda; Marka Overmarsa; i Otfrieda Schwarzkopfa (2000). Geometria obliczeniowa (wyd. 2). Skoczek. ISBN 3-540-65620-0 . Rozdział 2: Przecięcie odcinka linii, s. 19–44.
•   Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest i Clifford Stein . Wprowadzenie do algorytmów , wydanie drugie. MIT Press i McGraw-Hill, 1990. ISBN 0-262-03293-7 . Sekcja 33.2: Określanie, czy jakakolwiek para odcinków się przecina, s. 934–947.
• JL Bentley i T. Ottmann., Algorytmy raportowania i liczenia przecięć geometrycznych, IEEE Trans. Oblicz. C28 (1979), 643–647.

Linki zewnętrzne

• Przecięcia linii i płaszczyzn Algorytmy i przykładowy kod autorstwa Dana Sundaya
• Robert Pless. Wykład 4 notatki . Washington University w St. Louis , CS 506: Computational Geometry ( kopia w pamięci podręcznej ).
• Przecięcie segmentu linii w CGAL , bibliotece algorytmów geometrii obliczeniowej
• „Line Segment Intersection” autorstwa Jeffa Ericksona.
• Metoda przecięcia linia-linia z próbką kodu C Darel Rex Finley