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

2012-03-14T17:55:39Z

109.188.220.108: /* Структура данных */

Трапецоидная карта {{---}} геометрическая структура позволяющая локализоваться на площади за <tex>\mathcal{O}(\log(n))</tex>.
==Постановка задачи==
Предположим, у нас есть наши координаты, и есть карта мира.

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

'''Формальная постановка задачи'''

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

==Структура данных==
[[Файл:Trapezoidmapshagal.png|450px|thumb|right|трапецоидная карта]]

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

У нас есть множество отрезков, ограниченных оболочкой <tex>R</tex>(это не выпуклая оболочка, а просто мнимая граница плоскости, за которую не вылезают отрезки).

Мы договариваемся, что никакие две точки не лежат на одной вертикали(в противном случае всё ещё противнее).

''Трапецоидная карта'' множества отрезков <tex>S</tex> {{---}} это эти отрезки и из каждой точки выпущены два луча {{---}} вверх и вниз, до первого пересечения с другим отрезком или с оболочкой <tex>R</tex>.

{{Лемма
|statement= Любой <tex>\operatorname{face}</tex> трапецоидной карты ограничен одним или двумя вертикальными отрезками и обязательно двумя не вертикальными отрезками.
}}
[[Файл:Trapezoidmapnavigationshagal.jpg|650px|thumb|right|навигация в трапецоидной карте]]

Именно отсюда берется название структуры, так как любой <tex>\operatorname{face}</tex> либо трапеция, либо треугольник.

Введем обозначения для навигации по карте.

*''левая граница'' (<tex>\operatorname{leftp}</tex>) {{---}} точка, определяющая левую сторону трапецоида или, в случаи треугольника, просто являющаяся левой вершиной.
*''правая граница'' (<tex>\operatorname{rightp}</tex>) {{---}} аналогично левой, только справа.
*''верхний отрезок'' (<tex>\operatorname{top}</tex>) и нижний отрезок(<tex>\operatorname{bottom}</tex>) {{---}} отрезки, ограничивающие, трапецоид сверху и снизу.
*трапецоиды называются ''смежными'', если имеют общую вертикальную границу.
*пусть <tex>\Delta_1</tex> и <tex>\Delta_2</tex> смежны и либо <tex>\operatorname{top}(\Delta_1) = \operatorname{top}(\Delta_2)</tex>, либо <tex>\operatorname{bottom}(\Delta_1) = \operatorname{bottom}(\Delta_2)</tex>. Тогда <tex>\Delta_1</tex> и <tex>\Delta_2</tex> называют либо нижними, либо верхними левыми соседями.

{{Теорема
|statement=Трапецоидная карта, построенная на <tex>n</tex> отрезках содержит максимум <tex>6n+4</tex> вершины и максимум <tex>3n+1</tex> трапецоид.
|proof=
*''вершины'', а точнее откуда они берутся.
[[Файл:Trapezoidmapnavigationleftpshagal.jpg|400px|thumb|right|варианты leftp(<tex>\Delta</tex>)]]
**4 вершины уходит на оболочку <tex>R</tex>
**<tex>2 \cdot n</tex> концы отрезков
**<tex>2 \cdot 2n</tex> пересечения вертикальных лучей из концов отрезков с другими отрезками или оболочкой
*''трапецоиды''
Будем смотреть на левую сторону трапецоида.

У каждого трапецоида есть точка <tex>\operatorname{leftp}(\Delta)</tex>. Либо это конец какого-то отрезка, либо это левый нижний угол оболочки.

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

Далее заметим, что правый конец отрезка может быть <tex>\operatorname{leftp}(\Delta)</tex> только для одного трапецоида.

Левый конец может быть <tex>\operatorname{leftp}(\Delta)</tex> максимум для двух трапецоидов.

Из этого следует, что количество трапецоидов <tex>n + 2n + 1 = 3n + 1</tex>.

}}
Хранить трапецоиды можно в чем угодно. Вместе с самим трапецоидом, стоит хранить <tex>\operatorname{leftp}</tex>, <tex>\operatorname{rightp}</tex>, <tex>\operatorname{top}</tex> и <tex>\operatorname{bottom}</tex>. Так же следует хранить соседей трапецоида.

----

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

У каждого узла есть два ребенка. При этом узел может быть двух типов.
[[Файл:Trapezoidmapsearchstructureshagal.jpg|650px|thumb|right|навигация в трапецоидной карте]]

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

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

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

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

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

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

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

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

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

==Алгоритм==
[[Файл:Trapezoidmapnotsuchbadcaseshagal.jpg|400px|thumb|right|простой случай]]
Во время построения трапецоидной карты(в дальнейшем <tex>T</tex>) алгоритм так же строит структуру для поиска.

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

Наш алгоритм добавляет отрезки по одному и, после каждого добавления, модидицирует <tex>T</tex> и <tex>D</tex>.

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

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

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

===Алгоритм===

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

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

*Удалили их.

*Создали новые трапецоиды.
[[Файл:Trpezoidmapbadcaseshagal.jpg|400px|thumb|right|сложный случай]]

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

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

Пусть якобы есть множество трапецоидов <tex>\Delta_0, \Delta_1, \Delta_2 \ldots \Delta_k</tex>, упорядоченное по <tex>s_i</tex>

Пусть <tex>\Delta_{j+1}</tex> {{---}} один из правых соседей <tex>\Delta_j</tex>. Так же, при этом не сложно понять, каким соседом он является.

Если <tex>\operatorname{rightp} \Delta_j</tex> лежит выше <tex>s_i</tex>, то сосед нижний и наоборот.

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

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

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

Есть два случая.
*Простой {{---}} отрезок не пересекает ни одного трапецоида, то есть целиком внутри.

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

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

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

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

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

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

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

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

<tex>\Delta_0, \Delta_1, \Delta_2 \ldots \Delta_k</tex>.
==Случай коллизии==
Рассмотрим момент, когда мы мы строим карты. Мы должны добавить очередной отрезок.

Предположим, левый конец отрезка лежит на одной вертикале с уже добавленной в карту точкой <tex> p </tex>.

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

Что при этом произойдет.

*С геометрической точки зрения, появится ещё несколько трапецоидов, как в случае, если бы вновь добавленная точка была правее на <tex> \varepsilon \rightarrow 0</tex>.

А значит, у трапецоида по прежнему не более двух правых соседей.

*С точки зрения поисковой структуры мы по-прежнему можем локализоваться. По крайней мере, узел, соответствующий точке <tex> p </tex> будет иметь правым сыном нашу точку.

Итого, слова "трапецоидные карты просты отсутствие случаев" появляются именно отсюда, так как, казалось бы, неприятный случай будет прописан заменой <tex>\textless </tex>
на <tex> \le </tex>

==Асимптотика==
===Запрос===
Предположим у нас есть запрос на локализацию точки <tex>q</tex>. Время, затраченное, на этот запрос будет линейно зависеть от глубина графа.

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

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

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

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

Так как никто не выбирал исходное множество отрезков и запрос <tex>q</tex>, <tex>X_i</tex> {{---}} рандомная величина, зависящая только от рандомного порядка добавления отрезков.

<tex>E[\sum^{n}_{i=1}X_i] = \sum^{n}_{i=1}E[X_i]</tex>

Как уже упоминалось, на каждой итерации добавляется не более 3 узлов, а значит <tex>X_i \leq 3</tex>.

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

<tex>\sum^{n}_{i=1}E[X_i] <= \sum^{n}_{i=1}3P_i</tex>

Начинаем оценивать <tex> P_i </tex>.

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

Это значит, что на <tex>i-1</tex>-ой итерации мы локализовывали <tex>q</tex> в трапецоиде <tex>\Delta_q(i-1)</tex>,а на <tex>i</tex>-ой итерации уже в трапецоиде <tex> \Delta_q(i) </tex> и эти два трапецоида разные.

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

Таким образом <tex>P_i = P(\Delta_q(i) \ne \Delta_q(i - 1))</tex>.

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

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

Значит либо <tex>s_i = \operatorname{top} \Delta_i</tex> или <tex>\operatorname{bottom} \Delta_i</tex>, либо концы <tex>s_i = \operatorname{leftp} \Delta_i</tex> или <tex>\operatorname{rightp} \Delta_i</tex>.

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

Тогда, вероятность изменения трапецоида {{---}} это его вероятность исчезнуть, если удалится <tex>s_i</tex>.

Тогда переходим, к <tex>\operatorname{top} \Delta_i</tex> и т.п. так как мы уже говорили, что <tex>s_i</tex> будет определенной стороной при навигации.

Отрезки добавлялись рандомно, поэтому, в качестве <tex>s_i</tex> мог быть любой отрезок из <tex>S_i</tex>. А, тогда, вероятность для всех сторон <tex>\frac1i</tex>.

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

Таким образом <tex>P_i = P( \Delta_q(i) \ne \Delta_q(i - 1)) = P( \Delta_q(i) \in \Delta_q(i - 1) ) \le \frac4i</tex>

<tex>\sum^{n}_{i=1}E[X_i] \le \sum^{n}_{i=1}3P_i \le \sum^{n}_{i=1}\frac{12}i \le 12\sum^{n}_{i=1}(1/i) \approx 12 \cdot log(n)</tex>

===Память===
Заметим, что количество трапецоидов, как мы доказали раньше, равно <tex>\mathcal{O}(n)</tex>, поэтому мы должны оценить количество узлов созданых на <tex>i</tex>-ой итерации.

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

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

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

<tex>\mathrm{Mem} = \mathcal{O}(n) + \sum^{n}_{i=1} E[k_i]</tex>

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

А тогда <tex>\mathrm{Mem} = \mathcal{O}(n)</tex>

Из этих двух выводов очевидно следует, что время построения карты равно <tex>\mathcal{O}(n \log n)</tex>.

==Реализация==
Здесь будут рассмотрены некоторые основные моменты реализации
Это только идеи, в коде все выглядит примерно в 50 раз хуже.(по количеству строк)
===Класс "трапецоид"===
struct Trapezoid
Trapezoid next
Trapezoid up
Trapezoid down
Trapezoid end
Segment top
Segment bottom
Point left
Point right

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

TrapezoidMap(S - segments)
Строим оболочку(просто находим крайние точки множества отрезков по четырем направлениям)
Строим рандомную перестановку отрезков
for для всех
ищем множество трапецоидов пересекаемых отрезком <tex>s_i</tex>. //это специальная функция//
Удаляем это множество из карты и добавляем новые узлы появившиеся из-за <tex>s_i</tex> в поисковой структуре
Аналогично для просто карты

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

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

==Ссылки==
[http://graphics.stanford.edu/courses/cs268-09-winter/ Lecture notes from stanford, Seidel]

Викиконспекты - Вклад участника [ru]

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