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

Трапецоидная карта - геометрическая структура позволяющая локализоваться на площади за [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] называют либо нижними левыми соседями, либо верхними.

Теорема:

Трапецоидная карта построенная на n отрезках содержит максимум 6n+4 вершины и максимум 3n+1 трапецоид.

Доказательство:

[math]\triangleright[/math]

вершины, а точнее откуда они берутся. 4 вершины уходит на оболочку R. 2*n концы отрезков 2*2n пересечения вертикальных лучей из концов отрезков с другими отрезками или оболочкой трапецоиды Будем смотреть на левую сторону трапецоида.

[math]\triangleleft[/math]

Хранить трапецоиды можно в чем угодно. Вместе с самим трапецоидом, стоит хранить leftp, rightp, top и bottom так же следует хранить соседей трапецоида.

---

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

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

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

навигация в трапецоидной карте

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

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

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

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

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

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

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

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

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

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

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

Алгоритм

простой случай

Во время построения трапецоидной карты(в дальнейшем [math] T[/math]) алгоритм так же строит структуру для поиска .

Так как трапецоидная карта - геометрическая структура, а основные операции ведутся именно с поисковой, упор на неё.

Наш алгоритм добавляет отрезки по одному и после каждого добававления модидицирует [math] T[/math] и [math] D[/math].

Порядок добавления отрезков

От порядка добавления зависит время запроса. Как? Время запрос пропорцианально глубине графа.

Считается, что еслли добавлять отрезки рандомно, то время будет хорошим. Почему и какое время будет рассписано дальше.

Алгоритм

• Добавили отрезок.

• Нашли все трапецоиды, которые пересек новый отрезок.

• Удалили их.

• Создали новый трапецоиды.

сложный случай

Поиск трапецоидов которых пересек отрезок

Чтобы модифицировать карту, мы должны понять где произошло изменение.

Оно произошло в тех трапецоидах которые пересек текущий отрезок или можно сказать, что трапецоид с i-1-ой итерации не будет в i-ой только если его пересек отрезок.

Пусть якобы есть множество трапецоидов [math]\Delta_0, \Delta_1, \Delta_2 ... \Delta_k[/math] упорядоченное по [math]s_i[/math]

Пусть [math]\Delta_(j+1)[/math] один из правых соседей [math]\Delta_j[/math] Так же при этом не сложно понять каким соседом он является.

Если rightp([math]\Delta_j[/math]) лежит выше [math]s_i[/math], то сосед нижний и наоборот.

Это значит, что если мы знаем первый трапецоид, то мы можем найти остальные просто обходя по карте соседей справа.

Чтобы найти первый трапецоид нужно просто локализоваться правому концу в текущей карте.

update

Рассмотрим подробнее последние две части

Есть два случая.

• Простой - отрезок не пересекает ни одного трапецоида, то есть целеком внутри.

Тогда удаляем этот старый трапецоид и на его место ставим дерево из двух концов отрезка, отрезка и четырех образовавшихся трапецоидов.

Важно не забыть правильно определить соседей новых трапецоидов.

В случаи если какие-то трапецоиды выродятся в треугольники будет не четыре новых трапецоида , а 2 или 3. Слава богу это не самая большая проблема.

• Сложный - отрезок пересекает сразу несколько трапецоидов.

Итак наш отрезок пересекает трапецоиды [math]\Delta_0, \Delta_1, \Delta_2 ... \Delta_k[/math].

Сначала добавляем вертикальные лучи из концов текущего отрезка. Это нужно, чтобы модифицировать [math]\Delta_0 и \Delta_k[/math]. Теперь мы должны удалить соответствующие листья и на новые которые появились из-за изменения лучей.

Дальше мы модифицуруем вертикальные лучи, которые пересекают текущий отрезок. Этот процесс происходит достаточно быстро, так мы храним много информацию об этих лучах в

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

[math]\Delta_0, \Delta_1, \Delta_2 ... \Delta_k[/math].

Асимптотика

Запрос

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

При добавлении в карту очередного отрезка(в дальнейшем итерация алгоритма) глубина графа увеличивается максимум на 3. Из этого мы можем сделать простую оценку.

Наибольшее время на запрос, которое мы можем потратить — 3n. Произойдет это в самом ужасном из самых ужасных случаев.

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

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

Так как никто не выбирал исходное множество отрезков и запрос q, [math]X_i[/math] - рандомная величина зависящая только от рандомного порядка добавления отрезков.

[math]E[\sum^{n}_{i=1}X_i] = \sum^{n}_{i=1}E[X_i][/math]

Как уже упоминалось на каждой итерации добавляется не более 3 узлов, а значит [math]X_i[/math] <= 3.

Считая, что [math] P_i [/math] - вероятность того, что существует узел, который встречается при нашем запросе созданный на i-ой итерации.

[math]\sum^{n}_{i=1}E[X_i] \lt = \sum^{n}_{i=1}3P_i[/math]

Начинаем оценивать [math] P_i [/math].

Что значит, что узел был создан на i-ой итерации и встретился при запросе q?

Это значит, что на i - 1-ой итерации мы локализовывали q в трапецоиде [math] \Delta_q(i - 1) [/math],

а на i-ой итерации уже в трапецоиде [math] \Delta_q(i) [/math] и эти два трапецоида разные.

То есть, после добавления непонятно чего в карту, трапецоид изменился.

Таким образом P_i = P([math] \Delta_q(i) \ne \Delta_q(i - 1) [/math]).

Если эти два трапеецоида не равны, значит на i-ой итерации трапецоид [math] \Delta_q(i) [/math] был одним из созданных при модификации.

Заметим, что все трапецоиды созданные на этой итерации были смежны текущему отрезку([math] s_i [/math]).

Значит либо [math] s_i [/math] = top([math]\Delta_i[/math]) или bottom([math]\Delta_i[/math]), либо концы [math]s_i[/math] = leftp([math]\Delta_i[/math]) или rightp([math]\Delta_i[/math]).

Зафиксируем множество отрезков на i-ой итерации. Тогда состояние трапецоидов никак не будет зависеть от порядка добавленных отрезков.

Тогда, вероятность изменения трапецоида - это его вероятность исчезнуть если удалится [math]s_i[/math].

Тогда переходим, к top([math]\Delta_i[/math]) и т.п. так как мы уже говорили, что [math]s_i[/math] будет определенной стороной при навигации.

Отрезки добавлялись рандомно поэтому в качестве [math]s_i[/math] мог быть любой отрезок из [math]S_i[/math]. А тогда вероятность для всех сторон 1/i.

Суммируем по всем 4 сторонам.

Таким образом P_i = P([math] \Delta_q(i) \ne \Delta_q(i - 1) [/math]) = P([math] \Delta_q(i) \in \Delta_q(i - 1) [/math]) <= 4/i

[math]\sum^{n}_{i=1}E[X_i][/math] <= [math]\sum^{n}_{i=1}3P_i \lt = \sum^{n}_{i=1}12/i \lt =12\sum^{n}_{i=1}(1/i) \approx 12*log(n)[/math]

Память

Заметим, что количество трапецоидов как мы доказали раньше равно O(n), поэтому мы должны оценить количество узлов созданых на i-ой итерации.

А результирующее выражение для памяти тогда будет

Mem = O(n) + [math]\sum^{n}_{i=1}[/math]количество узлов созданное на i-ой итерации

Обозначив за k_i количество узлов созданное на i-ой итерации

Mem = O(n) + [math]\sum^{n}_{i=1}[/math]E[k_i]

Используя вывод из предыдущей части получаем, что E[k_i] <= O(i)/i = O(1)

А тогда Mem = O(n)

Из этих двух выводов очевидно следует, что время построения карты равно O(nlogn)

Реализация

Здесь будут рассмотрены некоторые основные моменты реализации Это только идейные реализации в коде все выглядет пример в 50 раз хуже.(по количеству строк)

Класс "трапецоид"

struct Trapezoid

 Trapezoid next
 Trapezoid up
 Trapezoid down
 Trapezoid end
 Segment top
 Segment bottom
 Point left
 Point right

Построение трапецоидной карты

TrapezoidMap(S - segments)

 Строим оболочку(просто находим крайние точки множества отрезков по четырем направлениям)
 Строим рандомную перестановку отрезков
 for i[math]\leftarrow[/math] 1 to n
 do ищем множество трапецоидов пересекаемых отрезком [math]s_i[/math]. //это специальная функция//
 Удаляем это множество из карты и добавляем новые узлы появившиеся из-за [math]s_i[/math] в поисковой структуре
 Аналогично для просто карты

Поиск трапецоидов, которых пересекает отрезок

LookforTrapezoid([math]s_i[/math] - segment)

 Запоминаем левый и правый конец [math]s_i[/math]  
 
 Делаем запрос на левый конец в карте.
 
 j [math]\leftarrow[/math] 0;
 
 while q [math]\in[/math] правый от rightp(трапецоид_j)
 
   do if rightp(трапецоид_j) над [math]s_i[/math]
 
     then ставим трапецоид_(j+1) нижним правым соседом трапецоид_j.
   
     else ставим трапецоид_(j+1) верхним правым соседом трапецоид_j.
   
   j [math]\leftarrow[/math] j+1

Ссылки

Lecture notes from stanford, Seidel