228
правок
Изменения
Нет описания правки
(Решение: молиться, или просто обрабатывать вручную.)
==Алгоритм==
Мы рассматриваем алгоритм построения карты и алгоритм запроса.
===Алгоритм построения карты===
Во время построения трапецоидной карты(в дальнейшем <tex> T</tex>) алгоритм так же строит структуру для поиска (в дальнейшем <tex> D</tex>).
Так как трапецоидная карта - геометрическая структура, а основные операции ведутся именно с поисковой, упор на неё.
Наш алгоритм добавляет отрезки по одному и после каждого добававления модидицирует <tex> T</tex> и <tex> D</tex>.
===Порядок добавления отрезков===
От порядка добавления зависит время запроса. Как? Время запрос пропорцианально глубине графа.
Считается, что еслли добавлять отрезки рандомно, то время будет хорошим. Почему и какое время будет рассписано дальше.
===Алгоритм===
#Добавили отрезок.
#Нашли все трапецоиды, которые пересек новый отрезок.
#Удалили их.
#Создали новый трапецоиды.
Рассмотрим подробнее последние две части
Есть два случая.
Простой - отрезок не пересекает ни одного трапецоида, то есть целеком внутри.
Тогда удаляем этот старый трапецоид и на его место ставим дерево из двух концов отрезка, отрезка и четырех образовавшихся трапецоидов.
Важно не забыть правильно определить соседей новых трапецоидов.
В случаи если какие-то трапецоиду выродятся в треугольники будет не четыре новых трапецоида , а 2 или 3. Слава богу это не самая большая проблема.
***картинка***
Сложный - отрезок пересекает сразу несколько трапецоидов.
Итак наш отрезок пересекает трапецоиды <tex>\Delta_0, \Delta_1, \Delta_2 ... \Delta_k</tex>.
Впервую очередь добавляем вертикальные лучи из концов текущего отрезка. Это нужно, чтобы модифицировать <tex>\Delta_0 и \Delta_k</tex>.
Дальше мы модифицуруем вертикальные лучи, которые пересекают текущий отрезок. Этот процесс происходит достаточно быстро, так мы храним много информацию об этих лучах в
<tex>\Delta_0, \Delta_1, \Delta_2 ... \Delta_k</tex>. Теперь мы должны удалить соответствующие листья и на новые которые появились из-за изменения лучей.
