3622
правки
Изменения
Нет описания правки
Нумерованные замечания {{---}} по содержанию, маркированные {{---}} по оформлению
== Модель вычислений 1. Основание вычислительной геометрии ==# [[ Аффинное пространство ]]## Написать# [[ Ориентация и объем ]]## Написать# [[ Скалярное произведение и метрика ]]## Написать# [[ Однородные координаты ]]## Написать=== Арифметика =2. Вычисление геометрических предикатов ==
# [[Представление чисел с плавающей точкой]] (''5'')
## Помёрджить с аналогичным конспектом по дискретке
#:* Дефисы заменить на тире
#:* Заменить знаки неравенств
# [[Предикат "левый поворот"]] (''10'')
## Перенести расчёт погрешности из конспекта про вещественные числа сюда
## Сказать, почему в расчёте не используется деление, и что обычно с этим делают
## Статью написать именно про предикат поворота, про его сакральный смысл, а не про пересечение отрезков; можно добавить различных применений
## Добавить пример, простое правило для запоминания направления
#:* Неплохо бы векторные картинки сделать вместо таких растровых
#:* Добавить категории
#:* Добавить источники информации
# [[Пересечение отрезков и поворот: определение, свойства, вычисление]] (''15'')
## Подробное и ясное объяснение шагов с картинками (взять часть информации из предиката поворота), вот [http://martin-thoma.com/how-to-check-if-two-line-segments-intersect/ здесь] детальный разбор этой задачи
## Про аффинное пространство будет отдельный конспект (если кто-нибудь напишет), поэтому только небольшую справку в начале надо сделать
## Рассказать про нахождение самой точки пересечения двух отрезков, и какие проблемы с этим связаны
#:* Переменные и константы в Tex
#:* Интервики
#:* Оформить правильно источники информации
#:* Отформатировать псевдокод, оформить как функцию, принимающих два отрезка, код смотреть в cg
#:* Добавить категории
# [[ 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'')## Чуть подробней написать про решение задачи, как находим, как упорядочиваем отрезки, добавить картинки опять же#:* Задачу в Шаблон#:* Правильно оформить англ. термины#:* Оформить правильно источники информации
== Аффинное пространство ===== Простые геометрические операции и алгоритмы ===# [[Предикат "левый поворот"]] (''10'')## Перенести расчёт погрешности из конспекта про вещественные числа сюда## Сказать, почему в расчёте не используется деление, и что обычно с этим делают## Статью написать именно про предикат поворота, про его сакральный смысл, а не про пересечение отрезков; можно добавить различных применений## Добавить пример, простое правило для запоминания направления#:* Неплохо бы векторные картинки сделать вместо таких растровых#:* Добавить категории#:* Добавить источники информации# [[Пересечение отрезков и поворот: определение, свойства, вычисление]] (''15'')## Подробное и ясное объяснение шагов с картинками (взять часть информации из предиката поворота), вот [http://martin-thoma.com/how-to-check-if-two-line-segments-intersect/ здесь] детальный разбор этой задачи## Про аффинное пространство будет отдельный конспект (если кто-нибудь напишет), поэтому только небольшую справку в начале надо сделать## Рассказать про нахождение самой точки пересечения двух отрезков, и какие проблемы с этим связаны#:* Переменные и константы в Tex#:* Интервики#:* Оформить правильно источники информации#:* Отформатировать псевдокод, оформить как функцию, принимающих два отрезка, код смотреть в cg#:* Добавить категории# [[Пересечение отрезков на сфере]] (''10'')## Доделать конспект: описать всё формально, подробно и понятно#:* Задачу в Шаблон#:* Алгоритм красиво оформить#:* Источники информации#:* Категории # [[Пересечение окружностей]] (10)## Добавить расчёт погрешностей (см. список тем)## Переходы бы подробней описать#:* Увеличить дроби#:* Добавить категории # [[Принадлежность точки выпуклому и невыпуклому многоугольникам]] (''5'')## Картинка в случае выпуклого многоугольника## Более подробное объяснение корректности алгоритма в случае невыпуклого полигона## Пару слов про то, работает ли в полигонах с дырками#:* Убрать плашку вверху#:* Оформить правильно источники информации#:* Добавить категории#:* min и max заменить на \min и \max# [[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull]] (''10'')## См6. обсуждения## В некоторых местах не очень понятно, почему это правда - пояснить корректность алгоритма## Про Чена очень мало, смотреть википедию русскую#:* Определение жирным#:* Дефисы на тире#:* Все ссылки в конец, оформить правильно Источники информации#:* Добавить в ссылки примеры кодов (из cg, ещё можно где-нибудь нагуглить)#:* Опустить заголовки на 1, сделать конспект более структурированным#:* Отформатировать псевдокоды=== Продвинутые алгоритмы =Триангуляция ==# [[Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка (log^2 на добавление/удаление)]] (''20'')## А что делать, когда у нас есть левая и правая оболочки?## Не написано, как определять эти случаи, и вообще надо по-другому делать## Пояснить подробней про сложные случаи#:* Переименовать конспект без "достаточно"#:* Добавить категории# [[Выпуклая оболочка в n-мерном пространстве]] (''15'')## Убрать плашку вверху## Рассказать про QuickHull и вероятностный алгоритм (а только потом уже про сложный)#:* Добавить категории и источники информации
# [[Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]] (''10'')
## Переименовать конспект в просто триангуляцию и ушную триангуляцию, выпилить в отдельный конспект
#:* Добавить источники информации
# [[Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой]]
#:* Таблички сделать красивые
#:* Оформить правильно источники информации
#:* Добавить категории
# [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых]] (''15'')
## Написать полный разбор задачи Line Arrangement со всякими подробностями типа точного вычисления предикатов
# [[Пересечение многоугольников (PSLG overlaying)]] (''25'')
## Полностью переписать конспект, здесь лишь неадекватный непонятный перевод де Берга == 8. Алгоритмы локализации ==# [[Принадлежность точки выпуклому и невыпуклому многоугольникам]] (''5'')## Картинка в случае выпуклого многоугольника## Более подробное объяснение корректности алгоритма в случае невыпуклого полигона## Пару слов про то, работает ли в полигонах с дырками#:* Убрать плашку вверху#:* Оформить правильно источники информации#:* Добавить категории#:* min и max заменить на \min и \max
# [[Локализация в ППЛГ методом полос (персистентные деревья) | Локализация в ППЛГ методом полос (персистентные деревья)]] (''5'')
## Добавить несколько больше информации в введение из лекций Станкевича
#:* Оформить правильно источники информации
#:* Добавить категории
== 9. Триангуляция Делоне и диаграмма Вороного ==# [[Упрощение полигональной цепиТриангуляция Делоне | Триангуляция Делоне ]] (''530'')## Чуть подробней расписать первую теорему, расписать координаты в векторе, пояснить результат## Структурней описать алгоритм локализации## Подробные доказательства всех лем для локализации## Точнее и подробней про констрейнты рассказать## Доказать парочку якобы очевидных фактов#:* Увеличить дроби#:* Заменить знаки неравенст#:* Источники информации#:* Категории# [[ Диаграмма Вороного | Диаграмма Вороного ]] (''30'')## Написать адекватный конспект - инкрементальное построение ДВ, ДВ k-ого порядка, начать, конечно, следует с наивного алгоритма пересечения полуплоскостей## Добавить преимущества Дугласа-Пекерапро связь с триангуляцией делоне# [[ Motorcycle graph ]]# [[ Straight skeleton ]] == 10. Планирование движения (Motion planning) ==# [[ Сумма Минковского (определение, вычисление) | Сумма Минковского (определение, вычисление) ]] (''20'')## Подробней описание, что это такое и зачем надо## Доказать получше экстремальность вершины в заданном направлении как сумму двух вершин в этом направлении## Доказать выпуклость суммы минковского двух выпуклых фигур#:* Чуть-чуть поправить структуру конспектаОтформатировать псевдокод#:* Задачу Источники информации, категории# [[ Visibility graph и motion planning | Visibility graph и motion planning ]] (''25'')## Сказать в лемму про разрешение графа ещё про невыпуклые вершины## Добавить про упрощение путей по навигационным картам## В картинке про заметающий луч, кажется, бага - надо получше объяснить, что на ней нарисовано## Ещё пояснить, почему мы рассматриваем только правую полуплоскость (и вообще как сортим вдоль луча, это мб нетривиально в Шаблоннекоторых случаях)## Доказать, что после суммы минковского препятствий будет не очень много углов внутри полигонов
#:* Оформить правильно Источники информации
#:* Внутренние ссылки сделать примечаниями#:* Отформатировать псевдокодНекоторые картинки можно красивей нарисовать
#:* Заменить знаки неравенств
# [[Snap rounding]] (''30'')## Написать полноценный конспект про SR по алгоритму на пучках, добавить наивный алгоритм# [[BSP-дерево]]:* Отформатировать псевдокоды
== Скалярное произведение и мера (проверяется) 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
