Изменения

== Конспекты Основание вычислительной геометрии ==* [[ Аффинное пространство ]]* [[ Объем ]]* [[ Скалярное произведение и метрика ]]* [[ Однородные координаты ]]* [[ Двойственное пространство ]]

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

== Сдача конспектов Пересечение отрезков ==* [[ Алгоритм Бентли-Оттмана ]]* [[ Пересечение множества отрезков ]]* [[ Алгоритм Балабана ]]* [[ Snap rounding ]]* [[ Пересечение отрезков на сфере ]]

* [https://docs.google.com/spreadsheet/pub?hl=en_US&hl=en_US&keyВыпуклые оболочки =0Ar0nZy99lVSvdDIzR1E5R1MwdDN0MXBiOHRyQ2NVV1E&output=html Распределение тем конспектов]* Для сдачи конспекта необходимо сообщить об этом одному из редакторов[[ Статические выпуклые оболочки:Джарвис, Грэхем, Эндрю, Чен, QuickHull ]]** Артём Васильев[[ Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка ]]** Андрей Комаров[[ Выпуклая оболочка в n-мерном пространстве ]]** Андрей Шулаев* Конспекты проверяются редакторами[[ Пересечение полуплоскостей, о недочётах сообщается на странице обсуждения.связь с выпуклыми оболочками ]]

== Презентации Поиск == * [[ К-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=0AvxUImW8vkVadHNKYXVPdlRNSXNBRTY3VURTeFZnY3c&output=html Распределение презентацийПринадлежность точки выпуклому и невыпуклому многоугольникам ]].# Сообщить о вашем выборе куратору.* [[ Локализация в ППЛГ методом полос (персистентные деревья) ]]# Убедиться в том, что вас записали * [[ Алгоритм Киркпатрика детализации триангуляции | Локализация в табличкуППЛГ.Алгоритм Киркпатрика ]]# Сделать fork * [https://bitbucket.org/andreyrybak/computational-geometry-presentations репозитория[ Трапецоидная карта ]].# Создать папку computational-geometry-presentations/cg2012.1/presentations/<название темы>/# Сделать презентацию.# Сообщить куратору и получить ответ.# Исправить недочеты (если есть) и вернуться к предыдущему пункту.

=== Требования к презентациям =Триангуляция Делоне и диаграмма Вороного ==* [[ Триангуляция Делоне ]]* [[ Триангуляция Делоне на сфере ]]* [[ Диаграмма Вороного ]]* [[ Motorcycle graph ]]* [[ Straight skeleton ]]

== Планирование движения (Motion planning) ==* Презентация должна быть презентацией[[ Сумма Минковского (определение, а не полотном текста. Хорошие картинки приветствуются. Неинформативные картинки не приветствуются. Копипаст в любом виде не приветствуется.вычисление) ]]* [[ Visibility graph и motion planning ]]

== Задачи ==* Презентации надо делать в TeX'е. Презентации в MS PowerPoint или аналогах будут караться отрубанием головы.[[ Диаметр множества точек (вращающиеся калиперы) ]]А именно, для этого стоит использовать пакет beamer. Он хороший, презентации в нём красивые, а аналогов вроде как * [[ Минимальная охватывающая окружность множества точек ]]* [[ Пересечение окружностей ]]* [[ Упрощение полигональной цепи ]]* [[ Вычисление площади и нет.объема ]]Почитать про него можно (внезапно!) тут: * [[http://ru.wikipedia.org/wiki/Beamer_(LaTeX) BeamerПересечение выпуклых многоугольников ]]. В конце статьи есть ссылки на документацию.

== Программирование ==* При составлении презентации стоит забить на оформление презентации в целом — так как она делается в TeX'е, можно будет быстро поменять стиль.[[ CMake_Tutorial|Туториал по cmake ]]Но! Весь текст должен выглядеть красиво и правильно.Нерусские кавычки в тексте, дефисы вместо минуса или тире, курсив вместо прямого шрифта и тому подобное не будут одобряться.По поводу внешнего вида презентации в целом придирок не будет. И вообще, надо ещё специально постараться, чтобы что-то в TeX'е выглядело плохо.* [[ Тестирование с использованием Google Test ]]

== Организационные вопросы ==* Антон не одобряет неторопливость![[Участник:Shersh/Тикеты к вычислительной геометрии (термы 4 и 5) | Правки к конспектам (year 2013)]]* [https://docs.google.com/spreadsheet/ccc?key=0AiudLnRYFaaXdFJZdXBaSHJQT29wd0EwekxSZ0JTZkE&usp=drive_web#gid=4 Список новых тем и дополнений]

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

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