3622
правки
Изменения
м
#:* Интервики
#:* Имя функции в \mathrm
== Базовые алгоритмы и структуры данных ==
#:* Отформатировать псевдокод, оформить как функцию, принимающих два отрезка, код смотреть в cg
# [[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull]] (''10'')
## См. обсуждения
## В некоторых местах не очень понятно, почему это правда - пояснить корректность алгоритма
## Про Чена очень мало, смотреть википедию русскую
#:* Определение жирным
#:* Дефисы на тире
#:* Все ссылки в конец, оформить правильно Источники информации
#:* Добавить в ссылки примеры кодов (из cg, ещё можно где-нибудь нагуглить)
#:* Опустить заголовки на 1, сделать конспект более структурированным
#:* Отформатировать псевдокоды
=== Продвинутые алгоритмы ===
# [[Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка (log^2 на добавление/удаление)]] (''20'')
## А что делать, когда у нас есть левая и правая оболочки?
## Не написано, как определять эти случаи, и вообще надо по-другому делать
## Пояснить подробней про сложные случаи
#:* Переименовать конспект без "достаточно"
#:* Добавить категории
# [[Выпуклая оболочка в n-мерном пространстве]] (''15'')
## Убрать плашку вверху
## Рассказать про QuickHull и вероятностный алгоритм (а только потом уже про сложный)
#:* Добавить категории и источники информации
# [[Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]] (''10'')
## Переименовать конспект в просто триангуляцию и ушную триангуляцию, выпилить в отдельный конспект
## А зачем нужно два уха?
## Нужно подробней написать, почему работает за O(n^2), сейчас это непонятно из конспекта, кажется, что за куб
#:* Интервики на число триангуляций (числа Каталана)
#:* Отформатировать псевдокод
#:* Добавить источники информации
# [[Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой]]
# [[Пересечение полуплоскостей, связь с выпуклыми оболочками]] (10)
## Написать подробней
## Почему соответствует выпуклой оболочке?
# [[Алгоритм Бентли-Оттмана]]
# [[Пересечение множества отрезков | Пересечение множества отрезков ]] (''15'')
## Помёрджить с конспектом про Бентли-Оттмана
## Написать понятный конспект с описанием всех шагов и частных случаев
# [[Алгоритм Балабана]] <tex>^\star</tex>
# [[Конфигурация]]
# [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых]] (''20'')
## Объединить с предыдудущим конспектом
## Получше объяснить строение DCEL, можно дать псевдокоды простых операций (соединение двух вершин ребром, то есть добавление диагонали)
## Подробно расписать задачу Line Arrangment, со всеми случаями и доказательством времени работы
#:* Таблички сделать красивые
#:* Оформить правильно источники информации
#:* Добавить категории
# [[Пересечение многоугольников (PSLG overlaying)]] (''25'')
## Полностью переписать конспект, здесь лишь неадекватный перевод де Берга
# [[ Сумма Минковского (определение, вычисление) | Сумма Минковского (определение, вычисление) ]] (''20'')
## Подробней описание, что это такое и зачем надо
## Доказать получше экстремальность вершины в заданном направлении как сумму двух вершин в этом направлении
## Доказать выпуклость суммы минковского двух выпуклых фигур
#:* Отформатировать псевдокод
#:* Источники информации, категории
→10. Планирование движения (Motion planning)
Нумерованные замечания {{---}} по содержанию, маркированные {{---}} по оформлению
== Модель вычислений 1. Основание вычислительной геометрии ==# '''взяли''' [[ Аффинное пространство ]] (''??'')## Написать# '''взяли''' [[ Ориентация и объем ]] (''??'')## Написать# [[ Скалярное произведение и метрика ]] (''??'')## Написать# [[ Однородные координаты ]] (''??'')## Написать === Арифметика =2. Вычисление геометрических предикатов ==
# [[Представление чисел с плавающей точкой]] (''5'')
## Помёрджить с аналогичным конспектом по дискретке
#:* Дефисы заменить на тире
#:* Заменить знаки неравенств
# [[Предикат "левый поворот"]] (''10'')
## Перенести расчёт погрешности из конспекта про вещественные числа сюда
## Сказать, почему в расчёте не используется деление, и что обычно с этим делают
## Статью написать именно про предикат поворота, про его сакральный смысл, а не про пересечение отрезков; можно добавить различных применений
## Добавить пример, простое правило для запоминания направления
#:* Неплохо бы векторные картинки сделать вместо таких растровых
#:* Добавить категории
#:* Добавить источники информации
# [[Пересечение отрезков и поворот: определение, свойства, вычисление]] (''15'')
## Подробное и ясное объяснение шагов с картинками (взять часть информации из предиката поворота), вот [http://martin-thoma.com/how-to-check-if-two-line-segments-intersect/ здесь] детальный разбор этой задачи
## Про аффинное пространство будет отдельный конспект (если кто-нибудь напишет), поэтому только небольшую справку в начале надо сделать
## Рассказать про нахождение самой точки пересечения двух отрезков, и какие проблемы с этим связаны
#:* Переменные и константы в Tex
#:* Интервики
#:* Оформить правильно источники информации
#:* Отформатировать псевдокод, оформить как функцию, принимающих два отрезка, код смотреть в cg
#:* Добавить категории
#:* Заменить math на tex
# [[ Adaptive precision arithmetic ]]
# [[Интервальная арифметика]] (''10'')
## Какой-нибудь пример с кодом на c++ (желательно предикат левый поворот) и с объяснением происходящего
#:* Оформить правильно Источники информации
#:* Добавить категории
== 3. Пересечение отрезков ==# [[Adaptive precision arithmeticАлгоритм Бентли-Оттмана]]=== Технические подробности ===# [[Запуск проекта визуализации cgПересечение множества отрезков | Пересечение множества отрезков ]] (''1015'')## Небольшой туториал, как начать работу Помёрджить с конспектом про Бентли-Оттмана## Написать понятный конспект с библиотекой визуализации, что поставить описанием всех шагов и как запуститьчастных случаев# [[Snap rounding]] (''30'')## Неплохо бы ещё скриншоты Написать полноценный конспект про SR по алгоритму на пучках, добавить наивный алгоритм# [[Пересечение отрезков на сфере]] (чтобы совсем всем ''10'')## Доделать конспект: описать всё было формально, подробно и понятно)#:* Задачу в Шаблон#:* Алгоритм красиво оформить#:* Источники информации#:* Категории == 4. Выпуклые оболочки ==# [[CMake_Tutorial|Туториал по cmakeСтатические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull]] (''1510'')## Сделать См. обсуждения## В некоторых местах не очень понятно, почему это правда - пояснить корректность алгоритма## Про Чена очень мало, смотреть википедию русскую#:* Определение жирным#:* Дефисы на тире#:* Все ссылки в конец, оформить правильно Источники информации#:* Добавить в ссылки примеры кодов (из cg, ещё можно где-нибудь нагуглить)#:* Опустить заголовки на 1, сделать конспект более формальнымструктурированным#:* Отформатировать псевдокоды# Как установить, что вообще надо [[Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка (log^2 на добавление/удаление)]] (ссылки добавить''20'')## Простые А что делать, когда у нас есть левая и последовательные примеры: сборка простого файла, нескольких файловправая оболочки?## Не написано, как подключить бустопределять эти случаи, gmp, gtestи вообще надо по-другому делать## Объяснение происходящего в библиотеке визуализации cgПояснить подробней про сложные случаи## Примеры полных скриптовВсё ещё ничего не понятно#:* Переименовать конспект без "достаточно"
#:* Добавить категории
# [[Выпуклая оболочка в n-мерном пространстве]] (''15'')## Убрать плашку вверху## Рассказать про QuickHull и вероятностный алгоритм (а только потом уже про сложный)#:* Добавить ссылоккатегории и источники информации# [[Тестирование Пересечение полуплоскостей, связь с использованием Google Testвыпуклыми оболочками]] (''10'')## Написать подробней## Почему соответствует выпуклой оболочке? == 5. Поиск ==# [[К-d деревья и перечисление точек в произвольном прямоугольнике (статика)]] (''5'')## Ссылка Мы ищем медиану по разным кординатам каждый раз, разве нам достаточно просто как-то посортить точки?## Более подробное доказательство асимптотики времени работы, разбор случаев, сказать, что оценка довольно грубая, на код битаяпрактике чуть быстрей, добавить пример кода с githubхотя всё равно медленно #:* Оформить правильно англоязычные термины#:* Оформить правильно источники информации#:* Отформатировать псевдокод#:* Задачу Функции в Шаблонтексте взять в \mathrm#:* Неплохо бы для понимания добавить картинки из гуглящейся презентации
#:* Добавить категории
# [[Квадродеревья | Квадродерево, сжатое квадродерево]] (''10'')
## А зачем оно надо?
#:* Оформить правильно источники информации
#:* Добавить категории
# [[Skip quadtree: определение, время работы | Skip quadtree: определение, время работы, запрос точек в прямоугольнике ]]# [[К-d деревья и перечисление точек в произвольном прямоугольнике (статика)]] (''5'')## Мы ищем медиану по разным кординатам каждый раз, разве нам достаточно просто как-то посортить точки?## Более подробное доказательство асимптотики времени работы, разбор случаев, сказать, что оценка довольно грубая, на практике чуть быстрей, хотя всё равно медленно #:* Оформить правильно англоязычные термины#:* Оформить правильно источники информации#:* Отформатировать псевдокод#:* Функции в тексте взять в \mathrm#:* Неплохо бы для понимания добавить картинки из гуглящейся презентации#:* Добавить категории
# [[Ортогональный поиск]]
## Впихнуть в Range tree (берётся вместе со следующим конспектом)
#:* Оформить правильно источники информации
#:* Добавить категории
# [[Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)]] (''5'')
## Чуть подробней написать про решение задачи, как находим, как упорядочиваем отрезки, добавить картинки опять же
#:* Задачу в Шаблон
#:* Правильно оформить англ. термины
#:* Оформить правильно источники информации
# [[Дерево интервалов (interval tree) и пересечение точки с множеством интервалов]] (''5'')
## Неплохо бы добавить ссылку на код реализации, довольно простая структура
#:* Добавить категории
#:* Добавить источники информации
# [[Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)BSP-дерево ]] (''5'')## Чуть подробней написать про решение задачи, как находим, как упорядочиваем отрезки, добавить картинки опять же#:* Задачу в Шаблон#:* Правильно оформить англ. термины#:* Оформить правильно источники информации
== Аффинное пространство ===== Простые геометрические операции и алгоритмы =6. Триангуляция ==# [[Предикат "левый поворот"Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]] (''10'')## Перенести расчёт погрешности из конспекта про вещественные числа сюдаПереименовать конспект в просто триангуляцию и ушную триангуляцию, выпилить в отдельный конспект## Сказать, почему в расчёте не используется деление, и что обычно с этим делаютА зачем нужно два уха?## Статью Нужно подробней написать именно про предикат поворота, про его сакральный смыслпочему работает за O(n^2), сейчас это непонятно из конспекта, а не про пересечение отрезков; можно добавить различных применений## Добавить примеркажется, простое правило для запоминания направлениячто за куб#:* Неплохо бы векторные картинки сделать вместо таких растровыхИнтервики на число триангуляций (числа Каталана)#:* Добавить категорииОтформатировать псевдокод
#:* Добавить источники информации
# [[Пересечение отрезков Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой]] == 7. ППЛГ и поворот: определение, свойства, вычислениеРСДС ==# [[Конфигурация]] (''1510'')## Подробное и ясное объяснение шагов с картинками Информацию про DCEL, его свойства, простые примеры операций (взять часть информации из предиката поворотасоединение двух вершин ребром, то есть добавление диагонали), вот [http://martin-thoma.com/how-to-check-if-two-line-segments-intersect/ здесь] детальный разбор этой задачи## Про аффинное пространство будет отдельный Оставить только общий конспект (если кто-нибудь напишет), поэтому только небольшую справку в начале надо сделать## Рассказать про нахождение самой точки пересечения двух отрезков, конфигурации и какие проблемы с этим связаны#:* Переменные и константы DCEL в Texчастности#:* ИнтервикиТаблички сделать красивые
#:* Оформить правильно источники информации
#:* Добавить категории
# [[Пересечение отрезков на сфереППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых]] (''1015'')## Доделать конспект: описать всё формально, подробно и понятно#:* Задачу в Шаблон#:* Алгоритм красиво оформить#:* Источники информации#:* Категории Написать полный разбор задачи Line Arrangement со всякими подробностями типа точного вычисления предикатов# [[Пересечение окружностеймногоугольников (PSLG overlaying)]] (10)## Добавить расчёт погрешностей (см== 8. список тем)## Переходы бы подробней описать#:* Увеличить дроби#:* Добавить категории Алгоритмы локализации ==
# [[Принадлежность точки выпуклому и невыпуклому многоугольникам]] (''5'')
## Картинка в случае выпуклого многоугольника
#:* Добавить категории
#:* min и max заменить на \min и \max
# [[Локализация в ППЛГ методом полос (персистентные деревья) | Локализация в ППЛГ методом полос (персистентные деревья)]] (''5'')
## Добавить несколько больше информации в введение из лекций Станкевича
#:* Оформить правильно источники информации
#:* Добавить категории
== 9. Триангуляция Делоне и диаграмма Вороного ==# [[Упрощение полигональной цепиТриангуляция Делоне | Триангуляция Делоне ]] (''530'')## Добавить преимущества Дугласа-ПекераЧуть подробней расписать первую теорему, расписать координаты в векторе, пояснить результат## Структурней описать алгоритм локализации## Подробные доказательства всех лем для локализации## Точнее и подробней про констрейнты рассказать## Доказать парочку якобы очевидных фактов#:* Чуть-чуть поправить структуру конспектаУвеличить дроби#:* Задачу в ШаблонЗаменить знаки неравенст#:* Оформить правильно Источники информации#:* Внутренние ссылки сделать примечаниямиКатегории# [[ Диаграмма Вороного | Диаграмма Вороного ]] (''30'')# [[ Motorcycle graph ]]# [[ Straight skeleton ]] == 10. Планирование движения (Motion planning) ==# [[ Сумма Минковского (определение, вычисление) | Сумма Минковского (определение, вычисление) ]] (''20'')## Подробней описание, что это такое и зачем надо## Доказать получше экстремальность вершины в заданном направлении как сумму двух вершин в этом направлении## Доказать выпуклость суммы минковского двух выпуклых фигур
#:* Отформатировать псевдокод
#:* Заменить знаки неравенствИсточники информации, категории# [[Snap roundingVisibility graph и motion planning | Visibility graph и motion planning ]] (''3025'')## Сказать в лемму про разрешение графа ещё про невыпуклые вершины '''(лемма без названия)'''## Написать полноценный конспект Добавить про SR упрощение путей по алгоритму навигационным картам '''(http://habrahabr.ru/post/199256/ дорожные карты)'''## В картинке про заметающий луч, кажется, бага - надо получше объяснить, что на пучкахней нарисовано '''(Lee’s Algorithm)'''## Ещё пояснить, почему мы рассматриваем только правую полуплоскость (и вообще как сортим вдоль луча, добавить наивный алгоритмэто мб нетривиально в некоторых случаях) '''(Lee’s Algorithm)'''## Доказать, что после суммы минковского препятствий будет не очень много углов внутри полигонов '''(Motion planning)'''# [[BSP-дерево]]:* Оформить правильно Источники информации '''(перенести Overmars and Welzl’s Algorithm)'''#:* Некоторые картинки можно красивей нарисовать#:* Заменить знаки неравенств '''(??)'''
== Скалярное произведение и мера (проверяется) 11. Задачи ==
# [[Диаметр множества точек (вращающиеся калиперы)]] (''10'')
## Картинку с пояснением определения следующей стороны для вращения при помощи поворота
#:* Задачу в шаблон
#:* Оформить правильно источники информации
# [[Минимальная охватывающая окружность множества точек]] (''25'')
## Рассказать, почему выпуклая оболочка (или диаметр двух дальних точек не подходят или подходят)
#:* Оформить правильно источники информации
#:* Добавить категории
# [[ Visibility graph и motion planning | Visibility graph и motion planning Пересечение окружностей]] (''2510'')## Сказать в лемму про разрешение графа ещё про невыпуклые вершиныДобавить расчёт погрешностей (см. список тем)## Добавить про упрощение путей по навигационным картамПереходы бы подробней описать#:* Увеличить дроби# В картинке про заметающий луч, кажется, бага - надо получше объяснить, что на ней нарисовано:* Добавить категории ## Ещё пояснить, почему мы рассматриваем только правую полуплоскость [[Упрощение полигональной цепи]] (и вообще как сортим вдоль луча, это мб нетривиально в некоторых случаях''5'')## Доказать, что после суммы минковского препятствий будет не очень много углов внутри полигоновДобавить преимущества Дугласа-Пекера#:* Чуть-чуть поправить структуру конспекта#:* Задачу в Шаблон
#:* Оформить правильно Источники информации
#:* Некоторые картинки можно красивей нарисоватьВнутренние ссылки сделать примечаниями#:* Отформатировать псевдокод
#:* Заменить знаки неравенств
#:* Отформатировать псевдокоды[[ Вычисление площади и объема ]] (''15'')## Написать# [[ Пересечение выпуклых многоугольников ]] (''15'')## Написать == 12. Программирование ==# [[ Триангуляция Делоне | Триангуляция Делоне Запуск проекта визуализации cg]] (''3010'')## Чуть подробней расписать первую теоремуНебольшой туториал, расписать координаты в векторекак начать работу с библиотекой визуализации, пояснить результатчто поставить и как запустить## Структурней описать алгоритм локализацииНеплохо бы ещё скриншоты добавить (чтобы совсем всем всё было понятно)# [[CMake_Tutorial|Туториал по cmake]] (''15'')## Подробные доказательства всех лем для локализацииСделать конспект более формальным## Точнее Как установить, что вообще надо (ссылки добавить)## Простые и подробней про констрейнты рассказатьпоследовательные примеры: сборка простого файла, нескольких файлов, как подключить буст, gmp, gtest## Доказать парочку якобы очевидных фактовОбъяснение происходящего в библиотеке визуализации cg#:* Увеличить дроби#:* Заменить знаки неравенстПримеры полных скриптов#:* Источники информацииДобавить категории#:* КатегорииДобавить ссылок# [[ Диаграмма Вороного | Диаграмма Вороного Тестирование с использованием Google Test]] (''305'')## Написать адекватный конспект - инкрементальное построение ДВ, ДВ k-ого порядка, начатьСсылка на код битая, конечно, следует добавить пример кода с наивного алгоритма пересечения полуплоскостейgithub#:* Задачу в Шаблон# :* Добавить про связь с триангуляцией делонекатегории# [[Motorcycle graph]]:* Интервики# [[Straight skeleton]]:* Имя функции в \mathrm
