Изменения

Назовем статусом структуру данныхмножество, в которой содержатся все отрезки, пересекающие нашу сканирующую прямую. Важно, что эти отрезки должны быть упорядочены по возрастанию (или убыванию) координаты их пересечения с прямой. Заметим, что в процессе работы алгоритма отрезки могут добавляться в произвольные места этой этого упорядоченной структурымножества, удаляться из произвольных мест или меняться местами друг с другом. Соответственно, нам идеально подходит структура данных дерево поиска, но это уже совсем другая история.

Попробуем найти событие, которое случится раньше всех других, если наша прямая уже пересекает какие-то отрезки. Нам, в данный момент, интересен случай, когда это событие является пересечением отрезков. Важно, что в этом пересечении участвуют два отрезка, которые обязательно являются соседними в нашем статусе. ====Доказательство====Предположим, что это не так. Значит, между этими двумя пересекающимися отрезками существует еще хотя бы один. Поскольку эти два отрезка пересекаются, то или третий пересекает перед их пересечением один из них, или пересекается с ними в той же точке. В любом случае, Важная мысль верна ===В итоге===Изначально у нас есть только события вида "начался отрезок" и "закончился отрезок". События вида "пересекаются два отрезка" будут добавляться нами в множество еще не обработанных событий. Соответственно, алгоритм выглядит так: выбираем то событие из множества необработанных, у которого наименьшая координата <tex>X</tex>, обрабатываем, делаем так, пока множество необработанных событий непустое. Плюс, на протяжении всего алгоритма должен поддерживаться следующий инвариант: в множество необработанных событий уже добавлены все пересечения отрезков, которые в текущем статусе текущие. ===Обработка событий=======Событие "начало отрезка"====Находим в статусе два отрезка, между которыми будет находится тот, который начинается. После этого добавляем его в статус на это место и точки его пересечения с соседними добавляем в множество необработанных событий. ====Событие "конец отрезка"====Находим в статусе отрезок, который заканчивается. Удаляем его оттуда, после чего в множество необработанных событий добавляем точку, в которой пересекаются отрезки, которые были соседями заканчивающегося в старом статусе. Это необходимо, потому что в новом статусе они станут соседними. Заметим, что добавляемое событие может уже находиться в множестве, но нас это совершенно не напрягает. ====Событие "пересечение отрезков"====Находим в статусе два отрезка, которые пересекаются. Меняем их местами (это действительно происходит). После этого добавляем в множество пересечения двух новых пар соседей, которые появились после перестановки пересекшихся отрезков.