Пересечение множества отрезков

Эта статья находится в разработке!

Пусть дано множество из [math]n[/math] отрезков и требуется найти все точки их пересечения. Очевидно, что задачу можно решить полным перебором за [math]O(n^2)[/math]; ясно также, что любой алгоритм будет в худшем случае работать за [math]\Theta(n^2)[/math] (нетрудно привести пример, когда количество пересечений квадратично, а алгоритм обязан сообщить о каждом пересечении). Однако существуют алгоритмы, которые оптимальнее, если количество точек пересечения отрезков невелико. Так алгоритм Бентли-Оттмана (англ. Bentley-Ottmann) позволяет решить задачу о пересечении отрезков, используя [math]O((n+I)\log{n})[/math] времени и [math]O(n)[/math] памяти, где [math]I[/math] — количество пересечений.

Формальная постановка задачи

Дано: [math]S[/math] — множество замкнутых отрезков на плоскости. Найти все точки их взаимного пересечения, охарактеризовав каждую точку пересечения множеством отрезков, которые участвуют в этом пересечении.

Описание алгоритма

В основу алгоритма положен метод заметающей прямой (sweep line), которая будет расположена горизонтально и двигаться вниз (в сторону уменьшения y-координаты). Нас будут интересовать события (events, event points) трёх типов:

• верхний конец отрезка,
• нижний конец отрезка,
• точка пересечения пары отрезков;

причем о событиях первых двух типов мы знаем заранее, а события, являющиеся пересечением отрезков, будут обнаружены и добавлены в множество необработанных событий динамически. Будем считать, что если у двух точек равные ординаты, то выше та, что лежит левее. Таким образом верхним концом горизонтального отрезка, в силу введенного порядка, является его левый конец. Это даст нам корректную обработку вырожденного случая, когда отрезок горизонтален. Можно представить, что заметающая прямая не горизонтальна, а повернута на малый угол против часовой стрелки, поэтому не существует такой конфигурации, что на ней лежит больше одного события (мы, для удобства, считаем точку пересечения трёх или более отрезков одним событием), а события с равными ординатами обрабатываются слева направо.

Нам потребуется две структуры данных.

Во-первых, мы будем хранить очередь событий [math]Q[/math] в виде сбалансированного бинарного дерева поиска, что позволит извлекать следующее событие и вставлять новое событие в очередь за [math]\log{m}[/math], где [math]m[/math] — количество элементов в очереди. Дерево будет отсортировано согласно порядку, введённому выше. Причём вместе с каждым событием мы будем хранить список отрезков, верхней точкой которых он является.

Во вторых, будем хранить статус [math]T[/math] заметающей прямой: множество отрезков, пересекающих заметающую прямую в данный момент времени, упорядоченных слева направо. От статуса нам потребуется оптимальные вставка и удаление отрезков, поэтому по-прежнему удобно воспользоваться бинарным деревом поиска.

Главная идея заключается в том, что мы будем тестировать пару отрезков на пересечение, если они являются соседними в статусе. Далее приведен псевдокод алгоритма, а ниже подробно расписана обработка события определенного типа.

findIntersections(S)
   Инициализировать Q и T
   for s in S
      вставить концы s в Q (вместе с верхним концом вставить сам s)
   while not Q.empty()
      p = Q.pop()
      handleEventPoint(p)

См. также

• Алгоритм Бентли-Оттмана

Источники

• Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars (2008), Computational Geometry: Algorithms and Applications (3rd edition), Springer-Verlag, ISBN 978-3-540-77973-5 Chapter 2: Line Segment Intersection: pp.20–29.