==Алгоритм==
Мы рассматриваем алгоритм построения карты и алгоритм запроса[[Файл:Trapezoidmapnotsuchbadcaseshagal.jpg|400px|thumb|right|простой случай]]===Алгоритм построения карты=== Во время построения трапецоидной карты(в дальнейшем <tex> T</tex>) алгоритм так же строит структуру для поиска (в дальнейшем <tex> D</tex>). Так как трапецоидная карта - геометрическая структура, а основные операции ведутся именно с поисковой, упор на неё. Наш алгоритм добавляет отрезки по одному и после каждого добававления модидицирует <tex> T</tex> и <tex> D</tex>. ===''Порядок добавления отрезков==='' От порядка добавления зависит время запроса. Как? Время запрос пропорцианально глубине графа. Считается, что еслли добавлять отрезки рандомно, то время будет хорошим. Почему и какое время будет рассписано дальше. ===''Алгоритм==='' #*Добавили отрезок. #*Нашли все трапецоиды, которые пересек новый отрезок. #*Удалили их. # *Создали новый трапецоиды. [[Файл:Trpezoidmapbadcaseshagal.jpg|400px|thumb|right|сложный случай]]Рассмотрим подробнее последние две части Есть два случая. *Простой - отрезок не пересекает ни одного трапецоида, то есть целеком внутри. Тогда удаляем этот старый трапецоид и на его место ставим дерево из двух концов отрезка, отрезка и четырех образовавшихся трапецоидов. Важно не забыть правильно определить соседей новых трапецоидов. В случаи если какие-то трапецоиду выродятся в треугольники будет не четыре новых трапецоида , а 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>. Теперь мы должны удалить соответствующие листья и на новые которые появились из-за изменения лучей.
