Изменения

<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>не пересекая образующие конфигурацию отрезки.

[[Файл:TrapazoidmapshagalTrapezoidmapshagal.jpgpng|650px450px|thumb|right|трапецоидная карта]]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В случаи если какие-то Итак, наш отрезок пересекает трапецоиды выродятся в треугольники будет не четыре новых трапецоида <tex>\Delta_0, \Delta_1, а 2 или 3\Delta_2 ... Слава богу это не самая большая проблема\Delta_k</tex>.

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

Итак наш Дальше мы модифицуруем вертикальные лучи, которые пересекают текущий отрезок пересекает трапецоиды <tex>\Delta_0, \Delta_1. Этот процесс происходит достаточно быстро, \Delta_2 ... \Delta_k</tex>так мы храним много информацию об этих лучах.

Дальше мы модифицуруем вертикальные лучи<tex>\Delta_0, которые пересекают текущий \Delta_1, \Delta_2 \ldots \Delta_k</tex>.*Находим множество трапецоидов, которых пересек отрезок. Этот процесс происходит достаточно быстро*Находим этот трапецоид в <tex> T </tex> и добавили вместо него нужные трапецоиды.*Спускаемся по <tex> D </tex> до соответствующих трапецоидов.*Вместо них добавляем новые ключи, так мы храним много информацию об этих лучах в как показано на картинке.

По хорошему Заметим, что не нужно каждый раз хранить все трапецоиды, которые пересек отрезок. Можно менять структуру во время поиска этих трапецоидов.Если идти по отрезку слева направо, то , как этот происходит просто ужасно только отрезок пересек очередное вертикальное дополнение, новый трапецоид левее этого дополнения заканчивается и видеть это больше изменяться не хочетсябудет. Мы можем сразу поменять структуру. Таким образом, сложный случай сводится к простому.===Модификация трапецоидной карты===Совместим update и алгоритм поиска новых трапецоидов.Находим первый трапецоид, в который попал новый отрезок. Предположим, а все потомуу нас простой случай, то есть менять нужно только один трапецоид. В таком случае мы сразу его модифицируем. Если новый отрезок пересекает несколько трапецоидов.Рассмотрим момент, когда текущий трапецоид заканчивается и мы начинаем рассматривать его соседей.Очевидно, что много что добавляется много новых узловесли мы модифицируем закончившийся трапецоид, мы по прежнему сможем рассматривать его соседей.При этом модификацию мы проводим так же, как в простом случае.  '''Update'''(Segment s) Point p <tex>\leftarrow</tex> s.start Point q <tex>\leftarrow</tex> s.finish Находим первый трапецоид <tex>\Delta_{0}</tex> <tex>\Delta_{temp}</tex> while q справа от rightp(<tex>\Delta_{0}</tex>) if <tex>\Delta_{0}</tex> ниже <tex> s_{i} </tex> <tex>\Delta_{temp}</tex> нижний правый сосед <tex>\Delta_{0}</tex> else <tex>\Delta_{temp}</tex> верхний правый сосед <tex>\Delta_{0}</tex> Модифицируем <tex>\Delta_{0}</tex> <tex>\Delta_{0} \leftarrow \Delta_{temp}</tex>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Что значит, что узел был создан на <tex>i</tex>-ой итерации и встретился при запросе q? Это значит, что на i - 1-ой итерации мы локализовывали q в трапецоиде <tex> \Delta_q(i - 1) 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</tex> = P(<tex> \Delta_q(i) \ne \Delta_q(i - 1)) </tex>).

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

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

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

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

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

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

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

Таким образом <tex>P_i = P( \Delta_q(i) \ne \Delta_q(i - 1)) = P( \Delta_q(i) \in \Delta_q(i - 1) ) \le 4/i\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>-ой итерации.

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

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

Mem = <tex>\mathrm{Mem} = \mathcal{O}(n) + \sum^{n}_{i=1}E[k_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] = \frac{1}i \sum^{}_{s \in S_i} \sum^{}_{\Delta \in T(S_i)} \delta(\Delta, s) \le \frac{4|T(S_i|}i = \mathcal{O}(1)</tex>

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

А тогда Mem = <tex>O(n)</tex> Из этих двух выводов очевидно следует, что время построения карты равно <tex>\mathcal{O}(nlognn \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)  Строим оболочку(просто находим крайние точки множества отрезков по четырем направлениям) Строим рандомную перестановку отрезков

ищем множество трапецоидов пересекаемых отрезком <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