Изменения
→Доказательство корректности
== Доказательство корректности ==
То что алгоритм сообщает только точки пересечения отрезков очевидно. Покажем, что все точки пересечения будут найдены.
{{Лемма
|statement=Пусть <tex>p</tex> {{---}} точка пересечения нескольких отрезков, причем <tex>p</tex> не совпадает ни с одним из концов отрезков, участвующих в пересечении. Отсортируем отезки по углу вокруг <tex>p</tex> и пусть отрезки <tex>s_i</tex> и <tex>s_j</tex> окажутся соседними в сортировке. Тогда существует событие <tex>q</tex> с приоритетом выше, чем у <tex>p</tex>, такое что при обработке этого события <tex>s_i</tex> и <tex>s_j</tex> будут соседними в статусе.
||proof=Рассмотрим событие <tex>q</tex> которое будет обработано непосредственно перед <tex>p</tex>. Предположим, что при обработке этого события <tex>s_i</tex> и <tex>s_j</tex> не будут соседними в статусе. Это возможно только если между ними есть третий отрезок <tex>s</tex>. Но тогда или <tex>s</tex> пересекает какой-то из отрезков <tex>s_i, s_j</tex> в точке с приоритетом выше, чем у <tex>p</tex>, но ниже, чем у <tex>q</tex>; или <tex>s</tex> пересекает их оба в точке <tex>p</tex>, что противоречит тому, что они соседние в сортировке по углу. Следовательно при обработке <tex>q</tex> <tex>s_i</tex> и <tex>s_j</tex> будут соседними в статусе.
}}
{{Теорема
|statement=Алгоритм сообщает о всех точках пересечения
||proof=Воспользуемся индукцией по событиям, отсортированным в порядке, введённом выше (<tex>p < q \Leftrightarrow p_y < q_y \lor p_y = q_y \land p_x < q_x</tex> {{---}} точка пересечения). Пусть <tex>p</tex> {{---}} точка пересечения. Предположим что все события <tex>q, q < p</tex> были обработаны корректно. Тогда <tex>p</tex> будет обнаружена.
Действительно, если <tex>p</tex> {{---}} конец некоторого отрезка, то <tex>p</tex> добавлена в очередь событий в начале работы. Все содержащие её отрезки из статуса, который будет текущим при обработке <tex>p</tex> будут найдены. Для остальных отрезков, содержащих <tex>p</tex>, верно, что <tex>p</tex> {{---}} их верхний конец, и они будут найдены, т.к. мы храним их вместе с <tex>p</tex> в очереди.
Если же <tex>p</tex> не является концом ни одного из отрезков, то по лемме найдётся событие <tex>q</tex> с приоритетом выше, чем у <tex>p</tex>, такое что при обработке этого события пара отрезков, пересекающихся в <tex>p</tex> будут соседними в статусе. Следовательно в этом случае мы также обнаружим <tex>p</tex>.
}}
== Оценка времени работы ==
