74
правки
Изменения
→Описание алгоритма
== Описание алгоритма ==
* верхний конец отрезка,
* нижний конец отрезка,
* точка пересечения пары отрезков;
причем о событиях первых двух типов мы знаем заранее, а события, являющиеся пересечением отрезков, будут обнаружены и добавлены в множество необработанных событий динамически. Будем считать, что если у двух точек равные ординаты, то выше та, что лежит левее. Таким образом верхним концом горизонтального отрезка, в силу введенного порядка, является его левый конец. Это даст нам корректную обработку вырожденного случая, когда отрезок горизонтален. [[Файл:Sweep_line_slight_rotation.png|200px|thumb|right|Приоритет событий]] Можно представить, что заметающая прямая не горизонтальна, а повернута на малый угол против часовой стрелки, поэтому не существует такой конфигурации, что на ней лежит больше одного события (мы, для удобства, считаем точку пересечения трёх или более отрезков одним событием), а события с равными ординатами обрабатываются слева направо.
Нам потребуется две структуры данных.
Во вторых, будем хранить статус <tex>T</tex> заметающей прямой: множество отрезков, пересекающих заметающую прямую в данный момент времени, упорядоченных слева направо. От статуса нам потребуется оптимальные вставка и удаление отрезков, поэтому по-прежнему удобно воспользоваться бинарным деревом поиска.
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: Status_structure.png|thumb|250px|center|Статус заметающей прямой]]
|[[Файл: Neighbour_segments.png|thumb|250px|center|Соседние отрезки в статусе]]
|
|}
Главная идея заключается в том, что мы будем проверять, пересекаются ли два отрезка, если они являются соседними в статусе. Это означает, что каждый отрезок мы будем проверять на пересечение с его левым и правым соседями в статусе. Далее, по ходу выполнения алгоритма, у отрезка могут измениться соседи; когда это происходит мы снова проверяем, не пересекает ли отрезок его новых соседей в статусе?
* Нижний конец отрезка. В этом случае мы удалим отрезок из статуса и проверим пару отрезков ставших соседними на пересечение. Как и в предыдущем случае, обнаруженные пересечения могут уже находиться в очереди.
{|border="0" cellpadding="5" width=30% align=center|[[Файл:Upper_and_intersection.png|thumb|250px|center|Обработка верхних концов и пересечений]]|[[Файл:Lower.png|thumb|250px|center|Обработка нижних концов]]||} Как было сказано выше, мы интерпретируем пересечение более двух отрезков в одной точке как одно событие. В этом случае обработка несколько сложнее (стоит пристально посмотреть пристально на псевдокод и рисунок {{---}} и убедиться, что алгоритм корректно обрабатывает такие события). Псевдокод функции обработки события:
handleEventPoint(p)
Q.insert(x) // должно работать корректно, если x уже есть в Q
== Доказательство корректности ==
