Изменения

Трапецоидная карта <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> называют либо нижними, либо верхними левыми соседями. 

*верхний отрезок(top) {{Теорема|statement=Трапецоидная карта, построенная на <tex>n</tex> отрезках содержит максимум <tex>6n+4</tex> вершины и нижний отрезок(bottom) - отрезки ограничивающие максимум <tex>3n+1</tex> трапецоид сверху и снизу.|proof=*''вершины'', а точнее откуда они берутся.

**4 вершины уходит на оболочку <tex>R</tex>**<tex>2 \cdot n</tex> концы отрезков**<tex>2 \cdot 2n</tex> пересечения вертикальных лучей из концов отрезков с другими отрезками или оболочкой*''трапецоиды называются смежными, если имеют общую вертикальную границу''Будем смотреть на левую сторону трапецоида.

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

Левый конец может быть <tex>\operatorname{leftp}(\Delta)</tex> максимум для двух трапецоидов.  Из этого следует, что количество трапецоидов <tex>n + 2n + 1 = 3n + 1</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>, то сосед нижний и наоборот. Это значит, что, если мы знаем первый трапецоид, то мы можем найти остальные, просто обходя по карте соседей справа. Чтобы найти первый трапецоид, нужно просто локализовать правый конец в текущей карте.

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

*'''Сложный ''' {{- --}} отрезок пересекает сразу несколько трапецоидов.

Итак , наш отрезок пересекает трапецоиды <tex>\Delta_0, \Delta_1, \Delta_2 ... \Delta_k</tex>.

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

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

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

Запрос производится за время пропорцианальное глубине Предположим, у нас есть запрос на локализацию точки <tex>q</tex>. Время, затраченное на этот запрос, будет линейно зависеть от глубины графа.  При добавлении в карту очередного отрезка(поисковой структурыв дальнейшем, итерация алгоритма). Если считать, что на каждой итерации глубина увеливается графа увеличивается максимум на 3. Из этого мы можем сделать простую оценку. Наибольшее время на запрос, то время работы в худшем случаи будет O(которое мы можем потратить {{---}} <tex>3n)</tex>. Но  Как говорилось раньше, отрезки мы вспоминаем, что порядок добавления отрезков рандомныйдобавляем в случайном порядке, а потому наврядли всегда редко будет худший самый ужасный случай, и, с вероятностных точек зрения, время на запрос будет меньше. Рассмотрим путь , пройденный точкой по графу. Каждый узел был создан на какой-то итерации цикла. Обозначим за <tex>X_i</tex> - количество узлов , созданных на итерации <tex>i</tex>. Эта Так как никто не выбирал исходное множество отрезков и запрос <tex>q</tex>, <tex>X_i</tex> {{---}} рандомная величина зависит , зависящая только от рандомного порядка добаления добавления отрезков(если множество установлено). Будет искать математическое ожидание глубины графа. <tex>E[\sum^{n}_{i=1}X_i] = \sum^{n}_{i=1}E[X_i]</tex> Как уже упоминалось, на каждой итерации добавляется не более 3 узлов, а значит <tex>X_i \leq 3</tex>. Считая, что <tex> P_i </tex> {{--- }} вероятность того, что существует узел, который встречается при нашем запросе, созданный на <tex>i</tex>-ой итерации был добавлен узел.

<tex>\sum^{n}_{i=1}E[X_i]</tex> <= \sum^{n}_{i=1}3P_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(\Delta_q(i) \ne \Delta_q(i - 1))</tex>. Если эти два трапецоида не равны, значит, на i-ой итерации трапецоид <tex>\Delta_q(i)</tex> был одним из созданных при модификации. Заметим, что все трапецоиды, созданные на этой итерации, были смежны текущему отрезку(<tex>s_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>i</tex>-ой итерации. Тогда состояние трапецоидов никак не будет зависеть от порядка добавленных отрезков. Тогда вероятность изменения трапецоида {{---}} это его вероятность исчезнуть, если удалится <tex>s_i</tex>. Тогда переходим, к <tex>\operatorname{top} \Delta_i</tex> и т.п. так как мы уже говорили, что <tex>s_i</tex> будет определенной стороной при навигации. Отрезки добавлялись рандомно, поэтому, в качестве <tex>s_i</tex> мог быть любой отрезок из <tex>S_i</tex>. А, тогда, вероятность для всех сторон <tex>\frac1i</tex>. Суммируем по всем 4 сторонам.

Наша задача, понять чем ограничена Таким образом <tex>P_i= P( \Delta_q(i) \ne \Delta_q(i - 1)) = P( \Delta_q(i) \in \Delta_q(i - 1) ) \le \frac4i</tex>.

Пусть <tex> \Delta_qsum^{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> - трапецоид содержащий q  ===Память===Заметим, что количество трапецоидов, как мы доказали раньше, равно <tex>\mathcal{O}(n)</tex>, поэтому мы должны оценить количество узлов созданых на <tex>i</tex>-ой итерации.

Представим, что наш трапецоид <tex> \Delta_qmathrm{Mem} = \mathcal{O}(n) + \sum^{n}_{i) =1}</tex> исчез когда мы удалили текущий отрезок. Он мог исчезнуть только если исчез один из указателей(top, bottom ...). Рассмотрим вероятность этого исчезновения. Так как отрезки мы добавляли в рандомном порядке, вероятность текущему отрезку быть top или bottom равна 1/количество узлов созданное на <tex>i. leftp исчезает только в том случаи если leftp была концом теккущего отрезка. А потому эта вероятность тоже равна 1</i. Аналогично для rightp.tex>-ой итерации

Таким образом P_i = P(Обозначив за <tex> \Delta_q(i) k_i</tex> \ne количество узлов, созданное на <tex> \Delta_q(i - 1) </tex>) = P(<tex> \Delta_q(i) </tex> \in <tex> \Delta_q(i - 1) </tex>) <= 4/iой итерации

А тогда <tex>\sum^mathrm{nMem}_{i=1}E[X_i]</tex> <= \sum^mathcal{nO}_{i=1}3P_i</tex> <= <tex>\sum^{n}_{i=1}12/i <=12\sum^{n}_{i=1}(1/i) \approx 12*log(n)</tex>

УраИз этих двух выводов очевидно следует, что время построения карты равно <tex>\mathcal{O}(n \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] [[Категория: Вычислительная геометрия]]