Изменения

Трапецоидная карта <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><texincludeonly>O(log(n))[[Категория: В разработке]]</texincludeonly> Трапецоидная карта {{---}} структура данных для локализации в конфигурации отрезков.

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

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

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

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

[[Файл:Trapezoidmapnavigationshagal.jpgpng|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=*''вершины'', а точнее откуда они берутся. **4 вершины уходит на оболочку <tex>R</tex>**<tex>2 \cdot n</tex> концы отрезков**<tex>2 \cdot 2n</tex> пересечения вертикальных лучей из концов отрезков с другими отрезками или оболочкой*''трапецоиды''Будем смотреть на левую сторону трапецоида.

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

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

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

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

Поисковая структура(в дальнейшем <tex> D</tex>) предсталяет представляет из себя ацикличный ациклический граф с одним корнем и каждому трапецоиду в структре соответствует один листсоответствующими трапецоидам листьями.

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

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

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

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

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

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

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

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

*Создали новый новые трапецоиды.[[Файл:TrpezoidmapbadcaseshagalTrpezoidmapbadcaseshaga.jpgpng|400px|thumb|right|сложный случай]] ===Поиск трапецоидов, которые пересек отрезок===Чтобы модифицировать карту, мы должны понять, где произошло изменение. Оно произошло в тех трапецоидах, которые пересек текущий отрезок. Пусть якобы есть множество трапецоидов <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>, то сосед нижний и наоборот.

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

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

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

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

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

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

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

<tex>\Delta_0Заметим, \Delta_1что не нужно каждый раз хранить все трапецоиды, \Delta_2 которые пересек отрезок.Можно менять структуру во время поиска этих трапецоидов.Если идти по отрезку слева направо, то, как только отрезок пересек очередное вертикальное дополнение, новый трапецоид левее этого дополнения заканчивается и больше изменяться не будет. Мы можем сразу поменять структуру. Таким образом, сложный случай сводится к простому.===Модификация трапецоидной карты===Совместим update и алгоритм поиска новых трапецоидов.Находим первый трапецоид, в который попал новый отрезок. Предположим, у нас простой случай, то есть менять нужно только один трапецоид. \Delta_k</tex>В таком случае мы сразу его модифицируем.

Запрос производится за время пропорцианальное глубине Предположим, у нас есть запрос на локализацию точки <tex>q</tex>. Время, затраченное на этот запрос, будет линейно зависеть от глубины графа.  При добавлении в карту очередного отрезка(поисковой структурыв дальнейшем, итерация алгоритма). Если считать, что на каждой итерации глубина увеливается графа увеличивается максимум на 3, то время работы в худшем случаи будет O(3n). Но Из этого мы вспоминаем, что порядок добавления отрезков рандомный, а потому наврядли всегда будет худший случайможем сделать простую оценку.

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

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

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

Как уже упоминалось, на каждой итерации добавляется не более 3 узлов, а значит <tex>X_i \leq 3</tex>. Считая, что <tex> P_i </tex> {{--- }} вероятность того, что существует узел, который встречается при нашем запросе, созданный на <tex>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(<tex> \Delta_q(i) \ne \Delta_q(i - 1) )</tex>. Если эти два трапецоида не равны, значит, на i-ой итерации трапецоид <tex>\Delta_q(i)</tex> был одним из созданных при модификации. Заметим, что все трапецоиды, созданные на этой итерации, были смежны текущему отрезку(<tex>s_i</tex>).

Если эти два трапеецоида не равныЗначит, значит на i-ой итерации трапецоид либо <tex> s_i = \Delta_q(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>-ой итерации были смежны текущему отрезку. Тогда состояние трапецоидов никак не будет зависеть от порядка добавленных отрезков.

Либо этот отрезок был top или bottom, либо Тогда вероятность изменения трапецоида {{---}} это его концы были leftp или rightp. Представимвероятность исчезнуть, что наш трапецоид если удалится <tex> \Delta_q(i) s_i</tex> исчез когда мы удалили текущий отрезок. Он мог исчезнуть только если исчез один из указателей(top, bottom ...).

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

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

leftp исчезает только в том случаи если leftp была концом теккущего отрезка. А потому эта вероятность тоже равна 1/i. Аналогично для rightpСуммируем по всем 4 сторонам.

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

<tex>\sum^{n}_{i=1}E[X_i]</tex> <= <tex>\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) + <tex>\sum^{n}_{i=1}</tex>количество узлов созданное на <tex>i</tex>-ой итерации

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

<tex>\mathrm{Mem } = \mathcal{O}(n) + <tex>\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>

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

А тогда Mem = O(n) Из этих двух выводов очевидно следует, что время построения карты равно <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) Строим оболочку(просто находим крайние точки множества отрезков по четырем направлениям) Строим рандомную перестановку отрезков for для всех ищем множество трапецоидов пересекаемых отрезком <tex>s_i</tex>. //это специальная функция// Удаляем это множество из карты и добавляем новые узлы появившиеся из-за <tex>s_i</tex> в поисковой структуре Аналогично для просто карты ==Ссылки==[http://graphics.stanford.edu/courses/cs268-09-winter/ Lecture notes from stanford, Seidel] [[Категория: Вычислительная геометрия]]