Изменения

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

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

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

== Выпуклые оболочки ==* [[Написание условий задачСтатические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, 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-дерево ]]

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

== Презентации ППЛГ и РСДС == * [[ Конфигурация ]]* [[ ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых ]]* [[ Пересечение многоугольников (PSLG overlaying) ]]

=== Проверка презентаций =Алгоритмы локализации ==* [[ Принадлежность точки выпуклому и невыпуклому многоугольникам ]]* [[ Локализация в ППЛГ методом полос (персистентные деревья) ]]* [[ Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ. Алгоритм Киркпатрика ]]* [[ Трапецоидная карта ]]

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

==Организационные вопросы = Требования =* [[Участник: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_[Список тем | Список тем (LaTeXyear 2010) тут]. В конце статьи есть ссылки на документацию.]* Картинки лучше рисовать с помощью [http://ru.wikipedia.org/wiki/Metapost MetaPost] или его аналогов [Список тем (например, tikz/pgfyear 2012)]]** Примеры по использованию 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 Разногласия между условием и чекером, в большинстве своем, будут трактоваться в пользу того, кто первый начал делать.]]