Изменения

В основу алгоритма положен метод [[Файл:Status_line.png|200px|thumb|right|Заметающая прямая и события]] Воспользуемся методом заметающей прямой (sweep line), которая будет расположена расположенной горизонтально и двигаться двигающейся вниз (в сторону уменьшения y-координаты). Нас будут интересовать события (events, event points) трёх типов:

причем о событиях первых двух типов мы знаем заранее, а события, являющиеся пересечением отрезков, будут обнаружены и добавлены в множество необработанных событий динамически. Будем считать, что если у двух точек равные ординаты, то выше та, что лежит левее. Таким образом верхним концом горизонтального отрезка, в силу введенного порядка, является его левый конец. Это даст нам корректную обработку вырожденного случая, когда отрезок горизонтален.  [[Файл:Sweep_line_slight_rotation.png|200px|thumb|right|Приоритет событий]] Можно представить, что заметающая прямая не горизонтальна, а повернута на малый угол против часовой стрелки, поэтому не существует такой конфигурации, что на ней лежит больше одного события (мы, для удобства, считаем точку пересечения трёх или более отрезков одним событием), а события с равными ординатами обрабатываются слева направо.

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

{|border="0" cellpadding="5" width=30% align=center|[[Файл:Upper_and_intersection.png|thumb|250px|center|Обработка верхних концов и пересечений]]|[[Файл:Lower.png|thumb|250px|center|Обработка нижних концов]]||} Как было сказано выше, мы интерпретируем пересечение более двух отрезков в одной точке как одно событие. В этом случае обработка несколько сложнее (стоит пристально посмотреть пристально на псевдокод и рисунок {{---}} и убедиться, что алгоритм корректно обрабатывает такие события). Псевдокод функции обработки события:

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)

Описанный алгоритм обрабатывает корректно горизонтальные отрезки и точки пересечения трёх и более отрезков, но не справляется с перекрывающимися отрезками. Об этом вскользь упомянуто здесь: {|border="0" cellpadding="5" width=30% align=center|[[Алгоритм Бентли-ОттманаФайл:Mantaining_status.png|thumb|450px|center|Поддержание статуса при обработке события]].||}

||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>O(n)</tex> памяти, однако очередь событий может занимать <tex>O(n + I)</tex> памяти. Если модифицировать алгоритм так, что в очереди будут храниться только точки пересечения торезковотрезков, соседних в статусе, то объём используемой памяти сократиться сократится до <tex>O(n)</tex>. Для этого нужно удалять точки пересечения отрезков, которые перестали быть соседними. Перед тем, как мы дойдём до точки удаленной точки, обязательно найдется найдётся соседняя в статусе пара отрезков, которая пересекается которые пересекаются в этой точке, и она снова будет вставлена в очередь. Ясно, что такая оптимизация не влияет на время работы алгоритма. == См. также ==* [[Алгоритм Бентли-Оттмана]]