Вычислительная геометрия — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Конспекты)
м (rollbackEdits.php mass rollback)
 
(не показано 55 промежуточных версий 24 участников)
Строка 1: Строка 1:
== Конспекты ==
+
== Основание вычислительной геометрии ==
 +
* [[ Аффинное пространство ]]
 +
* [[ Объем ]]
 +
* [[ Скалярное произведение и метрика ]]
 +
* [[ Однородные координаты ]]
 +
* [[ Двойственное пространство ]]
  
* [[Представление чисел с плавающей точкой]]
+
== Вычисление геометрических предикатов ==
* [[Предикат "левый поворот"]]
+
* [[ Представление чисел с плавающей точкой ]]
* [[Интервальная арифметика]]
+
* [[ Предикат "левый поворот" ]]
* [[Adaptive precision arithmetic]]
+
* [[ Пересечение отрезков и поворот: определение, свойства, вычисление ]]
* [[Алгоритм Бентли-Оттмана]]
+
* [[ Adaptive precision arithmetic ]]
* [[Конфигурация]]
+
* [[ Интервальная арифметика ]]
* [[Трапецоидная карта]]
 
* [[Алгоритм нахождения кратчайших путей вокруг полигональных препятствий]]
 
* [[Пересечение окружностей]]
 
* [[Упрощение полигональной цепи]]
 
* [[Список тем]]
 
  
== Инструкции ==
+
== Пересечение отрезков ==
* [[План курса]]
+
* [[ Алгоритм Бентли-Оттмана ]]
* [[Написание условий задач]]
+
* [[ Пересечение множества отрезков ]]
 +
* [[ Алгоритм Балабана ]]
 +
* [[ Snap rounding ]]
 +
* [[ Пересечение отрезков на сфере ]]
  
== Сдача конспектов ==
+
== Выпуклые оболочки ==
 +
* [[ Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull ]]
 +
* [[ Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка ]]
 +
* [[ Выпуклая оболочка в n-мерном пространстве ]]
 +
* [[ Пересечение полуплоскостей, связь с выпуклыми оболочками ]]
  
* [https://docs.google.com/spreadsheet/pub?key=0Ar0nZy99lVSvdDIzR1E5R1MwdDN0MXBiOHRyQ2NVV1E Распределение тем конспектов]
+
== Поиск ==
* Для сдачи конспекта необходимо сообщить об этом одному из редакторов:
+
* [[ К-d деревья и перечисление точек в произвольном прямоугольнике (статика) ]]
** Артём Васильев
+
* [[ Квадродеревья | Квадродерево, сжатое квадродерево ]]
** Андрей Комаров
+
* [[ Skip quadtree: определение, время работы | Skip quadtree: определение, время работы, запрос точек в прямоугольнике ]]
** Андрей Шулаев
+
* [[ Ортогональный поиск ]]
* Конспекты проверяются редакторами, о недочётах сообщается на странице обсуждения.
+
* [[ Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) ]]
 +
* [[ Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) ]]
 +
* [[ Дерево интервалов (interval tree) и пересечение точки с множеством интервалов ]]
 +
* [[ Пересечение прямоугольника с множеством прямоугольников (PST) | Пересечение прямоугольника с множеством прямоугольников (priority search tree) ]]
 +
* [[ BSP-дерево ]]
  
== Презентации ==  
+
== Триангуляция ==
 +
* [[ Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]]
 +
* [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой ]]
  
=== Проверка презентаций ===
+
== ППЛГ и РСДС ==
 +
* [[ Конфигурация ]]
 +
* [[ ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых ]]
 +
* [[ Пересечение многоугольников (PSLG overlaying) ]]
  
Чтобы сдать презентацию нужно:
+
== Алгоритмы локализации ==
 +
* [[ Принадлежность точки выпуклому и невыпуклому многоугольникам ]]
 +
* [[ Локализация в ППЛГ методом полос (персистентные деревья) ]]
 +
* [[ Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ. Алгоритм Киркпатрика ]]
 +
* [[ Трапецоидная карта ]]
  
# Выбрать тему (из того, что Антон рассказывал на лекциях).
+
== Триангуляция Делоне и диаграмма Вороного ==
# Проверить, не занята ли она, в таблице: [https://docs.google.com/spreadsheet/pub?key=0Ar0nZy99lVSvdDIzR1E5R1MwdDN0MXBiOHRyQ2NVV1E&gid=1 Распределение презентаций].
+
* [[ Триангуляция Делоне ]]
# Сообщить о вашем выборе куратору.
+
* [[ Триангуляция Делоне на сфере ]]
# Убедиться в том, что вас записали в табличку.
+
* [[ Диаграмма Вороного ]]
# Сделать fork [https://bitbucket.org/andreyrybak/computational-geometry-presentations репозитория].
+
* [[ Motorcycle graph ]]
# Создать папку computational-geometry-presentations/cg2012.1/presentations/<название темы>/
+
* [[ Straight skeleton ]]
# Сделать презентацию.
 
# Сообщить куратору и получить ответ.
 
# Исправить недочеты (если есть) и вернуться к предыдущему пункту.
 
  
Дедлайн: две недели после выбора темы {{---}} черновик презентации, через месяц {{---}} готовая презентация.
+
== Планирование движения (Motion planning) ==
 +
* [[ Сумма Минковского (определение, вычисление) ]]
 +
* [[ Visibility graph и motion planning ]]
  
В репозитории есть два примера презентаций в Beamer'e.
+
== Задачи ==
 +
* [[ Диаметр множества точек (вращающиеся калиперы) ]]
 +
* [[ Минимальная охватывающая окружность множества точек ]]
 +
* [[ Пересечение окружностей ]]
 +
* [[ Упрощение полигональной цепи ]]
 +
* [[ Вычисление площади и объема ]]
 +
* [[ Пересечение выпуклых многоугольников ]]
  
=== Требования к презентациям ===
+
== Программирование ==
 +
* [[ CMake_Tutorial|Туториал по cmake ]]
 +
* [[ Тестирование с использованием Google Test ]]
  
# Презентация должна быть презентацией, а не полотном текста.
+
== Организационные вопросы ==
# Неинформативные картинки не приветствуются.
+
* [[Участник:Shersh/Тикеты к вычислительной геометрии (термы 4 и 5) | Правки к конспектам (year 2013)]]
# Копипаста в любом виде не приветствуется.
+
* [https://docs.google.com/spreadsheet/ccc?key=0AiudLnRYFaaXdFJZdXBaSHJQT29wd0EwekxSZ0JTZkE&usp=drive_web#gid=4 Список новых тем и дополнений]
# Презентации надо делать в 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'е выглядело плохо.
+
----
  
== Условия и чекеры ==
+
* [[Список тем | Список тем (year 2010)]]
Куратор - Андрей Козлов
+
* [[Список тем (year 2012)]]
 
+
* [[Обсуждение:Вычислительная геометрия#Сдача конспектов | Сдача конспектов]]
Примерная процедура сдачи выглядит так:
+
* [[Обсуждение:Вычислительная геометрия#Презентации | Сдача презентаций]]
# написать в комментарий соответстующего тикета, что вы хотите им заняться
+
* [[Обсуждение:Вычислительная геометрия#Условия и чекеры | Условия и чекеры]]
# получить одобрение куратора
 
# сделать fork от evaluator-tasks
 
# сделать задание
 
# структура папок должна быть следующей:
 
#* evaluator-tasks/cg2012.1/statements/<название задачи> - для условий
 
#* evaluator-tasks/cg2012.1/checkers/<название задачи> - для чекеров
 
# оповестить меня о готовности и ждать проверки
 
#* в случае успеха - получить баллы (profit)
 
#* иначе - пофиксить ошибки и вернуться к пункту 5
 
 
 
Разногласия между условием и чекером, в большинстве своем, будут трактоваться в пользу того, кто первый начал делать.
 
  
 
[[Категория: Вычислительная геометрия]]
 
[[Категория: Вычислительная геометрия]]

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

Основание вычислительной геометрии

Вычисление геометрических предикатов

Пересечение отрезков

Выпуклые оболочки

Поиск

Триангуляция

ППЛГ и РСДС

Алгоритмы локализации

Триангуляция Делоне и диаграмма Вороного

Планирование движения (Motion planning)

Задачи

Программирование

Организационные вопросы