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

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

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

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

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

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