Викиконспекты - Вклад участника [ru]

Вычислительная геометрия

2012-03-02T17:35:38Z

94.25.194.87: /* Конспекты */

== Конспекты ==

* [[Представление чисел с плавающей точкой]]
* [[Предикат "левый поворот"]]
* [[Интервальная арифметика]]
* [[Adaptive precision arithmetic]]
* [[Алгоритм Бентли-Оттмана]]
* [[Конфигурация]]
* [[Трапецоидная карта]]
* [[Алгоритм нахождения кратчайших путей вокруг полигональных препятствий]]
* [[Пересечение окружностей]]
* [[Упрощение полигональной цепи]]
* [[Список тем]]

== Инструкции ==
* [[План курса]]
* [[Написание условий задач]]

== Сдача конспектов ==

* [https://docs.google.com/spreadsheet/pub?key=0Ar0nZy99lVSvdDIzR1E5R1MwdDN0MXBiOHRyQ2NVV1E Распределение тем конспектов]
* Для сдачи конспекта необходимо сообщить об этом одному из редакторов:
** Артём Васильев
** Андрей Комаров
** Андрей Шулаев
* Конспекты проверяются редакторами, о недочётах сообщается на странице обсуждения.

== Презентации ==

=== Проверка презентаций ===

Чтобы сдать презентацию нужно:

# Выбрать тему (из того, что Антон рассказывал на лекциях).
# Проверить, не занята ли она, в таблице: [https://docs.google.com/spreadsheet/pub?key=0Ar0nZy99lVSvdDIzR1E5R1MwdDN0MXBiOHRyQ2NVV1E&gid=1 Распределение презентаций].
# Сообщить о вашем выборе куратору.
# Убедиться в том, что вас записали в табличку.
# Сделать fork [https://bitbucket.org/andreyrybak/computational-geometry-presentations репозитория].
# Создать папку computational-geometry-presentations/cg2012.1/presentations/<название темы>/
# Сделать презентацию.
# Сообщить куратору и получить ответ.
# Исправить недочеты (если есть) и вернуться к предыдущему пункту.

Дедлайн: две недели после выбора темы {{---}} черновик презентации, через месяц {{---}} готовая презентация.

В репозитории есть два примера презентаций в Beamer'e.

=== Требования к презентациям ===

# Презентация должна быть презентацией, а не полотном текста.
# Неинформативные картинки не приветствуются.
# Копипаста в любом виде не приветствуется.
# Презентации надо делать в TeX'е. Презентации в MS PowerPoint или аналогах будут караться отрубанием головы. А именно, для этого стоит использовать пакет beamer. Он хороший, презентации в нём красивые, а аналогов вроде как и нет. Почитать про него можно [http://ru.wikipedia.org/wiki/Beamer_(LaTeX) тут]. В конце статьи есть ссылки на документацию.
# Картинки лучше рисовать с помощью [http://ru.wikipedia.org/wiki/Metapost MetaPost] или его аналогов (например, PGF/TikZ)
#* Примеры по использованию MetaPost можно посмотреть [http://tex.loria.fr/prod-graph/zoonekynd/metapost/metapost.html здесь]
#* Мануал можно взять на [ftp://ifmo2539.dyndns.org/ ftp-сервере]
#* Руководство по PGF/TikZ можно взять [http://ftp.math.purdue.edu/mirrors/ctan.org/graphics/pgf/base/doc/generic/pgf/pgfmanual.pdf здесь]
# Весь текст должен выглядеть красиво и правильно. Нерусские кавычки в тексте, дефисы вместо минуса или тире, курсив вместо прямого шрифта и тому подобное не будут одобряться.
# Антон не одобряет неторопливость!

И вообще, надо ещё специально постараться, чтобы что-то в TeX'е выглядело плохо.

== Условия и чекеры ==
Куратор - Андрей Козлов

Примерная процедура сдачи выглядит так:
# написать в комментарий соответстующего тикета, что вы хотите им заняться
# получить одобрение куратора
# сделать fork от evaluator-tasks
# сделать задание
# структура папок должна быть следующей:
#* evaluator-tasks/cg2012.1/statements/<название задачи> - для условий
#* evaluator-tasks/cg2012.1/checkers/<название задачи> - для чекеров
# оповестить меня о готовности и ждать проверки
#* в случае успеха - получить баллы (profit)
#* иначе - пофиксить ошибки и вернуться к пункту 5

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

[[Категория: Вычислительная геометрия]]

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

2012-03-02T14:42:04Z

94.25.194.87:

Трапецоидная карта - геометрическая структура позволяющая локализоваться на площади за <tex>O(log(n))</tex>.
==Постановка задачи==
Предположим, у нас есть наши координаты, и есть карта мира.

Мы можем найти по карте наше местоположение и сказать в какой стране мы находимся.
Области задаются замкнутыми ломаными.

'''Формальная постановка задачи'''

Есть множество отрезков на плоскости.
Есть запрос (точка q), на выходе {{---}} область, в которой находится точка q.

==Структура данных==
[[Файл:Trapazoidmapshagal.jpg|650px|thumb|right|трапецоидная карта]]

*''Геометрическая''

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

Мы договариваемся что никакие две точки не лежат на одной вертикале(в противном случаи все еще противнее)

''Трапецоидная карта'' множества отрезков S - это эти отрезки + из каждой точки выпущены два луча, вверх и вниз до первого пересечения с другим отрезком или с оболочкой R.

{{Лемма
|statement= Любой face трапецоидной карты ограничен одним или двумя вертикальными отрезками и обязательно двумя не вертикальными отрезками.
}}
[[Файл:Trapezoidmapnavigationshagal.jpg|650px|thumb|right|навигация в трапецоидной карте]]

Именно отсюда берется название структуры, так как любой face либо трапеция, либо треугольник.

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

*левая граница(leftp) - точка определяющая левую сторону трапецоида или в случаи треугольника просто являющаяся левой вершиной.
*правая граница(rightp) - аналогично левой только справа.

*верхний отрезок(top) и нижний отрезок(bottom) - отрезки ограничивающие трапецоид сверху и снизу.

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

*пусть <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>\Delta_1</tex>,<tex>\Delta_2</tex> называют либо нижними левыми соседями, либо верхними.

{{Теорема
|statement=Трапецоидная карта построенная на n отрезках содержит максимум 6n+4 вершины и максимум 3n+1 трапецоид.
|proof=
*''вершины'', а точнее откуда они берутся.
[[Файл:Trapezoidmapnavigationleftpshagal.jpg|400px|thumb|right|варианты leftp(<tex>\Delta</tex>)]]
**4 вершины уходит на оболочку R.
**<tex>2 \cdot n</tex> концы отрезков
**<tex>2 \cdot 2n</tex> пересечения вертикальных лучей из концов отрезков с другими отрезками или оболочкой
*''трапецоиды''
Будем смотреть на левую сторону трапецоида.

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

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

Далее заметим, что правый конец отрезка может быть leftp(<tex>\Delta</tex>) только для одного трапецоида.

Левый конец может быть leftp(<tex>\Delta</tex>) максимум для двух трапецоидов.

Из этого следует, что количество трапецоидов <tex>n + 2n + 1 = 3n + 1</tex>.

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

----

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

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

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

*Второй тип узла - отрезок.

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

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

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

*Если текущий узел соответсвует вершине, то смотрим левее или провее мы находимся(проверка по x-координате).

*Если текущий узел соответствует отрезку, то смотрим выше или ниже мы находимся(проверка по y-координате).

*Плохие случаи:

Мы находимся на одной вертикале с вершиной

Мы находимся на отрезке

(Решение: молиться, или просто обрабатывать вручную.)

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

Так как трапецоидная карта - геометрическая структура, а основные операции ведутся именно с поисковой, упор на неё.

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

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

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

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

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

*Добавили отрезок.

*Нашли все трапецоиды, которые пересек новый отрезок.

*Удалили их.

*Создали новый трапецоиды.
[[Файл:Trpezoidmapbadcaseshagal.jpg|400px|thumb|right|сложный случай]]

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

Оно произошло в тех трапецоидах которые пересек текущий отрезок или можно сказать, что трапецоид с i-1-ой итерации не будет в i-ой только если его пересек отрезок.

Пусть якобы есть множество трапецоидов <tex>\Delta_0, \Delta_1, \Delta_2 ... \Delta_k</tex> упорядоченное по <tex>s_i</tex>

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

Если rightp(<tex>\Delta_j</tex>) лежит выше <tex>s_i</tex>, то сосед нижний и наоборот.

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

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

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

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

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

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

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

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

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

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

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

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

<tex>\Delta_0, \Delta_1, \Delta_2 ... \Delta_k</tex>.
==Случай коллизии==

==Асимптотика==
===Запрос===
Предположим у нас есть запрос на локализацию точки q. Время затраченное на этот запрос будет линейно зависеть от глубина графа.

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

Наибольшее время на запрос, которое мы можем потратить {{---}} <tex>3n</tex>. Произойдет это в самом ужасном из самых ужасных случаев.

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

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

Так как никто не выбирал исходное множество отрезков и запрос q, <tex>X_i</tex> - рандомная величина зависящая только от рандомного порядка добавления отрезков.

<tex>E[\sum^{n}_{i=1}X_i] = \sum^{n}_{i=1}E[X_i]</tex>

Как уже упоминалось на каждой итерации добавляется не более 3 узлов, а значит <tex>X_i</tex> <= 3.

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

<tex>\sum^{n}_{i=1}E[X_i] <= \sum^{n}_{i=1}3P_i</tex>

Начинаем оценивать <tex> P_i </tex>.

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

Это значит, что на i - 1-ой итерации мы локализовывали q в трапецоиде <tex> \Delta_q(i - 1) </tex>,

а на i-ой итерации уже в трапецоиде <tex> \Delta_q(i) </tex> и эти два трапецоида разные.

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

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

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

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

Значит либо <tex> s_i </tex> = top(<tex>\Delta_i</tex>) или bottom(<tex>\Delta_i</tex>), либо концы <tex>s_i</tex> = leftp(<tex>\Delta_i</tex>) или rightp(<tex>\Delta_i</tex>).

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

Тогда, вероятность изменения трапецоида - это его вероятность исчезнуть если удалится <tex>s_i</tex>.

Тогда переходим, к top(<tex>\Delta_i</tex>) и т.п. так как мы уже говорили, что <tex>s_i</tex> будет определенной стороной при навигации.

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

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

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

<tex>\sum^{n}_{i=1}E[X_i] \le \sum^{n}_{i=1}3P_i \le \sum^{n}_{i=1}12/i \le 12\sum^{n}_{i=1}(1/i) \approx 12 \cdot log(n)</tex>

===Память===
Заметим, что количество трапецоидов как мы доказали раньше равно O(n), поэтому мы должны оценить количество узлов созданых на i-ой итерации.

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

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

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

Mem = <tex>O(n) + \sum^{n}_{i=1}</tex>E[k_i]

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

А тогда Mem = <tex>O(n)</tex>

Из этих двух выводов очевидно следует, что время построения карты равно <tex>O(nlogn)</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> в поисковой структуре

Аналогично для просто карты

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

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]