Редактирование: Трапецоидная карта

Перейти к: навигация, поиск

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 2: Строка 2:
 
<includeonly>[[Категория: В разработке]]</includeonly>
 
<includeonly>[[Категория: В разработке]]</includeonly>
  
Трапецоидная карта {{---}} структура данных для локализации в конфигурации отрезков.
+
Трапецоидная карта {{---}} геометрическая структура позволяющая локализоваться на площади за <tex>\mathcal{O}(\log(n))</tex>.
 
==Постановка задачи==
 
==Постановка задачи==
Есть конфигурация отрезков на плоскости и dcel-подобная структура, позволяющая по ребру из конфигурации получить соответствующий face.
+
<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 - 1$, $i$-мерные объекты, ограничивающие их.
 +
}}
 +
 
 +
{{Определение
 +
|id=primitives
 +
|definition =
 +
'''Вершина''' (англ. ''vertex'') — ячейка размерности 0. <br>
 +
'''Ребро''' (англ. ''edge'') — ячейка размерности 1. <br>
 +
'''Грань''' (англ. ''face'') — ячейка размерности 2. <br>
 +
'''Сторона''' (англ. ''facet'') — ячейка размерности d-1.
 +
}}
 +
 +
</wikitex>
 +
Предположим, у нас есть наши координаты, и есть двумерная конфигурация. Наша задача выдать грань содержащую точку. Пусть каждая грань  конфигурации является трапецоидом. Тогда каждая грань однозначно задается двумя отрезками ограничивающими эту грань(боковые стороны трапеции).
 +
Таким образом задача локализации точки сводится к тому, что нужно выдать два отрезка между которыми находится точка.
 +
 
 +
Мы можем найти по карте наше местоположение и сказать в какой стране мы находимся.
 +
Области задаются замкнутыми ломаными.
  
 
==Структура данных==
 
==Структура данных==
Строка 19: Строка 48:
 
  |statement= Любой <tex>\operatorname{face}</tex> трапецоидной карты ограничен одним или двумя вертикальными отрезками и обязательно двумя не вертикальными отрезками.
 
  |statement= Любой <tex>\operatorname{face}</tex> трапецоидной карты ограничен одним или двумя вертикальными отрезками и обязательно двумя не вертикальными отрезками.
 
}}
 
}}
[[Файл:Trapezoidmapnavigationshagal.png|650px|thumb|right|Трапецоидная карта]]
+
[[Файл:Trapezoidmapnavigationshagal.png|650px|thumb|right|навигация в трапецоидной карте]]
  
 
Именно отсюда берется название структуры, так как любой <tex>\operatorname{face}</tex> либо трапеция, либо треугольник.
 
Именно отсюда берется название структуры, так как любой <tex>\operatorname{face}</tex> либо трапеция, либо треугольник.
Строка 55: Строка 84:
  
 
}}
 
}}
Хранить трапецоиды можно в чем угодно. Вместе с самим трапецоидом, стоит хранить <tex>\operatorname{leftp}</tex>, <tex>\operatorname{rightp}</tex>, <tex>\operatorname{top}</tex> и <tex>\operatorname{bottom}</tex>. Также следует хранить соседей трапецоида.
+
Хранить трапецоиды можно в чем угодно. Вместе с самим трапецоидом, стоит хранить <tex>\operatorname{leftp}</tex>, <tex>\operatorname{rightp}</tex>, <tex>\operatorname{top}</tex> и <tex>\operatorname{bottom}</tex>. Так же следует хранить соседей трапецоида.
  
  
Строка 68: Строка 97:
 
*Второй тип узла - отрезок.
 
*Второй тип узла - отрезок.
 
 
Во время запроса мы двигаемся по графу от его корня до момента, когда окажемся в листе. Это и будет означать, что точка находится внутри трапецоида.
+
Во время запроса мы двигаемся по графу от его корня до момента, когда окажемся в листе. Это и будет означать, что точка находится внутри трапецоида.
 +
 +
Если мы находимся не в листе, то мы должны опредетиться, в каком из детей мы окажемся дальше.
 +
  
 
Еcть два правила:
 
Еcть два правила:
 
 
 
*Если текущий узел соответсвует вершине, то выбираем лексикографически нужную.
 
*Если текущий узел соответсвует вершине, то выбираем лексикографически нужную.
*Если текущий узел соответствует отрезку, то смотрим, выше или ниже мы находимся(проверка по <tex>y</tex>-координате).
+
*Если текущий узел соответствует отрезку, то смотрим выше или ниже мы находимся(проверка по <tex>y</tex>-координате).
  
 
==Алгоритм==
 
==Алгоритм==
 
[[Файл:Trapezoidmapnotsuchbadcaseshagal.png|400px|thumb|right|простой случай]]
 
[[Файл:Trapezoidmapnotsuchbadcaseshagal.png|400px|thumb|right|простой случай]]
Во время построения трапецоидной карты(в дальнейшем <tex>T</tex>) алгоритм также строит структуру для поиска.
+
Во время построения трапецоидной карты(в дальнейшем <tex>T</tex>) алгоритм так же строит структуру для поиска.
  
Наш алгоритм добавляет отрезки по одному и, после каждого добавления, модифицирует <tex>T</tex> и <tex>D</tex>.
+
Наш алгоритм добавляет отрезки по одному и, после каждого добавления, модидицирует <tex>T</tex> и <tex>D</tex>.
  
 
''Порядок добавления отрезков''
 
''Порядок добавления отрезков''
  
От порядка добавления зависит время запроса. Как? Время запроса пропорционально глубине графа.
+
От порядка добавления зависит время запроса. Как? Время запрос пропорцианально глубине графа.
  
Считается, что, если добавлять отрезки в случайном порядке, то время будет хорошим. Почему и какое время будет достигаться, расписано дальше.
+
Считается, что если добавлять отрезки в случайном порядке, то время будет хорошим. Почему и какое время будет достигаться, расписано дальше.
  
 
===Алгоритм===
 
===Алгоритм===
Строка 101: Строка 133:
 
Чтобы модифицировать карту, мы должны понять, где произошло изменение.
 
Чтобы модифицировать карту, мы должны понять, где произошло изменение.
  
Оно произошло в тех трапецоидах, которые пересек текущий отрезок.
+
Оно произошло в тех трапецоидах, которые пересек текущий отрезок, или можно сказать, что трапецоид с <tex>i-1</tex>-ой итерации не будет в <tex>i</tex>-ой только если его пересек отрезок.
  
 
Пусть якобы есть множество трапецоидов <tex>\Delta_0, \Delta_1, \Delta_2 \ldots \Delta_k</tex>, упорядоченное по <tex>s_i</tex>
 
Пусть якобы есть множество трапецоидов <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>\Delta_{j+1}</tex> {{---}} один из правых соседей <tex>\Delta_j</tex>. Так же, при этом не сложно понять, каким соседом он является.
  
 
Если <tex>\operatorname{rightp} \Delta_j</tex> лежит выше <tex>s_i</tex>, то сосед нижний и наоборот.
 
Если <tex>\operatorname{rightp} \Delta_j</tex> лежит выше <tex>s_i</tex>, то сосед нижний и наоборот.
  
Это значит, что, если мы знаем первый трапецоид, то мы можем найти остальные, просто обходя по карте соседей справа.
+
Это значит, что, если мы знаем первый трапецоид, то мы можем найти остальные просто обходя по карте соседей справа.
  
 
Чтобы найти первый трапецоид, нужно просто локализовать правый конец в текущей карте.
 
Чтобы найти первый трапецоид, нужно просто локализовать правый конец в текущей карте.
Строка 125: Строка 157:
 
В случае, если какие-то трапецоиды выродятся в треугольники, будет не четыре новых трапецоида, а 2 или 3.
 
В случае, если какие-то трапецоиды выродятся в треугольники, будет не четыре новых трапецоида, а 2 или 3.
 
*Находим множество трапецоидов, которых пересек отрезок (в данном случаи он один).
 
*Находим множество трапецоидов, которых пересек отрезок (в данном случаи он один).
*Находим этот трапецоид в <tex> T </tex> и добавляем вместо него нужные трапецоиды.
+
*Находим этот трапецоид в <tex> T </tex> и добавили вместо него нужные трапецоиды.
*Спускаемся по <tex> D </tex> до соответствующего трапецоида.
+
*Спускаемся по <tex> D </tex> до соответвствующего трапецоида.
*Вместо этого трапецоида добавляем ключ "x" и строим оттуда часть структуры, как показано на картинке.   
+
*Вместо этого трапецоида добавляем ключ "x" и строим от туда часть структуры как показано на картинке.   
  
  
 
*'''Сложный''' {{---}} отрезок пересекает сразу несколько трапецоидов.
 
*'''Сложный''' {{---}} отрезок пересекает сразу несколько трапецоидов.
  
Итак, наш отрезок пересекает трапецоиды <tex>\Delta_0, \Delta_1, \Delta_2 ... \Delta_k</tex>.
+
Итак наш отрезок пересекает трапецоиды <tex>\Delta_0, \Delta_1, \Delta_2 ... \Delta_k</tex>.
  
 
Сначала добавляем вертикальные лучи из концов текущего отрезка. Это нужно, чтобы модифицировать <tex>\Delta_0</tex> и <tex>\Delta_k</tex>.
 
Сначала добавляем вертикальные лучи из концов текущего отрезка. Это нужно, чтобы модифицировать <tex>\Delta_0</tex> и <tex>\Delta_k</tex>.
Строка 143: Строка 175:
 
*Находим множество трапецоидов, которых пересек отрезок.
 
*Находим множество трапецоидов, которых пересек отрезок.
 
*Находим этот трапецоид в <tex> T </tex> и добавили вместо него нужные трапецоиды.
 
*Находим этот трапецоид в <tex> T </tex> и добавили вместо него нужные трапецоиды.
*Спускаемся по <tex> D </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> p </tex>.
  
 
Скажем, что наша точка лежит правее, чем та, которая уже есть. В случае, если мы попали на уже созданный отрезок, мы скажем, что находимся, например, ниже его.  
 
Скажем, что наша точка лежит правее, чем та, которая уже есть. В случае, если мы попали на уже созданный отрезок, мы скажем, что находимся, например, ниже его.  
Строка 198: Строка 198:
 
==Асимптотика==
 
==Асимптотика==
 
===Запрос===
 
===Запрос===
Предположим, у нас есть запрос на локализацию точки <tex>q</tex>. Время, затраченное на этот запрос, будет линейно зависеть от глубины графа.  
+
Предположим у нас есть запрос на локализацию точки <tex>q</tex>. Время, затраченное, на этот запрос будет линейно зависит от глубины графа.  
  
 
При добавлении в карту очередного отрезка(в дальнейшем, итерация алгоритма), глубина графа увеличивается максимум на 3. Из этого мы можем сделать простую оценку.
 
При добавлении в карту очередного отрезка(в дальнейшем, итерация алгоритма), глубина графа увеличивается максимум на 3. Из этого мы можем сделать простую оценку.
Строка 204: Строка 204:
 
Наибольшее время на запрос, которое мы можем потратить {{---}} <tex>3n</tex>.  
 
Наибольшее время на запрос, которое мы можем потратить {{---}} <tex>3n</tex>.  
  
Как говорилось раньше, отрезки мы добавляем в случайном порядке, а потому редко будет самый ужасный случай, и, с вероятностных точек зрения, время на запрос будет меньше.
+
Как говорилось раньше, отрезки мы добавляем в случайном порядке, а потому, редко будет самый ужасный случай и, с вероятностных точек зрения, время на запрос будет меньше.
  
 
Рассмотрим путь, пройденный точкой по графу. Каждый узел был создан на какой-то итерации цикла. Обозначим за <tex>X_i</tex> количество узлов, созданных на итерации <tex>i</tex>.
 
Рассмотрим путь, пройденный точкой по графу. Каждый узел был создан на какой-то итерации цикла. Обозначим за <tex>X_i</tex> количество узлов, созданных на итерации <tex>i</tex>.
Строка 228: Строка 228:
 
Таким образом <tex>P_i = P(\Delta_q(i) \ne \Delta_q(i - 1))</tex>.
 
Таким образом <tex>P_i = P(\Delta_q(i) \ne \Delta_q(i - 1))</tex>.
 
  
 
  
Если эти два трапецоида не равны, значит, на i-ой итерации трапецоид <tex>\Delta_q(i)</tex> был одним из созданных при модификации.
+
Если эти два трапеецоида не равны, значит на i-ой итерации трапецоид <tex>\Delta_q(i)</tex> был одним из созданных при модификации.
  
 
Заметим, что все трапецоиды, созданные на этой итерации, были смежны текущему отрезку(<tex>s_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>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>i</tex>-ой итерации. Тогда состояние трапецоидов никак не будет зависеть от порядка добавленных отрезков.
  
Тогда вероятность изменения трапецоида {{---}} это его вероятность исчезнуть, если удалится <tex>s_i</tex>.
+
Тогда, вероятность изменения трапецоида {{---}} это его вероятность исчезнуть, если удалится <tex>s_i</tex>.
  
 
Тогда переходим, к <tex>\operatorname{top} \Delta_i</tex> и т.п. так как мы уже говорили, что <tex>s_i</tex> будет определенной стороной при навигации.
 
Тогда переходим, к <tex>\operatorname{top} \Delta_i</tex> и т.п. так как мы уже говорили, что <tex>s_i</tex> будет определенной стороной при навигации.
Строка 294: Строка 294:
 
     Удаляем это множество из карты и добавляем новые узлы появившиеся из-за <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
  
 
==Ссылки==
 
==Ссылки==
 
[http://graphics.stanford.edu/courses/cs268-09-winter/  Lecture notes from stanford, Seidel]
 
[http://graphics.stanford.edu/courses/cs268-09-winter/  Lecture notes from stanford, Seidel]
 
[[Категория: Вычислительная геометрия]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: