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

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

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

См. также Пересечение прямых

Примечания

Литература

Ссылки 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

Категория:Геометрические алгоритмы