Изменения

<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div><includeonly>[[Категория: В разработке]]</includeonly> Трапецоидная карта {{---}} геометрическая структура позволяющая локализоваться на площади за <tex>\mathcal{O}(\log(n))</tex>данных для локализации в конфигурации отрезков.

Предположим, у нас есть наши координаты, и есть карта мира. Мы можем найти по карте наше местоположение и сказать в какой стране мы находимся.Области задаются замкнутыми ломаными. '''Формальная постановка задачи'''  Есть множество конфигурация отрезков на плоскостии dcel-подобная структура, позволяющая по ребру из конфигурации получить соответствующий face.Есть запрос (точка <tex>q</tex>)Трапецоидная карта позволяет найти ребро, на выходе {{--до которого можно дойти от точки-}} областьзапроса, в которой находится точка <tex>q</tex>не пересекая образующие конфигурацию отрезки.

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

[[Файл:Trapezoidmapnavigationshagal.jpgpng|650px|thumb|right|навигация в трапецоидной картеТрапецоидная карта]]

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

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

*Если текущий узел соответсвует вершине, то смотрим левее или правее мы находимся(проверка по <tex>x</tex>-координате)выбираем лексикографически нужную.*Если текущий узел соответствует отрезку, то смотрим , выше или ниже мы находимся(проверка по <tex>y</tex>-координате). *Плохие случаи: Мы находимся на одной вертикали с вершиной Мы находимся на отрезке (Решение: молиться, или просто обрабатывать вручную.)

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

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

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

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

[[Файл:TrpezoidmapbadcaseshagalTrpezoidmapbadcaseshaga.jpgpng|400px|thumb|right|сложный случай]]

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

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

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

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

В случае, если какие-то трапецоиды выродятся в треугольники, будет не четыре новых трапецоида, а 2 или 3. Слава богу это не самая большая проблема*Находим множество трапецоидов, которых пересек отрезок (в данном случаи он один).*Находим этот трапецоид в <tex> T </tex> и добавляем вместо него нужные трапецоиды.*Спускаемся по <tex> D </tex> до соответствующего трапецоида.*Вместо этого трапецоида добавляем ключ "x" и строим оттуда часть структуры, как показано на картинке.

*'''Сложный''' {{---}} отрезок пересекает сразу несколько трапецоидов. Итак , наш отрезок пересекает трапецоиды <tex>\Delta_0, \Delta_1, \Delta_2 ... \Delta_k</tex>.

Рассмотрим момент, когда мы мы строим карты. Мы должны добавить очередной отрезок.

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

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

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

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

Если эти два трапеецоида трапецоида не равны, значит , на i-ой итерации трапецоид <tex>\Delta_q(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>s_i</tex>.

Используя вывод Введем новую функцию для трапецоида <tex> \Delta </tex> и отрезка s. Выделим множество <tex> S_i \in S </tex>. Пусть <tex> s \in S_i </tex> и <tex> \Delta \in T(S_i) </tex>. <tex> \delta(\Delta, s) </tex> равна 1, если при удалении <tex> s </tex> из предыдущей части получаем<tex> S_i </tex> <tex>, \Delta </tex> удалится, что иначе <tex> \delta </tex> равна 0. <tex>E[k_i] = \le frac{1}i \fracsum^{}_{s \mathcalin S_i} \sum^{O}_{\Delta \in T(iS_i)} \delta(\Delta, s)\le \frac{4|T(S_i|}i = \mathcal{O}(1)</tex>