Изменения

== Модель вычислений 1. Основание вычислительной геометрии ==# '''взяли''' [[ Аффинное пространство ]] (''??'')## Написать# '''взяли''' [[ Ориентация и объем ]] (''??'')## Написать# [[ Скалярное произведение и метрика ]] (''??'')## Написать# [[ Однородные координаты ]] (''??'')## Написать === Арифметика =2. Вычисление геометрических предикатов ==

 == 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#:* Неплохо бы для понимания добавить картинки из гуглящейся презентации

# [[Skip quadtree: определение, время работы | Skip quadtree: определение, время работы, запрос точек в прямоугольнике ]]# [[К-d деревья и перечисление точек в произвольном прямоугольнике (статика)]] (''5'')## Мы ищем медиану по разным кординатам каждый раз, разве нам достаточно просто как-то посортить точки?## Более подробное доказательство асимптотики времени работы, разбор случаев, сказать, что оценка довольно грубая, на практике чуть быстрей, хотя всё равно медленно #:* Оформить правильно англоязычные термины#:* Оформить правильно источники информации#:* Отформатировать псевдокод#:* Функции в тексте взять в \mathrm#:* Неплохо бы для понимания добавить картинки из гуглящейся презентации#:* Добавить категории

# [[Пересечение прямоугольника с множеством непересекающихся отрезков (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'')## Добавить несколько больше информации в введение из лекций Станкевича## Добавить картинок из гуглящейся презенташки#:* Задачу в Шаблон#:* Убрать плашку вверху#:* Интервики на персистентые деревья#:* Добавить категории# [[Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ. Алгоритм Киркпатрика ]] (''10'')## Добавить другой критерий выбора удаляемых вершин по степени (презенташка гуглится), доказать его корректность, сравнить с существующим## Рассказать про перетриангуляцию (как эффективно и как всё в DCEL вообще происходит)#:* Отформатировать псевдокод#: Джарвис* Пофиксить категории#:* Увеличить дроби# [[Трапецоидная карта]] (''20'')## Сказать, что в статике можно строить заметающей прямой трапецоидную карту (и сказать, как строить)## Про мнимую оболочку сказать получше - окружаем прямоугольником отрезки## Чуть переформулировать постановку (всё же решаем задачу локализации, а не поиска пути, но про него можно отдельно сказать)## Сказать в начале, Грэхемкакие частные случаи не рассматриваем## Более подробные псевдокоды, Эндрюну и вообще конспект сделать более структурированным## Добавить худший случай для построения## Доказательства асимптотик можно сделать попроще, используя регрессионный анализ#:* Задачу в Шаблон#:* Оформить правильно источники информации#:* Добавить категории == 9. Триангуляция Делоне и диаграмма Вороного ==# [[ Триангуляция Делоне | Триангуляция Делоне ]] (''30'')## Чуть подробней расписать первую теорему, Ченрасписать координаты в векторе, QuickHullпояснить результат## Структурней описать алгоритм локализации## Подробные доказательства всех лем для локализации## Точнее и подробней про констрейнты рассказать## Доказать парочку якобы очевидных фактов#:* Увеличить дроби#:* Заменить знаки неравенст#:* Источники информации#:* Категории# [[ Диаграмма Вороного | Диаграмма Вороного ]] (''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'')## Картинку с пояснением определения следующей стороны для вращения при помощи поворота## Сказать, оформить правильно Источники информациичто поиск минимальной охватывающей окружности тут не прокатывает (с контрпримером)#:* Добавить Задачу в ссылки примеры кодов шаблон#:* Оформить правильно источники информации# [[Минимальная охватывающая окружность множества точек]] (из cg''25'')## Рассказать, ещё можно где-нибудь нагуглитьпочему выпуклая оболочка (или диаметр двух дальних точек не подходят или подходят)## Добавить реализацию через одну функцию## Нормальное и понятное доказательство корректности с картинками## Добавить оптимизации по скорости## А зачем оно вообще надо?#:* Опустить заголовки на 1, сделать конспект более структурированнымУбрать плашку вверху#:* Заменить знаки неравенств

=== Продвинутые алгоритмы ===#:* Оформить правильно источники информации# [[Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка (log^2 на добавление/удаление)]]:* Добавить категории# [[Выпуклая оболочка в n-мерном пространствеПересечение окружностей]](''10'')# [[Триангуляция полигонов # Добавить расчёт погрешностей (ушная + монотоннаясм. список тем)#Ушной метод | Триангуляция многоугольника за n^2]]# [[Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой]]Переходы бы подробней описать# [[Пересечение полуплоскостей, связь с выпуклыми оболочками]]:* Увеличить дроби# [[Алгоритм Бентли-Оттмана]]:* Добавить категории # [[Пересечение множества отрезков | Пересечение множества отрезков Упрощение полигональной цепи]] (''155'')## Помёрджить с конспектом про БентлиДобавить преимущества Дугласа-ОттманаПекера#:* Чуть-чуть поправить структуру конспекта# Написать понятный конспект с описанием всех шагов и частных случаев:* Задачу в Шаблон#:* Оформить правильно Источники информации#:* Внутренние ссылки сделать примечаниями# [[Алгоритм Балабана]] <tex>^\star</tex>:* Отформатировать псевдокод# [[Конфигурация]]:* Заменить знаки неравенств# [[ППЛГ Вычисление площади и РСДС объема ]] (PSLG и DCEL''15''): определение, построение РСДС множества прямых]]## Написать# [[Пересечение выпуклых многоугольников (PSLG overlaying)]]# [[Локализация в ППЛГ методом полос (персистентные деревья) | Локализация в ППЛГ методом полос (персистентные деревья''15'')]]# [[Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ# Написать  == 12. Алгоритм Киркпатрика ]]Программирование ==# [[Трапецоидная картаЗапуск проекта визуализации cg]](''10'')# [[Упрощение полигональной цепи]]# Небольшой туториал, как начать работу с библиотекой визуализации, что поставить и как запустить# [[Snap rounding]]# Неплохо бы ещё скриншоты добавить (чтобы совсем всем всё было понятно)# [[BSP-деревоCMake_Tutorial|Туториал по cmake]]== Скалярное произведение и мера (проверяется''15'') ==# [[ Диаметр множества точек (вращающиеся калиперы) | Диаметр множества точек # Сделать конспект более формальным## Как установить, что вообще надо (вращающиеся калиперыссылки добавить) ]]# [[ Сумма Минковского (определение# Простые и последовательные примеры: сборка простого файла, нескольких файлов, как подключить буст, вычисление) | Сумма Минковского (определениеgmp, вычисление) ]]gtest## Объяснение происходящего в библиотеке визуализации cg## Примеры полных скриптов#:* Добавить категории#:* Добавить ссылок# [[ Минимальная охватывающая окружность множества точек | Минимальная охватывающая окружность множества точек Тестирование с использованием Google Test]](''5'')# [[ Visibility graph и motion planning | Visibility graph и motion planning ]]# Ссылка на код битая, добавить пример кода с github# [[ Триангуляция Делоне | Триангуляция Делоне ]]:* Задачу в Шаблон# [[ Диаграмма Вороного | Диаграмма Вороного ]]:* Добавить категории# [[Motorcycle graph]]:* Интервики# [[Straight skeleton]]:* Имя функции в \mathrm