Изменения

==Постановка задачи==

На плоскости лежит <tex>n</tex> отрезков, каждый из них задан координатами своих концов. Требуется по этим данным определить множество точек, в которых эти отрезки пересекаются. Однако, не всегда координаты точки можно абсолютно точно представить с помощью вещественных типов данных. Поэтому характеризовать каждую точку будем множеством отрезков, которые пересекаются в этой точке.

===Статус===

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

===В итоге===

Изначально у нас есть только события вида "начался отрезок" и "закончился отрезок". События вида "пересекаются два отрезка" будут добавляться нами в множество еще не обработанных событий. Соответственно, алгоритм выглядит так: выбираем то событие из множества необработанных, у которого наименьшая координата <tex>X</tex>, обрабатываем, делаем так, пока множество необработанных событий непустое. Плюс, на протяжении всего алгоритма должен поддерживаться следующий инвариант: в множество необработанных событий уже добавлены все пересечения отрезков, которые в текущем статусе текущие.

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

Слегка поменяем нашу концепцию. Сканирующая прямая теперь становится не совсем прямой. Теперь у нас появляется, скорее, сканирующая точка. Суть изменения в следующем: в случае, если несколько событий попадают на одну вертикальную прямую, мы их обрабатываем в порядке возрастания координаты по оси <tex>X</tex>. Внимательный читатель сейчас, наверное, воскликнет: "А как же тогда наш статус? Ведь отрезки не могут пересекать точку!". Однако и это не является проблемой. Если отрезок, который лежит в статусе, не вертикален, то он сортируется по своей координате <tex>Y</tex>, в которой он пересекается с вертикальной прямой, проведенной через нашу точку (да, это бывшая сканирующая прямая). А вот если отрезок вертикален, то его параметром является как раз ордината "сканирующей точки". <s>Если внимательно подумать, то все будет корректно.</s>Здесь должна быть анимашка, в которой показывается, что все будет корректно.