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

Материал из Викиконспекты
Перейти к: навигация, поиск

Трапецоидная карта - геометрическая структура позволяющая локализоваться на площади за [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]
  • вершины, а точнее откуда они берутся.
варианты leftp([math]\Delta[/math])
    • 4 вершины уходит на оболочку R.
    • 2*n концы отрезков
    • 2*2n пересечения вертикальных лучей из концов отрезков с другими отрезками или оболочкой
  • трапецоиды

Будем смотреть на левую сторону трапецоида.

У каждого трапецоида есть точка leftp([math]\Delta[/math]). Либо это конец какого-то отрезка, либо это левый нижний угол оболочки.

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

Далее заметим, что правый конец отрезка может быть leftp([math]\Delta[/math]) только для одного трапецоида.

Левый конец может быть leftp([math]\Delta[/math]) максимум для двух трапецоидов.

Из этого следует, что количество трапецоидов n + 2n + 1 = 3n + 1.
[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] и эти два трапецоида разные.

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

Таким образом [math]P_i[/math] = 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 для всех
   
     ищем множество трапецоидов пересекаемых отрезком [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

Ссылки

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Трапецоидная_карта&oldid=18175»