2015-06-28
973
Лабораторная работа №4 5.10.2012
Метод заметающей прямой
Метод заметающей прямой (метод выметания) является одним из основных методов вычислительной геометрии.
Постановка задачи
Дано множество отрезков, причем никакие три из них не походят через одну точку. Проверить, есть ли среди заданных отрезков хотя бы два пересекающихся.
Идея метода состоит в переходе от двумерного пространства к произведению (одномерное) пространство-время. После этого отрезки становятся точками, движущимися по прямой, и их можно упорядочивать.
Замечание. Для простоты будем предполагать, что среди рассматриваемых отрезков нет вертикальных и что никакие три отрезка не проходят через одну точку.
Введем отношение порядка на отрезках. Будем говорить, что два отрезка сравнимы относительно x, если вертикальная прямая с абсциссой x пересекает оба отрезка. При этом s 1 выше s 2, если точка пересечения s 1 с вертикальной прямой выше точки пересечения s 2 с этой же прямой.
В точке пересечения отрезков отношение порядка между ними меняется на противоположное. По предположению никакие три отрезка не проходят через одну точку, поэтому в окрестности точки пересечения пересекающиеся отрезки непосредственно следуют друг за другом (в смысле введенного на них порядка).
