Изменения
→Описание алгоритма
Во вторых, будем хранить статус <tex>T</tex> заметающей прямой: множество отрезков, пересекающих заметающую прямую в данный момент времени, упорядоченных слева направо. От статуса нам потребуется оптимальные вставка и удаление отрезков, поэтому по-прежнему удобно воспользоваться бинарным деревом поиска.
Главная идея заключается в том, что мы будем тестировать пару отрезков на пересечениепроверять, пересекаются ли два отрезка, если они являются соседними в статусе. Это означает, что каждый отрезок мы будем проверять на пересечение с его левым и правым соседями в статусе. Далее, по ходу выполнения алгоритма, у отрезка могут измениться соседи; когда это происходит мы снова проверяем, не пересекает ли отрезок его новых соседей в статусе? Далее приведен псевдокод алгоритма, а ниже подробно расписана обработка события определенного типа.
findIntersections(S)
p = Q.pop()
handleEventPoint(p)
Рассмотрим обработку событий.
* Верхний конец отрезка. В этом случае мы вставим отрезок в статус и проверим, не пересекает ли он соседние отрезки в статусе. Нас будут интересовать только пересечения ниже заметающей прямой. Естественно, если пересечения будут обнаружены, то они должны быть вставлены в <tex>Q</tex>.
* Пересечение отрезков. Если событие {{---}} это точка пересечения двух отрезков, то эти отрезки меняют порядок и у каждого появляется, возможно, новый сосед. Мы проверим каждую пару новых соседей в статусе на пересечение. По-прежнему нас интересуют только пересечения ниже заметающей прямой. Отметим отдельно, что в этом случае найденные пересечения могли уже быть обнаружены ранее (когда пересекающиеся отрезки были соседними в статусе).
* Нижний конец отрезка. В этом случае мы удалим отрезок из статуса и проверим пару отрезков ставших соседними на пересечение. Как и в предыдущем случае, обнаруженные пересечения могут уже находиться в очереди.
Как было сказано выше, мы интерпретируем пересечение более двух отрезков в одной точке как одно событие. В этом случае обработка несколько сложнее (стоит посмотреть пристально на псевдокод и убедиться, что алгоритм корректно обрабатывает такие события). Псевдокод функции обработки события:
handleEventPoint(p)
U(p) = множество отрезков, верхний конец которых есть p // Напомним, что мы храним такие отрезки в Q вместе c p
// Далее найдём в T все отрезки, которые содержат p (они будут соседними в дереве)
L(p) = множество отрезков, нижний конец которых есть p
C(p) = множество отрезков, содержащих внутри себя p
'''if''' <tex> \vert L(p) \cup C(p) \cup U(p) \vert > 1</tex>
report(p, <tex>L(p) \cup C(p) \cup U(p)</tex>) // сообщить о p как о точки пересечения отрезков <tex>L(p) \cup C(p) \cup U(p)</tex>
T.remove(<tex>L(p) \cup C(p)</tex>)
T.insert(<tex>C(p) \cup U(p)</tex>)
// отрезки должны быть вставлены в порядке,
// в котором они пересекают горизонтальную линию,
// лежащую немного ниже заметающей прямой
// (при удалении-вставке отрезков из C(p) - те поменяют порядок на обратный
'''if''' <tex>C(p) \cup U(p) = \emptyset</tex>
s_l = левый сосед p в T
s_r = правый сосед p в T
findIntersection(s_l, s_r, p)
'''else'''
s1 = самый левый отрезок из <tex>C(p) \cup U(p)</tex> в T
s_l = левый сосед s1 в T
findIntersection(s_l, s1, p)
s2 = самый правый отрезок из <tex>C(p) \cup U(p)</tex> в T
s_r = правый сосед s2 в T
findIntersection(s2, s_r, p)
findIntersection(s_l, s_r, p)
'''if''' not intersects(s_l, s_r)
'''return'''
x = точка пересечения s_l и s_r
'''if''' x лежит ниже заметающей прямой или на ней справа от p
Q.insert(x) // должно работать корректно, если x уже есть в Q
== Доказательство корректности ==
