Просмотр исходного текста страницы Участник:Shersh/Тикеты к вычислительной геометрии (термы 4 и 5)

Нумерованные замечания {{---}} по содержанию, маркированные {{---}} по оформлению
== 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