== Конспекты Основание вычислительной геометрии ==* [[ Аффинное пространство ]]* [[ Объем ]]* [[ Скалярное произведение и метрика ]]* [[ Однородные координаты ]]* [[ Двойственное пространство ]]
== Вычисление геометрических предикатов ==* [[Представление чисел с плавающей точкой]]* [[Предикат "левый поворот"]]* [[Интервальная арифметикаПересечение отрезков и поворот: определение, свойства, вычисление ]]* [[Adaptive precision arithmetic]]* [[Алгоритм Бентли-Оттмана]]* [[Конфигурация]]* [[Трапецоидная карта]]* [[Алгоритм нахождения кратчайших путей вокруг полигональных препятствий]]* [[Пересечение окружностей]]* [[Упрощение полигональной цепи]]* [[Список темИнтервальная арифметика ]]
== Инструкции Пересечение отрезков ==* [[План курсаАлгоритм Бентли-Оттмана ]]* [[Написание условий задачПересечение множества отрезков ]]* [[ Алгоритм Балабана ]]* [[ Snap rounding ]]* [[ Пересечение отрезков на сфере ]]
== Сдача конспектов Выпуклые оболочки ==* [[ Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull ]]* [[ Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка ]]* [[ Выпуклая оболочка в n-мерном пространстве ]]* [[ Пересечение полуплоскостей, связь с выпуклыми оболочками ]]
== Поиск ==* [[ К-d деревья и перечисление точек в произвольном прямоугольнике (статика) ]]* [https[ Квадродеревья | Квадродерево, сжатое квадродерево ]]* [[ Skip quadtree://docs.google.com/spreadsheet/pub?key=0Ar0nZy99lVSvdDIzR1E5R1MwdDN0MXBiOHRyQ2NVV1E Распределение тем конспектовопределение, время работы | 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 ]]
# Презентация должна быть презентацией, а не полотном текста.== Организационные вопросы ==# Неинформативные картинки не приветствуются.# Копипаста в любом виде не приветствуется.# Презентации надо делать в TeX'е. Презентации в MS PowerPoint или аналогах будут караться отрубанием головы. А именно, для этого стоит использовать пакет beamer. Он хороший, презентации в нём красивые, а аналогов вроде как и нет. Почитать про него можно * [[httpУчастник:Shersh//ru.wikipedia.org/wiki/Beamer_Тикеты к вычислительной геометрии (LaTeXтермы 4 и 5) тут]. В конце статьи есть ссылки на документацию.# Картинки лучше рисовать с помощью [http://ru.wikipedia.org/wiki/Metapost MetaPost] или его аналогов | Правки к конспектам (например, PGF/TikZyear 2013)#* Примеры по использованию MetaPost можно посмотреть [http://tex.loria.fr/prod-graph/zoonekynd/metapost/metapost.html здесь]#* Мануал можно взять на [ftp://ifmo2539.dyndns.org/ ftp-сервере]#* Руководство по PGF/TikZ можно взять [httphttps://ftpdocs.math.purdue.edu/mirrors/ctangoogle.org/graphics/pgf/base/doc/genericcom/pgfspreadsheet/pgfmanual.pdf здесь]ccc?key=0AiudLnRYFaaXdFJZdXBaSHJQT29wd0EwekxSZ0JTZkE&usp=drive_web# Весь текст должен выглядеть красиво gid=4 Список новых тем и правильно. Нерусские кавычки в тексте, дефисы вместо минуса или тире, курсив вместо прямого шрифта и тому подобное не будут одобряться.# Антон не одобряет неторопливость!дополнений]
И вообще, надо ещё специально постараться, чтобы что-то в TeX'е выглядело плохо.---
== Условия и чекеры ==* [[Список тем | Список тем (year 2010)]]Куратор - Андрей Козлов* [[Список тем (year 2012)]] Примерная процедура сдачи выглядит так* [[Обсуждение:Вычислительная геометрия# написать в комментарий соответстующего тикета, что вы хотите им занятьсяСдача конспектов | Сдача конспектов]]# получить одобрение куратора# сделать fork от evaluator-tasks# сделать задание# структура папок должна быть следующей* [[Обсуждение:Вычислительная геометрия#* evaluator-tasks/cg2012.1/statements/<название задачи> - для условийПрезентации | Сдача презентаций]]#* evaluator-tasks/cg2012.1/checkers/<название задачи> - для чекеров[[Обсуждение:Вычислительная геометрия# оповестить меня о готовности Условия и ждать проверки#* в случае успеха - получить баллы (profit)#* иначе - пофиксить ошибки чекеры | Условия и вернуться к пункту 5 Разногласия между условием и чекером, в большинстве своем, будут трактоваться в пользу того, кто первый начал делать.чекеры]]
[[Категория: Вычислительная геометрия]]
