Трапецоидная карта — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Асимптотика)
м (rollbackEdits.php mass rollback)
 
(не показана 81 промежуточная версия 14 участников)
Строка 1: Строка 1:
Трапецоидная карта - геометрическая структура позволяющая локализоваться на площади за <tex>O(log(n))</tex>.
+
<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>
 +
 
 +
Трапецоидная карта {{---}} структура данных для локализации в конфигурации отрезков.
 
==Постановка задачи==
 
==Постановка задачи==
  Предположим, у нас есть наши координаты, и есть карта мира.
+
Есть конфигурация отрезков на плоскости и dcel-подобная структура, позволяющая по ребру из конфигурации получить соответствующий face.
 
+
Трапецоидная карта позволяет найти ребро, до которого можно дойти от точки-запроса, не пересекая образующие конфигурацию отрезки.
  Мы можем найти по карте наше местоположение и сказать в какой области мы находимся.
 
  Области задаются отрезками.
 
 
 
  '''Формальная постановка задачи'''
 
  Есть множество отрезков на плоскости.
 
  Есть запрос (точка q), на выход подается область заданная какими-то отрезками в которой находится q.
 
  
 
==Структура данных==
 
==Структура данных==
[[Файл:Trapazoidmapshagal.jpg|650px|thumb|right|трапецоидная карта]]
+
[[Файл:Trapezoidmapshagal.png|450px|thumb|right|трапецоидная карта]]
 
  
 
*''Геометрическая''
 
*''Геометрическая''
  
У нас есть множество отрезков ограничееных оболочкой R(это не выпуклая оболочка, а просто мнимая граница плоскости за которую не вылезают отрезки)
+
У нас есть множество отрезков, ограниченных оболочкой <tex>R</tex>(это не выпуклая оболочка, а просто мнимая граница плоскости, за которую не вылезают отрезки).
+
 
Мы договариваемся что никакие две точки не лежат на одной вертикале(в противном случаи все еще противнее)
+
''Трапецоидная карта'' множества отрезков <tex>S</tex> {{---}} это множество трапецоидов построенных следующим образом, из каждой точки выпущены два луча {{---}} вверх и вниз, до первого пересечения с другим отрезком или с оболочкой <tex>R</tex>.
 
''Трапецоидная карта'' множества отрезков S - это эти отрезки + из кажой точки выпущены два луча, вверх и вниз до первого пересечения с другим отрезком или с оболочкой R.
 
 
 
 
{{Лемма  
 
{{Лемма  
  |statement= Любой face трапецоидной карты ограничен одним или двумя вертикальными отрезками и обязательно двумя не вертикальными отрезками.
+
  |statement= Любой <tex>\operatorname{face}</tex> трапецоидной карты ограничен одним или двумя вертикальными отрезками и обязательно двумя не вертикальными отрезками.
 
}}
 
}}
[[Файл:Trapezoidmapnavigationshagal.jpg|650px|thumb|right|навигация в трапецоидной карте]]
+
[[Файл:Trapezoidmapnavigationshagal.png|650px|thumb|right|Трапецоидная карта]]
  
Именно отсюда берется название стрктуры, так как любой face либо трапеция, либо треугольник.
+
Именно отсюда берется название структуры, так как любой <tex>\operatorname{face}</tex> либо трапеция, либо треугольник.
 
 
  
 
Введем обозначения для навигации по карте.
 
Введем обозначения для навигации по карте.
  
*левая граница(leftp) - точка определяющая левуюы сторону трапецоида или в случаи треугольника просто являющаяся левой вершиной.
+
*''левая граница'' (<tex>\operatorname{leftp}</tex>) {{---}} точка, определяющая левую сторону трапецоида или, в случаи треугольника, просто являющаяся левой вершиной.
*правая граница(rightp) - аналогично левой только справа.
+
*''правая граница'' (<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> пересечения вертикальных лучей из концов отрезков с другими отрезками или оболочкой
 +
*''трапецоиды''
 +
Будем смотреть на левую сторону трапецоида.  
  
*верхний отрезок(top) и нижний отрезок(bottom) - отрезки ограничивающие трапецоид сверху и снизу.
+
У каждого трапецоида есть точка <tex>\operatorname{leftp}(\Delta)</tex>. Либо это конец какого-то отрезка, либо это левый нижний угол оболочки.
  
*трапецоиды называются смежными, если имеют общую вертикальную границу.
+
При этом можно сразу сказать, что левый и нижний угол будут соответствовать только одному трапецоиду.
  
*пусть <tex>\Delta_1 и \Delta_2</tex> смежны и либо top(<tex>\Delta_1</tex>) = top(<tex>\Delta_2</tex>), либо bottom(<tex>\Delta_1</tex>) = bottom(<tex>\Delta_2</tex>)
+
Далее заметим, что правый конец отрезка может быть <tex>\operatorname{leftp}(\Delta)</tex> только для одного трапецоида.
Тогда <tex>\Delta_1</tex>,<tex>\Delta_2</tex> называют либо большими левыми соседями, либо меньшими.
 
  
 +
Левый конец может быть <tex>\operatorname{leftp}(\Delta)</tex> максимум для двух трапецоидов.
  
 +
Из этого следует, что количество трапецоидов <tex>n + 2n + 1 = 3n + 1</tex>.
  
Хранить трапецоиды можно в чем угодно. Вместе с самим трапецоидом, стоит хранить leftp, rightp, top и bottom так же следует хранить соседей трапецоида.
+
}}
 +
Хранить трапецоиды можно в чем угодно. Вместе с самим трапецоидом, стоит хранить <tex>\operatorname{leftp}</tex>, <tex>\operatorname{rightp}</tex>, <tex>\operatorname{top}</tex> и <tex>\operatorname{bottom}</tex>. Также следует хранить соседей трапецоида.
  
  
 
----
 
----
 
+
[[Файл:Trapezoidmapsearchstructureshagal.png|650px|thumb|right|навигация в трапецоидной карте]]
 
*''Поисковая структура''
 
*''Поисковая структура''
Поисковая структура(в дальнейшем <tex> D</tex>) предсталяет из себя ацикличный граф с одним корнем и каждому трапецоиду в структре соответствует один лист.
+
Поисковая структура представляет из себя ациклический граф с одним корнем и соответствующими трапецоидам листьями.
 
 
У каждого узла есль два ребенка и при этом узел может быть двух типов.
+
У каждого узла есть два ребенка. При этом узел может быть двух типов.
[[Файл:Trapezoidmapsearchstructureshagal.jpg|650px|thumb|right|навигация в трапецоидной карте]]
 
  
Первый тип узла - точка, соответствующая концу отрезка.
+
*Первый тип узла - точка, соответствующая концу отрезка.
+
*Второй тип узла - отрезок.
Второй тип узла - отрезок.
 
 
Во время запроса мы двигаемся по графу от его корня до момента, когда окажемся в листе, это и будет означать что точка находится внутри трапецоида.
 
 
Если мы находимся не в листе, то мы должны опрелетиться в каком из детей мы окажемся дальше.
 
 
 
 +
Во время запроса мы двигаемся по графу от его корня до момента, когда окажемся в листе. Это и будет означать, что точка находится внутри трапецоида.
 +
 
Еcть два правила:
 
Еcть два правила:
 
 
*Если текущий узел соответсвует вершине, то смотрим левее или провее мы находимся(проверка по x-координате).
+
*Если текущий узел соответсвует вершине, то выбираем лексикографически нужную.
 
+
*Если текущий узел соответствует отрезку, то смотрим, выше или ниже мы находимся(проверка по <tex>y</tex>-координате).
*Если текущий узел соответствует отрезку, то смотрим выше или ниже мы находимся(проверка по y-координате).
 
 
*Плохие случаи:
 
 
Мы находимся на одной вертикале с вершиной
 
 
Мы находимся на отрезке
 
 
(Решение: молиться, или просто обрабатывать вручную.)
 
  
 
==Алгоритм==
 
==Алгоритм==
[[Файл:Trapezoidmapnotsuchbadcaseshagal.jpg|400px|thumb|right|простой случай]]
+
[[Файл:Trapezoidmapnotsuchbadcaseshagal.png|400px|thumb|right|простой случай]]
Во время построения трапецоидной карты(в дальнейшем <tex> T</tex>) алгоритм так же строит структуру для поиска (в дальнейшем <tex> D</tex>).
+
Во время построения трапецоидной карты(в дальнейшем <tex>T</tex>) алгоритм также строит структуру для поиска.
 
 
Так как трапецоидная карта - геометрическая структура, а основные операции ведутся именно с поисковой, упор на неё.
 
  
Наш алгоритм добавляет отрезки по одному и после каждого добававления модидицирует <tex> T</tex> и <tex> D</tex>.
+
Наш алгоритм добавляет отрезки по одному и, после каждого добавления, модифицирует <tex>T</tex> и <tex>D</tex>.
  
 
''Порядок добавления отрезков''
 
''Порядок добавления отрезков''
  
От порядка добавления зависит время запроса. Как? Время запрос пропорцианально глубине графа.
+
От порядка добавления зависит время запроса. Как? Время запроса пропорционально глубине графа.
  
Считается, что еслли добавлять отрезки рандомно, то время будет хорошим. Почему и какое время будет рассписано дальше.
+
Считается, что, если добавлять отрезки в случайном порядке, то время будет хорошим. Почему и какое время будет достигаться, расписано дальше.
  
''Алгоритм''
+
===Алгоритм===
  
 
*Добавили отрезок.
 
*Добавили отрезок.
Строка 99: Строка 95:
 
*Удалили их.
 
*Удалили их.
  
*Создали новый трапецоиды.
+
*Создали новые трапецоиды.
[[Файл:Trpezoidmapbadcaseshagal.jpg|400px|thumb|right|сложный случай]]
+
[[Файл:Trpezoidmapbadcaseshaga.png|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>, то сосед нижний и наоборот.
  
----
+
Это значит, что, если мы знаем первый трапецоид, то мы можем найти остальные, просто обходя по карте соседей справа.
 +
 
 +
Чтобы найти первый трапецоид, нужно просто локализовать правый конец в текущей карте.
  
 +
===update===
 
Рассмотрим подробнее последние две части
 
Рассмотрим подробнее последние две части
  
 
Есть два случая.
 
Есть два случая.
*Простой - отрезок не пересекает ни одного трапецоида, то есть целеком внутри.
+
*'''Простой''' {{---}} отрезок не пересекает ни одного трапецоида, то есть целиком внутри.
  
 
Тогда удаляем этот старый трапецоид и на его место ставим дерево из двух концов отрезка, отрезка и четырех образовавшихся трапецоидов.
 
Тогда удаляем этот старый трапецоид и на его место ставим дерево из двух концов отрезка, отрезка и четырех образовавшихся трапецоидов.
Строка 113: Строка 123:
 
Важно не забыть правильно определить соседей новых трапецоидов.
 
Важно не забыть правильно определить соседей новых трапецоидов.
  
 +
В случае, если какие-то трапецоиды выродятся в треугольники, будет не четыре новых трапецоида, а 2 или 3.
 +
*Находим множество трапецоидов, которых пересек отрезок (в данном случаи он один).
 +
*Находим этот трапецоид в <tex> T </tex> и добавляем вместо него нужные трапецоиды.
 +
*Спускаемся по <tex> D </tex> до соответствующего трапецоида.
 +
*Вместо этого трапецоида добавляем ключ "x" и строим оттуда часть структуры, как показано на картинке. 
 +
 +
 +
*'''Сложный''' {{---}} отрезок пересекает сразу несколько трапецоидов.
 +
 +
Итак, наш отрезок пересекает трапецоиды <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> и добавили вместо него нужные трапецоиды.
 +
*Спускаемся по <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>
  
В случаи если какие-то трапецоиды выродятся в треугольники будет не четыре новых трапецоида , а 2 или 3. Слава богу это не самая большая проблема.
+
==Случай коллизии==
 +
Рассмотрим момент, когда мы строим карты. Мы должны добавить очередной отрезок.
  
*Сложный - отрезок пересекает сразу несколько трапецоидов.
+
Предположим, левый конец отрезка лежит на одной вертикали с уже добавленной в карту точкой <tex> p </tex>.
  
Итак наш отрезок пересекает трапецоиды <tex>\Delta_0, \Delta_1, \Delta_2 ... \Delta_k</tex>.
+
Скажем, что наша точка лежит правее, чем та, которая уже есть. В случае, если мы попали на уже созданный отрезок, мы скажем, что находимся, например, ниже его.  
  
Сначала добавляем вертикальные лучи из концов текущего отрезка. Это нужно, чтобы модифицировать <tex>\Delta_0 и \Delta_k</tex>.
+
Что при этом произойдет.
Теперь мы должны удалить соответствующие листья и на новые которые появились из-за изменения лучей.
 
  
Дальше мы модифицуруем вертикальные лучи, которые пересекают текущий отрезок. Этот процесс происходит достаточно быстро, так мы храним много информацию об этих лучах в  
+
*С геометрической точки зрения, появится ещё несколько трапецоидов, как в случае, если бы вновь добавленная точка была правее на <tex> \varepsilon \rightarrow 0</tex>.
  
По хорошему то как этот происходит просто ужасно и видеть это не хочется, а все потому, что много что добавляется много новых узлов.
+
А значит, у трапецоида по прежнему не более двух правых соседей.
  
<tex>\Delta_0, \Delta_1, \Delta_2 ... \Delta_k</tex>.
+
*С точки зрения поисковой структуры мы по-прежнему можем локализоваться. По крайней мере, узел, соответствующий точке <tex> p </tex> будет иметь правым сыном нашу точку.
  
 +
Итого, слова "трапецоидные карты просты отсутствие случаев" появляются именно отсюда, так как, казалось бы, неприятный случай будет прописан заменой <tex>\textless </tex>
 +
на <tex> \le </tex>
  
 
==Асимптотика==
 
==Асимптотика==
 
===Запрос===
 
===Запрос===
Запрос производится за время пропорцианальное глубине графа(поисковой структуры). Если считать, что на каждой итерации глубина увеливается максимум на 3, то время работы в худшем случаи будет O(3n). Но мы вспоминаем, что порядок добавления отрезков рандомный, а потому наврядли всегда будет худший случай.
+
Предположим, у нас есть запрос на локализацию точки <tex>q</tex>. Время, затраченное на этот запрос, будет линейно зависеть от глубины графа.
 +
 
 +
При добавлении в карту очередного отрезка(в дальнейшем, итерация алгоритма), глубина графа увеличивается максимум на 3. Из этого мы можем сделать простую оценку.
 +
 
 +
Наибольшее время на запрос, которое мы можем потратить {{---}} <tex>3n</tex>.  
  
Рассмотрим путь пройденный точкой по графу. Каждый узел был создан на какой-то итерации цикла. Обозначим за <tex>X_i</tex> - количество узлов созданных на итерации i.
+
Как говорилось раньше, отрезки мы добавляем в случайном порядке, а потому редко будет самый ужасный случай, и, с вероятностных точек зрения, время на запрос будет меньше.
  
Эта величина зависит только от порядка добаления отрезков(если множество установлено).
+
Рассмотрим путь, пройденный точкой по графу. Каждый узел был создан на какой-то итерации цикла. Обозначим за <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>
 
<tex>E[\sum^{n}_{i=1}X_i] = \sum^{n}_{i=1}E[X_i]</tex>
  
Считая, что <tex> P_i </tex> - вероятность того, что на i-ой итерации был добавлен узел.
+
Как уже упоминалось, на каждой итерации добавляется не более 3 узлов, а значит <tex>X_i \leq 3</tex>.
 +
 
 +
Считая, что <tex>P_i</tex> {{---}} вероятность того, что существует узел, который встречается при нашем запросе, созданный на <tex>i</tex>-ой итерации.
 
 
 
<tex>\sum^{n}_{i=1}E[X_i] <= \sum^{n}_{i=1}3P_i</tex>
 
<tex>\sum^{n}_{i=1}E[X_i] <= \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>\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>-ой итерации.
 
 
Наша задача, понять чем ограничена P_i.
+
А результирующее выражение для памяти тогда будет
 
 
Пусть <tex> \Delta_q(i) </tex> - трапецоид содержащий q на i-ой итерации.
+
<tex>\mathrm{Mem} = \mathcal{O}(n) + \sum^{n}_{i=1}</tex> количество узлов созданное на <tex>i</tex>-ой итерации
 
 
Скажем, что произошло изменение на i-ой итерации если <tex> \Delta_q(i) </tex> != <tex> \Delta_q(i - 1) </tex>
+
Обозначив за <tex>k_i</tex> количество узлов, созданное на <tex>i</tex>-ой итерации
 +
 +
<tex>\mathrm{Mem} = \mathcal{O}(n) + \sum^{n}_{i=1} E[k_i]</tex>
  
Таким образом P_i = P(<tex> \Delta_q(i) \ne \Delta_q(i - 1) </tex>).
+
Введем новую функцию для трапецоида <tex> \Delta </tex> и отрезка s.
  
Если эти два трапеецоида не равны, значит на i-ой итерации трапецоид <tex> \Delta_q(i) </tex> был одним из созданных при моификации.
+
Выделим множество <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.
  
Либо этот отрезок был top или bottom, либо его концы были leftp или rightp.
+
<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>\mathrm{Mem} = \mathcal{O}(n)</tex>
 
 
Представим, что наш трапецоид <tex> \Delta_q(i) </tex> исчез когда мы удалили текущий отрезок. Он мог исчезнуть только если исчез один из указателей(top, bottom ...).
+
Из этих двух выводов очевидно следует, что время построения карты равно <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
  
Рассмотрим вероятность этого исчезновения.
+
===Построение трапецоидной карты===
  
Так как отрезки мы добавляли в рандомном порядке, вероятность текущему отрезку быть top или bottom равна 1/i.
+
TrapezoidMap(S - segments)
 +
  Строим оболочку(просто находим крайние точки множества отрезков по четырем направлениям)
 +
  Строим рандомную перестановку отрезков
 +
  for для всех
 +
    ищем множество трапецоидов пересекаемых отрезком <tex>s_i</tex>. //это специальная функция//
 +
    Удаляем это множество из карты и добавляем новые узлы появившиеся из-за <tex>s_i</tex> в поисковой структуре
 +
    Аналогично для просто карты
  
leftp исчезает только в том случаи если leftp была концом теккущего отрезка. А потому эта вероятность тоже равна 1/i. Аналогично для rightp.
+
==Ссылки==
+
[http://graphics.stanford.edu/courses/cs268-09-winter/ Lecture notes from stanford, Seidel]
Таким образом P_i = P(<tex> \Delta_q(i) \ne \Delta_q(i - 1) </tex>) = P(<tex> \Delta_q(i)  \in  \Delta_q(i - 1) </tex>) <= 4/i
+
 
+
[[Категория: Вычислительная геометрия]]
<tex>\sum^{n}_{i=1}E[X_i]</tex> <= <tex>\sum^{n}_{i=1}3P_i <= \sum^{n}_{i=1}12/i <=12\sum^{n}_{i=1}(1/i) \approx 12*log(n)</tex>
 
 
Ура
 

Текущая версия на 19:21, 4 сентября 2022

Эта статья находится в разработке!


Трапецоидная карта — структура данных для локализации в конфигурации отрезков.

Постановка задачи

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

Структура данных

трапецоидная карта
  • Геометрическая

У нас есть множество отрезков, ограниченных оболочкой [math]R[/math](это не выпуклая оболочка, а просто мнимая граница плоскости, за которую не вылезают отрезки).

Трапецоидная карта множества отрезков [math]S[/math] — это множество трапецоидов построенных следующим образом, из каждой точки выпущены два луча — вверх и вниз, до первого пересечения с другим отрезком или с оболочкой [math]R[/math].

Лемма:
Любой [math]\operatorname{face}[/math] трапецоидной карты ограничен одним или двумя вертикальными отрезками и обязательно двумя не вертикальными отрезками.
Трапецоидная карта

Именно отсюда берется название структуры, так как любой [math]\operatorname{face}[/math] либо трапеция, либо треугольник.


Введем обозначения для навигации по карте.

  • левая граница ([math]\operatorname{leftp}[/math]) — точка, определяющая левую сторону трапецоида или, в случаи треугольника, просто являющаяся левой вершиной.
  • правая граница ([math]\operatorname{rightp}[/math]) — аналогично левой, только справа.
  • верхний отрезок ([math]\operatorname{top}[/math]) и нижний отрезок([math]\operatorname{bottom}[/math]) — отрезки, ограничивающие, трапецоид сверху и снизу.
  • трапецоиды называются смежными, если имеют общую вертикальную границу.
  • пусть [math]\Delta_1[/math] и [math]\Delta_2[/math] смежны и либо [math]\operatorname{top}(\Delta_1) = \operatorname{top}(\Delta_2)[/math], либо [math]\operatorname{bottom}(\Delta_1) = \operatorname{bottom}(\Delta_2)[/math]. Тогда [math]\Delta_1[/math] и [math]\Delta_2[/math] называют либо нижними, либо верхними левыми соседями.


Теорема:
Трапецоидная карта, построенная на [math]n[/math] отрезках содержит максимум [math]6n+4[/math] вершины и максимум [math]3n+1[/math] трапецоид.
Доказательство:
[math]\triangleright[/math]
  • вершины, а точнее откуда они берутся.
    • 4 вершины уходит на оболочку [math]R[/math]
    • [math]2 \cdot n[/math] концы отрезков
    • [math]2 \cdot 2n[/math] пересечения вертикальных лучей из концов отрезков с другими отрезками или оболочкой
  • трапецоиды

Будем смотреть на левую сторону трапецоида.

У каждого трапецоида есть точка [math]\operatorname{leftp}(\Delta)[/math]. Либо это конец какого-то отрезка, либо это левый нижний угол оболочки.

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

Далее заметим, что правый конец отрезка может быть [math]\operatorname{leftp}(\Delta)[/math] только для одного трапецоида.

Левый конец может быть [math]\operatorname{leftp}(\Delta)[/math] максимум для двух трапецоидов.

Из этого следует, что количество трапецоидов [math]n + 2n + 1 = 3n + 1[/math].
[math]\triangleleft[/math]

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



навигация в трапецоидной карте
  • Поисковая структура

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

У каждого узла есть два ребенка. При этом узел может быть двух типов.

  • Первый тип узла - точка, соответствующая концу отрезка.
  • Второй тип узла - отрезок.

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

Еcть два правила:

  • Если текущий узел соответсвует вершине, то выбираем лексикографически нужную.
  • Если текущий узел соответствует отрезку, то смотрим, выше или ниже мы находимся(проверка по [math]y[/math]-координате).

Алгоритм

простой случай

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

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

Порядок добавления отрезков

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

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

Алгоритм

  • Добавили отрезок.
  • Нашли все трапецоиды, которые пересек новый отрезок.
  • Удалили их.
  • Создали новые трапецоиды.
сложный случай

Поиск трапецоидов, которые пересек отрезок

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

Оно произошло в тех трапецоидах, которые пересек текущий отрезок.

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

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

Если [math]\operatorname{rightp} \Delta_j[/math] лежит выше [math]s_i[/math], то сосед нижний и наоборот.

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

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

update

Рассмотрим подробнее последние две части

Есть два случая.

  • Простой — отрезок не пересекает ни одного трапецоида, то есть целиком внутри.

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

Важно не забыть правильно определить соседей новых трапецоидов.

В случае, если какие-то трапецоиды выродятся в треугольники, будет не четыре новых трапецоида, а 2 или 3.

  • Находим множество трапецоидов, которых пересек отрезок (в данном случаи он один).
  • Находим этот трапецоид в [math] T [/math] и добавляем вместо него нужные трапецоиды.
  • Спускаемся по [math] D [/math] до соответствующего трапецоида.
  • Вместо этого трапецоида добавляем ключ "x" и строим оттуда часть структуры, как показано на картинке.


  • Сложный — отрезок пересекает сразу несколько трапецоидов.

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

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

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


[math]\Delta_0, \Delta_1, \Delta_2 \ldots \Delta_k[/math].

  • Находим множество трапецоидов, которых пересек отрезок.
  • Находим этот трапецоид в [math] T [/math] и добавили вместо него нужные трапецоиды.
  • Спускаемся по [math] D [/math] до соответствующих трапецоидов.
  • Вместо них добавляем новые ключи, как показано на картинке.

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

Модификация трапецоидной карты

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

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

 Update(Segment s)
 
 Point p [math]\leftarrow[/math] s.start
 Point q [math]\leftarrow[/math] s.finish
 Находим первый трапецоид [math]\Delta_{0}[/math]
 [math]\Delta_{temp}[/math]
 
 while  q справа от rightp([math]\Delta_{0}[/math])
   
   if [math]\Delta_{0}[/math] ниже [math] s_{i} [/math]
     [math]\Delta_{temp}[/math] нижний правый сосед [math]\Delta_{0}[/math] 
   else 
     [math]\Delta_{temp}[/math] верхний правый сосед [math]\Delta_{0}[/math] 
   
   Модифицируем [math]\Delta_{0}[/math] 
    
   [math]\Delta_{0} \leftarrow \Delta_{temp}[/math]

Случай коллизии

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

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

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

Что при этом произойдет.

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

А значит, у трапецоида по прежнему не более двух правых соседей.

  • С точки зрения поисковой структуры мы по-прежнему можем локализоваться. По крайней мере, узел, соответствующий точке [math] p [/math] будет иметь правым сыном нашу точку.

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

Асимптотика

Запрос

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

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

Наибольшее время на запрос, которое мы можем потратить — [math]3n[/math].

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

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

Так как никто не выбирал исходное множество отрезков и запрос [math]q[/math], [math]X_i[/math] — рандомная величина, зависящая только от рандомного порядка добавления отрезков.

[math]E[\sum^{n}_{i=1}X_i] = \sum^{n}_{i=1}E[X_i][/math]

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

Считая, что [math]P_i[/math] — вероятность того, что существует узел, который встречается при нашем запросе, созданный на [math]i[/math]-ой итерации.

[math]\sum^{n}_{i=1}E[X_i] \lt = \sum^{n}_{i=1}3P_i[/math]

Начинаем оценивать [math] P_i [/math].

Что значит, что узел был создан на [math]i[/math]-ой итерации и встретился при запросе [math]q[/math]?

Это значит, что на [math]i-1[/math]-ой итерации мы локализовывали [math]q[/math] в трапецоиде [math]\Delta_q(i-1)[/math],а на [math]i[/math]-ой итерации уже в трапецоиде [math] \Delta_q(i) [/math] и эти два трапецоида разные.

То есть, после добавления непонятно чего в карту, трапецоид изменился.

Таким образом [math]P_i = P(\Delta_q(i) \ne \Delta_q(i - 1))[/math].

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

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

Значит, либо [math]s_i = \operatorname{top} \Delta_i[/math] или [math]\operatorname{bottom} \Delta_i[/math], либо концы [math]s_i = \operatorname{leftp} \Delta_i[/math] или [math]\operatorname{rightp} \Delta_i[/math].

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

Тогда вероятность изменения трапецоида — это его вероятность исчезнуть, если удалится [math]s_i[/math].

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

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

Суммируем по всем 4 сторонам.

Таким образом [math]P_i = P( \Delta_q(i) \ne \Delta_q(i - 1)) = P( \Delta_q(i) \in \Delta_q(i - 1) ) \le \frac4i[/math]

[math]\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)[/math]

Память

Заметим, что количество трапецоидов, как мы доказали раньше, равно [math]\mathcal{O}(n)[/math], поэтому мы должны оценить количество узлов созданых на [math]i[/math]-ой итерации.

А результирующее выражение для памяти тогда будет

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

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

[math]\mathrm{Mem} = \mathcal{O}(n) + \sum^{n}_{i=1} E[k_i][/math]

Введем новую функцию для трапецоида [math] \Delta [/math] и отрезка s.

Выделим множество [math] S_i \in S [/math]. Пусть [math] s \in S_i [/math] и [math] \Delta \in T(S_i) [/math].

[math] \delta(\Delta, s) [/math] равна 1, если при удалении [math] s [/math] из [math] S_i [/math] [math], \Delta [/math] удалится, иначе [math] \delta [/math] равна 0.

[math]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)[/math]

А тогда [math]\mathrm{Mem} = \mathcal{O}(n)[/math]

Из этих двух выводов очевидно следует, что время построения карты равно [math]\mathcal{O}(n \log n)[/math].

Реализация

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

Класс "трапецоид"

struct Trapezoid
  Trapezoid next
  Trapezoid up
  Trapezoid down
  Trapezoid end
  Segment top
  Segment bottom
  Point left
  Point right

Построение трапецоидной карты

TrapezoidMap(S - segments)
  Строим оболочку(просто находим крайние точки множества отрезков по четырем направлениям)
  Строим рандомную перестановку отрезков
  for для всех
    ищем множество трапецоидов пересекаемых отрезком [math]s_i[/math]. //это специальная функция//
    Удаляем это множество из карты и добавляем новые узлы появившиеся из-за [math]s_i[/math] в поисковой структуре
    Аналогично для просто карты

Ссылки

Lecture notes from stanford, Seidel