Изменения

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

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

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

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