1632
правки
Изменения
м
===Поиск трапецоидов, которых пересекает отрезок===
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
rollbackEdits.php mass rollback
}}
Хранить трапецоиды можно в чем угодно. Вместе с самим трапецоидом, стоит хранить <tex>\operatorname{leftp}</tex>, <tex>\operatorname{rightp}</tex>, <tex>\operatorname{top}</tex> и <tex>\operatorname{bottom}</tex>. Так же Также следует хранить соседей трапецоида.
*Если текущий узел соответсвует вершине, то выбираем лексикографически нужную.
*Если текущий узел соответствует отрезку, то смотрим , выше или ниже мы находимся(проверка по <tex>y</tex>-координате).
==Алгоритм==
[[Файл:Trapezoidmapnotsuchbadcaseshagal.png|400px|thumb|right|простой случай]]
Во время построения трапецоидной карты(в дальнейшем <tex>T</tex>) алгоритм так же также строит структуру для поиска.
Наш алгоритм добавляет отрезки по одному и, после каждого добавления, модидицирует модифицирует <tex>T</tex> и <tex>D</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>\operatorname{rightp} \Delta_j</tex> лежит выше <tex>s_i</tex>, то сосед нижний и наоборот.
Это значит, что, если мы знаем первый трапецоид, то мы можем найти остальные , просто обходя по карте соседей справа.
Чтобы найти первый трапецоид, нужно просто локализовать правый конец в текущей карте.
*Находим множество трапецоидов, которых пересек отрезок (в данном случаи он один).
*Находим этот трапецоид в <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> 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>
==Случай коллизии==
Рассмотрим момент, когда мы мы строим карты. Мы должны добавить очередной отрезок.
Предположим, левый конец отрезка лежит на одной вертикале вертикали с уже добавленной в карту точкой <tex> p </tex>.
Скажем, что наша точка лежит правее, чем та, которая уже есть. В случае, если мы попали на уже созданный отрезок, мы скажем, что находимся, например, ниже его.
==Асимптотика==
===Запрос===
Предположим , у нас есть запрос на локализацию точки <tex>q</tex>. Время, затраченное, на этот запрос , будет линейно зависит зависеть от глубины графа.
При добавлении в карту очередного отрезка(в дальнейшем, итерация алгоритма), глубина графа увеличивается максимум на 3. Из этого мы можем сделать простую оценку.
Наибольшее время на запрос, которое мы можем потратить {{---}} <tex>3n</tex>.
Как говорилось раньше, отрезки мы добавляем в случайном порядке, а потому, редко будет самый ужасный случай , и, с вероятностных точек зрения, время на запрос будет меньше.
Рассмотрим путь, пройденный точкой по графу. Каждый узел был создан на какой-то итерации цикла. Обозначим за <tex>X_i</tex> количество узлов, созданных на итерации <tex>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> в поисковой структуре
Аналогично для просто карты
==Ссылки==
[http://graphics.stanford.edu/courses/cs268-09-winter/ Lecture notes from stanford, Seidel]
[[Категория: Вычислительная геометрия]]
