Задача о пересечении отрезков

Задача о пересечении отрезков заключается в определении, пересекаются ли какие-либо два отрезка из заданного списка на плоскости.

Простые алгоритмы проверяют каждую пару отрезков. Однако если нужно проверить большое число отрезков на пересечение, задача становится возрастающе неэффективной, поскольку большинство пар отрезков при обычном вводе не лежат близко друг от друга. Наиболее общий и более эффективный путь решения этой задачи для большого числа отрезков заключается в использовании алгоритма заметающей прямой, в котором мы воображаем себе прямую, проходящую через отрезки, и отслеживаем пересечения отрезков с помощью структуры данных, основанной на двоичных деревьях поиска. Алгоритм Шамоса — Хауи применяет этот принцип для решения задачи нахождения пересечения отрезков, как описано выше. Алгоритм Бентли — Оттманна работает по тому же принципу и находит список всех пересечений за логарифмическое время на одно пересечение.

См. также

• Пересечение прямых

Литература

• Shamos M. I., Hoey D. 17th Annual Symposium on Foundations of Computer Science (sfcs 1976). — 1976. — doi:10.1109/SFCS.1976.16.
• Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Chapter 2: Line Segment Intersection // Computational Geometry. — 2nd. — Springer, 2000. — С. 19—44. — ISBN 3-540-65620-0.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Section 33.2: Determining whether any pair of segments intersects // Introduction to Algorithms. — Second Edition. — MIT Press and McGraw-Hill, 1990. — С. 934—947. — ISBN 0-262-03293-7.
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, 3-е издание = Introduction to Algorithms, Third Edition. — М.: «Вильямс», 2013. — 1328 с. — ISBN 978-5-8459-1794-2.
• Bentley J. L., Ottmann T. Algorithms for reporting and counting geometric intersections // IEEE Trans. Comput. — 1979. — Вып. C28. — С. 643–647.

Ссылки

• Intersections of Lines and Planes Algorithms and sample code by Dan Sunday
• Robert Pless. Lecture 4 notes. Washington University in St. Louis, CS 506: Computational Geometry.
• Line segment intersection in CGAL, the Computational Geometry Algorithms Library
• «Line Segment Intersection» lecture notes by Jeff Erickson.
• Line-Line Intersection Method With C Code Sample Darel Rex Finley