3622
правки
Изменения
м
## Написать адекватный конспект - инкрементальное построение ДВ, ДВ k-ого порядка, начать, конечно, следует с наивного алгоритма пересечения полуплоскостей
## Добавить про связь с триангуляцией делоне
→10. Планирование движения (Motion planning)
Нумерованные замечания {{---}} по содержанию, маркированные {{---}} по оформлению
== 1. Основание вычислительной геометрии ==
# '''взяли''' [[ Аффинное пространство ]](''??'')
## Написать
# '''взяли''' [[ Ориентация и объем ]](''??'')
## Написать
# [[ Скалярное произведение и метрика ]](''??'')
## Написать
# [[ Однородные координаты ]](''??'')
## Написать
== 2. Вычисление геометрических предикатов ==
# [[Представление чисел с плавающей точкой]] (''5'')
#:* Отформатировать псевдокод, оформить как функцию, принимающих два отрезка, код смотреть в cg
#:* Добавить категории
#:* Заменить math на tex
# [[ Adaptive precision arithmetic ]]
# [[Интервальная арифметика]] (''10'')
== 3. Пересечение отрезков ==
# '''xxx''' [[Алгоритм Бентли-Оттмана]]# '''xxx''' [[Пересечение множества отрезков | Пересечение множества отрезков ]] (''15'')
## Помёрджить с конспектом про Бентли-Оттмана
## Написать понятный конспект с описанием всех шагов и частных случаев
#:* Опустить заголовки на 1, сделать конспект более структурированным
#:* Отформатировать псевдокоды
# '''xxx''' [[Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка (log^2 на добавление/удаление)]] (''20'')
## А что делать, когда у нас есть левая и правая оболочки?
## Не написано, как определять эти случаи, и вообще надо по-другому делать
## Пояснить подробней про сложные случаи
## Всё ещё ничего не понятно
#:* Переименовать конспект без "достаточно"
#:* Добавить категории
# [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых]] (''15'')
## Написать полный разбор задачи Line Arrangement со всякими подробностями типа точного вычисления предикатов
# [[Пересечение многоугольников (PSLG overlaying)]] (''25'')## Полностью переписать конспект, здесь лишь непонятный перевод де Берга
== 8. Алгоритмы локализации ==
#:* Категории
# [[ Диаграмма Вороного | Диаграмма Вороного ]] (''30'')
# [[ Motorcycle graph ]]
# [[ Straight skeleton ]]
#:* Источники информации, категории
# [[ 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. Задачи ==
