3622
правки
Изменения
м
→10. Планирование движения (Motion planning)
Нумерованные замечания {{---}} по содержанию, маркированные {{---}} по оформлению== Модель вычислений 1. Основание вычислительной геометрии ==# '''взяли''' [[ Аффинное пространство ]] (''??'')## Написать# '''взяли''' [[ Ориентация и объем ]] (''??'')## Написать# [[ Скалярное произведение и метрика ]] (''??'')## Написать# [[ Однородные координаты ]] (''??'')## Написать ==2. Вычисление геометрических предикатов = Арифметика =# [[Представление чисел с плавающей точкой]] (''5'')## Помёрджить с аналогичным конспектом по дискретке## Добавить код получения машинного эпсилон в c++#:* Оформить правильно источники информации#:* Поправить категории#:* Дефисы заменить на тире#:* Заменить знаки неравенств# [[Предикат "левый поворот"]] (''10'')## Перенести расчёт погрешности из конспекта про вещественные числа сюда## Сказать, почему в расчёте не используется деление, и что обычно с этим делают## Статью написать именно про предикат поворота, про его сакральный смысл, а не про пересечение отрезков; можно добавить различных применений## Добавить пример, простое правило для запоминания направления#:* Неплохо бы векторные картинки сделать вместо таких растровых#:* Добавить категории#:* Добавить источники информации# [[Пересечение отрезков и поворот: определение, свойства, вычисление]] (''15'')## Подробное и ясное объяснение шагов с картинками (взять часть информации из предиката поворота), вот [http://martin-thoma.com/how-to-check-if-two-line-segments-intersect/ здесь] детальный разбор этой задачи## Про аффинное пространство будет отдельный конспект (если кто-нибудь напишет), поэтому только небольшую справку в начале надо сделать## Рассказать про нахождение самой точки пересечения двух отрезков, и какие проблемы с этим связаны#:* Переменные и константы в Tex#:* Интервики#:* Оформить правильно источники информации#:* Отформатировать псевдокод, оформить как функцию, принимающих два отрезка, код смотреть в cg#:* Добавить категории#:* Заменить math на tex# [[ Adaptive precision arithmetic ]]# [[Интервальная арифметика]] (''10'')## Какой-нибудь пример с кодом на c++ (желательно предикат левый поворот) и с объяснением происходящего## И написать, что делать, если в интервальной арифметике посчиталось неточно (добавить просто пример с mpq_class)## Пару мотивационных слов о том, как надо делать вычисления (про скатывание в рациональную), о скорости и т. д.#:* Англоязычные термины#:* В формулы можно добавить пробелы для лучшей читаемости#:* Оформить правильно Источники информации#:* Добавить категории == 3. Пересечение отрезков ==# [[Алгоритм Бентли-Оттмана]]# [[Пересечение множества отрезков | Пересечение множества отрезков ]] (''15'')## Помёрджить с конспектом про Бентли-Оттмана## Написать понятный конспект с описанием всех шагов и частных случаев# [[Snap rounding]] (''30'')## Написать полноценный конспект про SR по алгоритму на пучках, добавить наивный алгоритм# [[Пересечение отрезков на сфере]] (''10'')## Доделать конспект: описать всё формально, подробно и понятно#:* Задачу в Шаблон#:* Алгоритм красиво оформить#:* Источники информации#:* Категории ==4. Выпуклые оболочки ==# [[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull]] (''10'')## См. обсуждения## В некоторых местах не очень понятно, почему это правда - пояснить корректность алгоритма## Про Чена очень мало, смотреть википедию русскую#:* Определение жирным#:* Дефисы на тире#:* Все ссылки в конец, оформить правильно Источники информации#:* Добавить в ссылки примеры кодов (из cg, ещё можно где-нибудь нагуглить)#:* Опустить заголовки на 1, сделать конспект более структурированным#:* Отформатировать псевдокоды# [[Динамическая выпуклая оболочка (достаточно 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 в частности#:* Таблички сделать красивые#:* Оформить правильно источники информации#:* Добавить категории# [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых]] (''15'')## Написать полный разбор задачи Line Arrangement со всякими подробностями типа точного вычисления предикатов# [[Пересечение многоугольников (PSLG overlaying)]] ==8. Алгоритмы локализации = Аффинное пространство =# [[Принадлежность точки выпуклому и невыпуклому многоугольникам]] (''5'')## Картинка в случае выпуклого многоугольника## Более подробное объяснение корректности алгоритма в случае невыпуклого полигона## Пару слов про то, работает ли в полигонах с дырками#:* Убрать плашку вверху#:* Оформить правильно источники информации#:* Добавить категории#:* min и max заменить на \min и \max# [[Локализация в ППЛГ методом полос (персистентные деревья) | Локализация в ППЛГ методом полос (персистентные деревья)]] (''5'')## Добавить несколько больше информации в введение из лекций Станкевича## Добавить картинок из гуглящейся презенташки#:* Задачу в Шаблон#:* Убрать плашку вверху#:* Интервики на персистентые деревья#:* Добавить категории# [[Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ. Алгоритм Киркпатрика ]] (''10'')## Добавить другой критерий выбора удаляемых вершин по степени (презенташка гуглится), доказать его корректность, сравнить с существующим## Рассказать про перетриангуляцию (как эффективно и как всё в DCEL вообще происходит)#:* Отформатировать псевдокод#:* Пофиксить категории#:* Увеличить дроби# [[Трапецоидная карта]] (''20'')## Сказать, что в статике можно строить заметающей прямой трапецоидную карту (и сказать, как строить)## Про мнимую оболочку сказать получше - окружаем прямоугольником отрезки## Чуть переформулировать постановку (всё же решаем задачу локализации, а не поиска пути, но про него можно отдельно сказать)## Сказать в начале, какие частные случаи не рассматриваем## Более подробные псевдокоды, ну и вообще конспект сделать более структурированным## Добавить худший случай для построения## Доказательства асимптотик можно сделать попроще, используя регрессионный анализ#:* Задачу в Шаблон#:* Оформить правильно источники информации#:* Добавить категории == 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'')## Рассказать, почему выпуклая оболочка (или диаметр двух дальних точек не подходят или подходят)## Добавить реализацию через одну функцию## Нормальное и понятное доказательство корректности с картинками## Добавить оптимизации по скорости## А зачем оно вообще надо?#:* Убрать плашку вверху#:* Заменить знаки неравенств#:* Отформатировать псевдокоды#:* Оформить правильно источники информации#:* Добавить категории# [[Пересечение окружностей]] (''10'')## Добавить расчёт погрешностей (см. список тем)## Переходы бы подробней описать#:* Увеличить дроби#:* Добавить категории # [[Упрощение полигональной цепи]] (''5'')## Добавить преимущества Дугласа-Пекера#:* Чуть-чуть поправить структуру конспекта#:* Задачу в Шаблон#:* Оформить правильно Источники информации#:* Внутренние ссылки сделать примечаниями#:* Отформатировать псевдокод#:* Заменить знаки неравенств# [[ Вычисление площади и мера объема ]] (''15'')## Написать# [[ Пересечение выпуклых многоугольников ]] (''15'')## Написать ==12. Программирование ==# [[Запуск проекта визуализации cg]] (''10'')## Небольшой туториал, как начать работу с библиотекой визуализации, что поставить и как запустить## Неплохо бы ещё скриншоты добавить (чтобы совсем всем всё было понятно)# [[CMake_Tutorial|Туториал по cmake]] (''15'')## Сделать конспект более формальным## Как установить, что вообще надо (ссылки добавить)## Простые и последовательные примеры: сборка простого файла, нескольких файлов, как подключить буст, gmp, gtest## Объяснение происходящего в библиотеке визуализации cg## Примеры полных скриптов#:* Добавить категории#:* Добавить ссылок# [[Тестирование с использованием Google Test]] (''5'')## Ссылка на код битая, добавить пример кода с github#:* Задачу в Шаблон#:* Добавить категории#:* Интервики#:* Имя функции в \mathrm
