Изменения

== Модель вычислений 1. Основание вычислительной геометрии ==# '''взяли''' [[ Аффинное пространство ]] (''??'')## Написать# '''взяли''' [[ Ориентация и объем ]] (''??'')## Написать# [[ Скалярное произведение и метрика ]] (''??'')## Написать# [[ Однородные координаты ]] (''??'')## Написать === Арифметика =2. Вычисление геометрических предикатов ==

#:* Категории # [[Пересечение окружностей]] (10)## Добавить расчёт погрешностей (см== 4. список тем)## Переходы бы подробней описать#:* Увеличить дроби#:* Добавить категории # [[Принадлежность точки выпуклому и невыпуклому многоугольникам]] (''5'')## Картинка в случае выпуклого многоугольника## Более подробное объяснение корректности алгоритма в случае невыпуклого полигона## Пару слов про то, работает ли в полигонах с дырками#:* Убрать плашку вверху#:* Оформить правильно источники информации#:* Добавить категории#:* min и max заменить на \min и \maxВыпуклые оболочки ==

=== Продвинутые алгоритмы ===# [[Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка (log^2 на добавление/удаление)]](''20'')## А что делать, когда у нас есть левая и правая оболочки?## Не написано, как определять эти случаи, и вообще надо по-другому делать## Пояснить подробней про сложные случаи## Всё ещё ничего не понятно#:* Переименовать конспект без "достаточно"#:* Добавить категории# [[Выпуклая оболочка в n-мерном пространстве]](''15'')## Убрать плашку вверху## Рассказать про QuickHull и вероятностный алгоритм (а только потом уже про сложный)#:* Добавить категории и источники информации# [[Алгоритм Бентли-ОттманаПересечение полуплоскостей, связь с выпуклыми оболочками]](''10'')## Написать подробней## Почему соответствует выпуклой оболочке? == 5. Поиск ==# [[Алгоритм БалабанаК-d деревья и перечисление точек в произвольном прямоугольнике (статика)]](''5'')## Мы ищем медиану по разным кординатам каждый раз, разве нам достаточно просто как-то посортить точки?## Более подробное доказательство асимптотики времени работы, разбор случаев, сказать, что оценка довольно грубая, на практике чуть быстрей, хотя всё равно медленно #:* Оформить правильно англоязычные термины#:* Оформить правильно источники информации#:* Отформатировать псевдокод#:* Функции в тексте взять в \mathrm#:* Неплохо бы для понимания добавить картинки из гуглящейся презентации#:* Добавить категории# [[Трапецоидная картаКвадродеревья | Квадродерево, сжатое квадродерево]](''10'')# [[Алгоритм Киркпатрика детализации триангуляции]]# А зачем оно надо?## Про перечисление точек в прямоугольнике более формально написать, псевдокод добавить хороший, оценки сказать## Время работы ортогонального поиска в сжатом квадродереве#:* Убрать текст про билеты вверху#:* Англоязычные термины#:* Внутренние ссылки оформить как примечания#:* Картинки наезжают на заголовки#:* Оформить правильно источники информации#:* Добавить категории# [[Упрощение полигональной цепиSkip quadtree: определение, время работы | Skip quadtree: определение, время работы, запрос точек в прямоугольнике ]]

## Впихнуть в Range tree (берётся вместе со следующим конспектом)# [[Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree)]] (''20'')## Написать в одномерном случае сначала, что его можно решать проще, а в двумерном, что можно использовать простой вариант одномерного в узле## Картинки очень нужны, без них слабо понятно## Псевдокоды неплохо бы добавить## Написать подробно Fractional Cascading с картинками (см. список тем)#:* Переименовать конспект в Range tree#:* Заменить знаки неравенств#:* Заменить вертикальную черту на \mid#:* Задачу в Шаблон#:* Все переменные и константы в Tex#:* Оформить правильно источники информации#:* Добавить категории# [[Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)]] (''5'')## Чуть подробней написать про решение задачи, как находим, как упорядочиваем отрезки, добавить картинки опять же#:* Задачу в Шаблон#:* Правильно оформить англ. термины#:* Оформить правильно источники информации# [[Дерево интервалов (interval tree) и пересечение точки с множеством интервалов]] (''5'')## Неплохо бы добавить ссылку на код реализации, довольно простая структура## Можно сказать, как соптимизировать, если нам нужно только количество отрезков## Картинки было бы неплохо добавить#:* Переименовать конспект в Interval tree#:* Определение жирным, англоязычные термины правильно оформить#:* Отформартировать псевдокод, описать структуру дерева подробней#:* Добавить Источники информации#:* Добавить категории# [[Триангуляция полигонов Пересечение прямоугольника с множеством прямоугольников (ушная + монотоннаяPST)]](''5'')## Картинки добавить#:* Переименовать конспект в Priority search tree#:* Логичней сначала писать задачу, а потом давать определение структуры#:* Отформартировать псевдокоды#:* Добавить категории#:* Добавить источники информации# [[ BSP-дерево ]] == 6. Триангуляция ==# [[ Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]](''10'')## Переименовать конспект в просто триангуляцию и ушную триангуляцию, выпилить в отдельный конспект## А зачем нужно два уха?## Нужно подробней написать, почему работает за O(n^2), сейчас это непонятно из конспекта, кажется, что за куб#:* Интервики на число триангуляций (числа Каталана)#:* Отформатировать псевдокод#:* Добавить источники информации# [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой ]] == 7. ППЛГ и РСДС ==# [[ Пересечение полуплоскостейКонфигурация]] (''10'')## Информацию про DCEL, его свойства, связь с выпуклыми оболочками | Пересечение полуплоскостейпростые примеры операций (соединение двух вершин ребром, связь с выпуклыми оболочками ]]то есть добавление диагонали)## Оставить только общий конспект про конфигурации и DCEL в частности# [[ Пересечение множества отрезков | Пересечение множества отрезков ]]:* Таблички сделать красивые# [[ Snap rounding | Snap rounding ]]:* Оформить правильно источники информации# [[Конфигурация]]:* Добавить категории# [[ ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых | ППЛГ и РСДС ]] (PSLG и DCEL''15''): определение, построение РСДС множества прямых ]]## Написать полный разбор задачи Line Arrangement со всякими подробностями типа точного вычисления предикатов# [[ Пересечение многоугольников (PSLG overlaying) | Пересечение многоугольников ]] == 8. Алгоритмы локализации ==# [[Принадлежность точки выпуклому и невыпуклому многоугольникам]] (PSLG overlaying''5'') ]]## Картинка в случае выпуклого многоугольника## Более подробное объяснение корректности алгоритма в случае невыпуклого полигона## Пару слов про то, работает ли в полигонах с дырками#:* Убрать плашку вверху#:* Оформить правильно источники информации#:* Добавить категории#:* min и max заменить на \min и \max# [[ Локализация в ППЛГ методом полос (персистентные деревья) | Локализация в ППЛГ методом полос (персистентные деревья) ]](''5'')## Добавить несколько больше информации в введение из лекций Станкевича## Добавить картинок из гуглящейся презенташки#:* Задачу в Шаблон#:* Убрать плашку вверху#:* Интервики на персистентые деревья#:* Добавить категории# [[ Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ. Алгоритм Киркпатрика ]](''10'')## Добавить другой критерий выбора удаляемых вершин по степени (презенташка гуглится), доказать его корректность, сравнить с существующим## Рассказать про перетриангуляцию (как эффективно и как всё в DCEL вообще происходит)#:* Отформатировать псевдокод#:* Пофиксить категории#:* Увеличить дроби# [[ Трапецоидная карта | Трапецоидная карта ]](''20'')## Сказать, что в статике можно строить заметающей прямой трапецоидную карту (и сказать, как строить)# [[BSP# Про мнимую оболочку сказать получше -дерево]]окружаем прямоугольником отрезки## Чуть переформулировать постановку (всё же решаем задачу локализации, а не поиска пути, но про него можно отдельно сказать)## Сказать в начале, какие частные случаи не рассматриваем## Более подробные псевдокоды, ну и вообще конспект сделать более структурированным## Добавить худший случай для построения## Доказательства асимптотик можно сделать попроще, используя регрессионный анализ#:* Задачу в Шаблон#:* Оформить правильно источники информации#:* Добавить категории == Скалярное произведение 9. Триангуляция Делоне и мера (проверяется) диаграмма Вороного ==# [[ Диаметр множества точек Триангуляция Делоне | Триангуляция Делоне ]] (вращающиеся калиперы''30'') ## Чуть подробней расписать первую теорему, расписать координаты в векторе, пояснить результат## Структурней описать алгоритм локализации## Подробные доказательства всех лем для локализации## Точнее и подробней про констрейнты рассказать## Доказать парочку якобы очевидных фактов#:* Увеличить дроби#:* Заменить знаки неравенст#:* Источники информации#:* Категории# [[ Диаграмма Вороного | Диаметр множества точек Диаграмма Вороного ]] (вращающиеся калиперы''30'') # [[ Motorcycle graph ]]# [[ Straight skeleton ]] == 10. Планирование движения (Motion planning) ==# [[ Сумма Минковского (определение, вычисление) | Сумма Минковского (определение, вычисление) ]](''20'')## Подробней описание, что это такое и зачем надо## Доказать получше экстремальность вершины в заданном направлении как сумму двух вершин в этом направлении## Доказать выпуклость суммы минковского двух выпуклых фигур#:* Отформатировать псевдокод#:* Источники информации, категории# [[ Visibility graph и motion planning | Visibility graph и motion planning ]] (''25'')## Сказать в лемму про разрешение графа ещё про невыпуклые вершины '''(лемма без названия)'''## Добавить про упрощение путей по навигационным картам '''(http://habrahabr.ru/post/199256/ дорожные карты)'''## В картинке про заметающий луч, кажется, бага - надо получше объяснить, что на ней нарисовано '''(Lee’s Algorithm)'''## Ещё пояснить, почему мы рассматриваем только правую полуплоскость (и вообще как сортим вдоль луча, это мб нетривиально в некоторых случаях) '''(Lee’s Algorithm)'''## Доказать, что после суммы минковского препятствий будет не очень много углов внутри полигонов '''(Motion planning)'''#:* Оформить правильно Источники информации '''(перенести Overmars and Welzl’s Algorithm)'''#:* Некоторые картинки можно красивей нарисовать#:* Заменить знаки неравенств '''(??)''' == 11. Задачи ==# [[ Минимальная охватывающая окружность Диаметр множества точек | (вращающиеся калиперы)]] (''10'')## Картинку с пояснением определения следующей стороны для вращения при помощи поворота## Сказать, что поиск минимальной охватывающей окружности тут не прокатывает (с контрпримером)#:* Задачу в шаблон#:* Оформить правильно источники информации# [[Минимальная охватывающая окружность множества точек ]](''25'')## Рассказать, почему выпуклая оболочка (или диаметр двух дальних точек не подходят или подходят)## Добавить реализацию через одну функцию## Нормальное и понятное доказательство корректности с картинками## Добавить оптимизации по скорости## А зачем оно вообще надо?#:* Убрать плашку вверху#:* Заменить знаки неравенств#:* Отформатировать псевдокоды#:* Оформить правильно источники информации#:* Добавить категории# [[ Visibility graph и motion planning | Visibility graph Пересечение окружностей]] (''10'')## Добавить расчёт погрешностей (см. список тем)## Переходы бы подробней описать#:* Увеличить дроби#:* Добавить категории # [[Упрощение полигональной цепи]] (''5'')## Добавить преимущества Дугласа-Пекера#:* Чуть-чуть поправить структуру конспекта#:* Задачу в Шаблон#:* Оформить правильно Источники информации#:* Внутренние ссылки сделать примечаниями#:* Отформатировать псевдокод#:* Заменить знаки неравенств# [[ Вычисление площади и motion planning объема ]](''15'')## Написать# [[ Триангуляция Делоне | Триангуляция Делоне Пересечение выпуклых многоугольников ]](''15'')## Написать  == 12. Программирование ==# [[ Диаграмма Вороного | Диаграмма Вороного Запуск проекта визуализации cg]](''10'')## Небольшой туториал, как начать работу с библиотекой визуализации, что поставить и как запустить## Неплохо бы ещё скриншоты добавить (чтобы совсем всем всё было понятно)# [[Motorcycle graphCMake_Tutorial|Туториал по cmake]](''15'')## Сделать конспект более формальным## Как установить, что вообще надо (ссылки добавить)## Простые и последовательные примеры: сборка простого файла, нескольких файлов, как подключить буст, gmp, gtest## Объяснение происходящего в библиотеке визуализации cg## Примеры полных скриптов#:* Добавить категории#:* Добавить ссылок# [[Straight skeletonТестирование с использованием Google Test]](''5'')## Ссылка на код битая, добавить пример кода с github#:* Задачу в Шаблон#:* Добавить категории#:* Интервики#:* Имя функции в \mathrm