Трапецоидная карта

Трапецоидная карта - геометрическая структура позволяющая локализоваться на площади за [math]O(log(n))[/math].

Постановка задачи

 Предположим, у нас есть наши координаты, и есть карта мира.
 Мы можем найти по карте наше местоположение и сказать в какой области мы находимся.
 Области задаются отрезками. 
 Формальная постановка задачи

Есть множество отрезков на плоскости. Есть запрос (точка q), на выход подается область заданная какими-то отрезками в которой находится q.

Структура данных

Геометрическая

У нас есть множество отрезков ограничееных оболочкой R(это не выпуклая оболочка, а просто мнимая граница плоскости за которую не вылезают отрезки) Мы договариваемся что никакие две точки не лежат на одной вертикале(в противном случаи все еще противнее) Трапецоидная карта множества отрезков S - это эти отрезки + из кажой точки выпущены два луча, вверх и вниз до первого пересечения с другим отрезком или с оболочкой R. ***картинака*** !!!Очевидный факт - любой face трапецоидной карты ограничен одним или двумя вертикальными отрезками и обязательно двумя не вертикальными отрезками. Именно отсюда берется название стрктуры, так как любой face либо трапеция, либо треугольник. Введем обозначения для навигации по карте. *левая граница(leftp) - точка определяющая левуюы сторону трапецоида или в случаи треугольника просто являющаяся левой вершиной. *правая граница(rightp) - аналогично левой только справа. *верхний отрезок(top) и нижний отрезок(bottom) - отрезки ограничивающие трапецоид сверху и снизу.

***картинка**** *трапецоиды называются смежными, если имеют общую вертикальную границу. *пусть [math]\Delta_1 и \Delta_2[/math] смежны и либо top([math]\Delta_1[/math]) = top([math]\Delta_2[/math]), либо bottom([math]\Delta_1[/math]) = bottom([math]\Delta_2[/math])

Тогда [math]\Delta_1[/math],[math]\Delta_2[/math] называют либо большими левыми соседями, либо меньшими. Хранить трапецоиды можно в чем угодно. Вместе с самим трапецоидом, стоит хранить leftp, rightp, top и bottom так же следует хранить соседей трапецоида.

Теорема о количетве трапецоидов

Поисковая структура

Поисковая структура(в дальнейшем [math] D[/math]) предсталяет из себя ацикличный граф с одним корнем и каждому трапецоиду в структре сооьветствует один лист.

У каждого узла есль два ребенка и при этом узел может быть двух типов.

Первый тип узла - точка, соответствующая концу отрезка.

Второй тип узла - отрезок.

Во время запроса мы двигаемся по графу от его корня до момента, когда окажемся в листе, это и будет означать что точка находится внутри трапецоида.

Если мы находимся не в листе, то мы должны опрелетиться в каком из детей мы окажемся дальше.

Еcть два правила:

#Если текущий узел соответсвует вершине, то смотрим левее или провее мы находимся(проверка по x-координате).

#Если текущий узел соответствует отрезку, то смотрим выше или ниже мы находимся(проверка по y-координате).

#Плохие случаи:

##Мы находимся на одной вертикале с вершиной

##Мы находимся на отрезке

Решение: молиться, или просто обрабатывать вручную.

Алгоритм

Мы рассматриваем алгоритм построения карты и алгоритм запроса.

Алгоритм построения карты

Во время построения трапецоидной карты(в дальнейшем [math] T[/math]) алгоритм так же строит структуру для поиска (в дальнейшем [math] D[/math]). Так как трапецоидная карта - геометрическая структура, а основные операции ведутся именно с поисковой, упор на неё. Наш алгоритм добавляет отрезки по одному и после каждого добававления модидицирует [math] T[/math] и [math] D[/math]. ===Порядок добавления отрезков=== От порядка добавления зависит время запроса. Как? Время запрос пропорцианально глубине графа. Считается, что еслли добавлять отрезки рандомно, то время будет хорошим. Почему и какое время будет рассписано дальше. ===Алгоритм=== #Добавили отрезок. #Нашли все трапецоиды, которые пересек новый отрезок. #Удалили их. #Создали новый трапецоиды. Рассмотрим подробнее последние две части Есть два случая. Простой - отрезок не пересекает ни одного трапецоида, то есть целеком внутри. Тогда удаляем этот старый трапецоид и на его место ставим дерево из двух концов отрезка, отрезка и четырех образовавшихся трапецоидов. Важно не забыть правильно определить соседей новых трапецоидов. В случаи если какие-то трапецоиду выродятся в треугольники будет не четыре новых трапецоида , а 2 или 3. Слава богу это не самая большая проблема. ***картинка*** Сложный - отрезок пересекает сразу несколько трапецоидов.

 По очереди добавляем отрезки на плоскость. На каждом шагу модифицуруем трапецоидную карту.

Асимптотика

Рассмотрим путь пройденный точкой при запросе. Каждый узел на этом пути был создан на какой-то итерации алгоритма. Пусть [math]X_i[/math] - количество узлов созданных на i-ой bnthfwbb алгоритма. [math]X_i[/math] рандомная велина зависящая только от рандомного порядка добавления отрезков.

Запрос

Запрос производится за время пропорцианальное глубине графа(поисковой структуры). Если считать, что на каждой итерации глубина увеливается максимум на 3, то время работы в худшем случаи будет O(3n). Но мы вспоминаем, что порядок добавления отрезков рандомный, а потому наврядли всегда будет худший случай. Рассмотрим путь пройденный точкой по графу. Каждый узел был создан на какой-то итерации цикла. Обозначим за [math]X_i[/math] - количество узлов созданных на итерации i. Эта величина зависит только от порядка добаления отрезков(если множество установлено). Будет искать математическое ожидание глубины графа. [math]E[\sum^{n}_{i=1}X_i] = \sum^{n}_{i=1}E[X_i][/math]

Реализация

Здесь будут примерно расссписано, то как реализовывать основные моменты. ===Определение трапецоидов, которых пересечет новый отрезок=== 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 Находим оболочку [math]R[/math], такую что все отрезки находятся внутри. Строим рандомную перестановку отрезков. for i = 1 to n Находим множество трапецоидов пересекаемых текущим отрезком. Удаляем из нужные листья из [math] D [/math], обавляем новые.