Изменения

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

<wikitex>{{Определение|id=arrangement|definition ='''Конфигурацией''' (англ. ''arrangement'') $\mathcal{A}(\mathcal{H})$ называется разбиение $\mathbb{R}^d$ в связные открытые(топологически) области размерностей $0, 1 \dots d $ множеством $\mathcal{H}$ гиперплоскостей в $ \mathbb{R}^d$.}} {{Определение|id=cell|definition ='''Ячейкой''' (англ. ''cell'') размерности $d$ в $\mathcal{A}(\mathcal{H})$ называется максимальная связная область в $R^d$, не пересекаемая ни одной гиперплоскостью в $\mathcal{H}$. <br>Ячейкой размерности $k$, где $0 \le k < d$ в $\mathcal{A}(\mathcal{H})$ называется максимальная связная область в пересечении гиперплоскостей подмножества $\mathcal{S} \in \mathcal{H}$, которая не пересекается ни одной гиперплоскостью из множества $\mathcal{H} \setminus \mathcal{S}$.<br>В случае ограниченных гиперплоскостей, ячейками соответствующих размерностей также считаются точки, отрезки (лучи), грани Есть конфигурация отрезков на плоскости и прочие вплоть до размерности $k dcel- 1$подобная структура, $i$-мерные объекты, ограничивающие их.}} {{Определение|id=primitives|definition ='''Вершина''' (англ. ''vertex'') — ячейка размерности 0. <br>'''Ребро''' (англ. ''edge'') — ячейка размерности 1. <br>'''Грань''' (англ. ''позволяющая по ребру из конфигурации получить соответствующий face'') — ячейка размерности 2. <br>'''Сторона''' (англ. ''facet'') — ячейка размерности d-1.}} </wikitex>ПредположимТрапецоидная карта позволяет найти ребро, у нас есть наши координаты, и есть двумерная конфигурация. Наша задача выдать грань содержащую точку. Пусть каждая грань конфигурации является трапецоидом. Тогда каждая грань однозначно задается двумя отрезками ограничивающими эту грань(боковые стороны трапеции).Таким образом задача локализации до которого можно дойти от точки сводится к тому-запроса, что нужно выдать два отрезка между которыми находится точка. Мы можем найти по карте наше местоположение и сказать в какой стране мы находимся.Области задаются замкнутыми ломанымине пересекая образующие конфигурацию отрезки.

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

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

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

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

Во время построения трапецоидной карты(в дальнейшем <tex>T</tex>) алгоритм так же также строит структуру для поиска.

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

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

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

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

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

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

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

Итак , наш отрезок пересекает трапецоиды <tex>\Delta_0, \Delta_1, \Delta_2 ... \Delta_k</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>q</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>.