==Постановка задачи==
Предположим, у нас есть наши координаты, и есть карта мира.
Мы можем найти по карте наше местоположение и сказать в какой области мы находимся.
Области задаются отрезками.
''===Формальная постановка задачи''===
Есть множество отрезков на плоскости.
Есть запрос (точка q), на выход подается область заданная какими-то отрезками в которой находится q.
==Структура данных==
===Геометрическая=== У нас есть множество отрезков ограничееных оболочкой R(это не выпуклая оболочка, а просто мнимая граница плоскости за которую не вылезают отрезки) Мы договариваемся что никакие две точки не лежат на одной вертикале(в противном случаи все еще противнее)
''Трапецоидная карта'' множества отрезков S - это эти отрезки + из кажой точки выпущены два луча, вверх и вниз до первого пересечения с другим отрезком или с оболочкой R.
***картинака***
Именно отсюда берется название стрктуры, так как любой face либо трапеция, либо треугольник.
Введем обозначения для навигации по карте.
*левая граница(leftp) - точка определяющая левуюы сторону трапецоида или в случаи треугольника просто являющаяся левой вершиной. *правая граница(rightp) - аналогично левой только справа. *верхний отрезок(top) и нижний отрезок(bottom) - отрезки ограничивающие трапецоид сверху и снизу. [[Файл:Trapezoidmapshagal.jpg|400px|thumb|right|трапецоидная карта]] ***картинка**** *трапецоиды называются смежными, если имеют общую вертикальную границу. *пусть <tex>\Delta_1 и \Delta_2</tex> смежны и либо top(<tex>\Delta_1</tex>) = top(<tex>\Delta_2</tex>), либо bottom(<tex>\Delta_1</tex>) = bottom(<tex>\Delta_2</tex>)
Тогда <tex>\Delta_1</tex>,<tex>\Delta_2</tex> называют либо большими левыми соседями, либо меньшими.
Теорема о количетве трапецоидов
===Поисковая структура===
Поисковая структура(в дальнейшем <tex> D</tex>) предсталяет из себя ацикличный граф с одним корнем и каждому трапецоиду в структре сооьветствует один лист.
У каждого узла есль два ребенка и при этом узел может быть двух типов.
Первый тип узла - точка, соответствующая концу отрезка.
Второй тип узла - отрезок.
Во время запроса мы двигаемся по графу от его корня до момента, когда окажемся в листе, это и будет означать что точка находится внутри трапецоида.
Если мы находимся не в листе, то мы должны опрелетиться в каком из детей мы окажемся дальше.
Еcть два правила:
#Если текущий узел соответсвует вершине, то смотрим левее или провее мы находимся(проверка по x-координате).
#Если текущий узел соответствует отрезку, то смотрим выше или ниже мы находимся(проверка по y-координате).
#Плохие случаи:
##Мы находимся на одной вертикале с вершиной
##Мы находимся на отрезке
Решение: молиться, или просто обрабатывать вручную.
==Алгоритм==
Мы рассматриваем алгоритм построения карты и алгоритм запроса.
===Алгоритм построения карты===
Во время построения трапецоидной карты(в дальнейшем <tex> T</tex>) алгоритм так же строит структуру для поиска (в дальнейшем <tex> D</tex>).
Так как трапецоидная карта - геометрическая структура, а основные операции ведутся именно с поисковой, упор на неё.
Наш алгоритм добавляет отрезки по одному и после каждого добававления модидицирует <tex> T</tex> и <tex> D</tex>.
===Порядок добавления отрезков===
От порядка добавления зависит время запроса. Как? Время запрос пропорцианально глубине графа.
Считается, что еслли добавлять отрезки рандомно, то время будет хорошим. Почему и какое время будет рассписано дальше.
===Алгоритм===
#Добавили отрезок.
#Нашли все трапецоиды, которые пересек новый отрезок.
#Удалили их.
#Создали новый трапецоиды.
Рассмотрим подробнее последние две части
Есть два случая.
Простой - отрезок не пересекает ни одного трапецоида, то есть целеком внутри.
Тогда удаляем этот старый трапецоид и на его место ставим дерево из двух концов отрезка, отрезка и четырех образовавшихся трапецоидов.
Важно не забыть правильно определить соседей новых трапецоидов.
В случаи если какие-то трапецоиду выродятся в треугольники будет не четыре новых трапецоида , а 2 или 3. Слава богу это не самая большая проблема.
***картинка***
Сложный - отрезок пересекает сразу несколько трапецоидов.
По очереди добавляем отрезки на плоскость. На каждом шагу модифицуруем трапецоидную карту.
===Алгоритм локализации точки===
==Асимптотика==
Рассмотрим путь пройденный точкой при запросе. Каждый узел на этом пути был создан на какой-то итерации алгоритма.
Пусть <tex>X_i</tex> - количество узлов созданных на i-ой bnthfwbb алгоритма.
<tex>X_i</tex> рандомная велина зависящая только от рандомного порядка добавления отрезков.
===Память===
===Построение===
===Запрос===
Запрос производится за время пропорцианальное глубине графа(поисковой структуры). Если считать, что на каждой итерации глубина увеливается максимум на 3, то время работы
в худшем случаи будет O(3n). Но мы вспоминаем, что порядок добавления отрезков рандомный, а потому наврядли всегда будет худший случай.
Рассмотрим путь пройденный точкой по графу. Каждый узел был создан на какой-то итерации цикла. Обозначим за <tex>X_i</tex> - количество узлов созданных на итерации i.
Эта величина зависит только от порядка добаления отрезков(если множество установлено).
Будет искать математическое ожидание глубины графа.
<tex>E[\sum^{n}_{i=1}X_i] = \sum^{n}_{i=1}E[X_i]</tex>
==Реализация==
Здесь будут примерно расссписано, то как реализовывать основные моменты.
===Определение трапецоидов, которых пересечет новый отрезок===
List<Trapezoid> FollowSegment
Point p, q - концы текущего отрезка.
Запрос на p - выдает трапецоид из текущего состояния карты, в котором лежит p(локализуем p)
j = 0
while q справа от правой границы трапецоида номер j
if правая граница выше отрезка then
трапецоид номер j + 1 , будет меньшим правым соседом j
else
трапецоид номер j + 1 , будет большим правым соседом j
j = j + 1
return трапецоиды которые попали.
===Построение карта===
Поисковая структура и карта Trapezoid map
Находим оболочку <tex>R</tex>, такую что все отрезки находятся внутри.
Строим <b>рандомную</b> перестановку отрезков.
for i = 1 to n
Находим множество трапецоидов пересекаемых текущим отрезком.
Удаляем из нужные листья из <tex> D </tex>, обавляем новые.
