Участник:Shersh/Тикеты к вычислительной геометрии (термы 4 и 5) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Скалярное произведение и мера (проверяется))
Строка 1: Строка 1:
 
Нумерованные замечания {{---}} по содержанию, маркированные {{---}} по оформлению
 
Нумерованные замечания {{---}} по содержанию, маркированные {{---}} по оформлению
−
== Модель вычислений ==
+
== 1. Основание вычислительной геометрии ==
−
=== Арифметика ===
+
# [[ Аффинное пространство ]]
 +
## Написать
 +
# [[ Ориентация и объем ]]
 +
## Написать
 +
# [[ Скалярное произведение и метрика ]]
 +
## Написать
 +
# [[ Однородные координаты ]]
 +
## Написать
 +
== 2. Вычисление геометрических предикатов ==
 
# [[Представление чисел с плавающей точкой]] (''5'')
 
# [[Представление чисел с плавающей точкой]] (''5'')
 
## Помёрджить с аналогичным конспектом по дискретке
 
## Помёрджить с аналогичным конспектом по дискретке
Строка 9: Строка 17:
 
#:* Дефисы заменить на тире
 
#:* Дефисы заменить на тире
 
#:* Заменить знаки неравенств
 
#:* Заменить знаки неравенств
 +
# [[Предикат "левый поворот"]] (''10'')
 +
## Перенести расчёт погрешности из конспекта про вещественные числа сюда
 +
## Сказать, почему в расчёте не используется деление, и что обычно с этим делают
 +
## Статью написать именно про предикат поворота, про его сакральный смысл, а не про пересечение отрезков; можно добавить различных применений
 +
## Добавить пример, простое правило для запоминания направления
 +
#:* Неплохо бы векторные картинки сделать вместо таких растровых
 +
#:* Добавить категории
 +
#:* Добавить источники информации
 +
# [[Пересечение отрезков и поворот: определение, свойства, вычисление]] (''15'')
 +
## Подробное и ясное объяснение шагов с картинками (взять часть информации из предиката поворота), вот [http://martin-thoma.com/how-to-check-if-two-line-segments-intersect/ здесь] детальный разбор этой задачи
 +
## Про аффинное пространство будет отдельный конспект (если кто-нибудь напишет), поэтому только небольшую справку в начале надо сделать
 +
## Рассказать про нахождение самой точки пересечения двух отрезков, и какие проблемы с этим связаны
 +
#:* Переменные и константы в Tex
 +
#:* Интервики
 +
#:* Оформить правильно источники информации
 +
#:* Отформатировать псевдокод, оформить как функцию, принимающих два отрезка, код смотреть в cg
 +
#:* Добавить категории
 +
# [[ Adaptive precision arithmetic ]]
 
# [[Интервальная арифметика]] (''10'')
 
# [[Интервальная арифметика]] (''10'')
 
## Какой-нибудь пример с кодом на c++ (желательно предикат левый поворот) и с объяснением происходящего
 
## Какой-нибудь пример с кодом на c++ (желательно предикат левый поворот) и с объяснением происходящего
Строка 17: Строка 43:
 
#:* Оформить правильно Источники информации
 
#:* Оформить правильно Источники информации
 
#:* Добавить категории
 
#:* Добавить категории
−
# [[Adaptive precision arithmetic]]
+
 
−
=== Технические подробности ===
+
== 3. Пересечение отрезков ==
−
# [[Запуск проекта визуализации cg]] (''10'')
+
# [[Алгоритм Бентли-Оттмана]]
−
## Небольшой туториал, как начать работу с библиотекой визуализации, что поставить и как запустить
+
# [[Пересечение множества отрезков | Пересечение множества отрезков ]] (''15'')
−
## Неплохо бы ещё скриншоты добавить (чтобы совсем всем всё было понятно)
+
## Помёрджить с конспектом про Бентли-Оттмана
−
# [[CMake_Tutorial|Туториал по cmake]] (''15'')
+
## Написать понятный конспект с описанием всех шагов и частных случаев
−
## Сделать конспект более формальным
+
# [[Snap rounding]] (''30'')
−
## Как установить, что вообще надо (ссылки добавить)
+
## Написать полноценный конспект про SR по алгоритму на пучках, добавить наивный алгоритм
−
## Простые и последовательные примеры: сборка простого файла, нескольких файлов, как подключить буст, gmp, gtest
+
# [[Пересечение отрезков на сфере]] (''10'')
−
## Объяснение происходящего в библиотеке визуализации cg
+
## Доделать конспект: описать всё формально, подробно и понятно
−
## Примеры полных скриптов
+
#:* Задачу в Шаблон
 +
#:* Алгоритм красиво оформить
 +
#:* Источники информации
 +
#:* Категории
 +
 
 +
== 4. Выпуклые оболочки ==
 +
# [[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull]] (''10'')
 +
## См. обсуждения
 +
## В некоторых местах не очень понятно, почему это правда - пояснить корректность алгоритма
 +
## Про Чена очень мало, смотреть википедию русскую
 +
#:* Определение жирным
 +
#:* Дефисы на тире
 +
#:* Все ссылки в конец, оформить правильно Источники информации
 +
#:* Добавить в ссылки примеры кодов (из cg, ещё можно где-нибудь нагуглить)
 +
#:* Опустить заголовки на 1, сделать конспект более структурированным
 +
#:* Отформатировать псевдокоды
 +
# [[Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка (log^2 на добавление/удаление)]] (''20'')
 +
## А что делать, когда у нас есть левая и правая оболочки?
 +
## Не написано, как определять эти случаи, и вообще надо по-другому делать
 +
## Пояснить подробней про сложные случаи
 +
#:* Переименовать конспект без "достаточно"
 
#:* Добавить категории
 
#:* Добавить категории
−
#:* Добавить ссылок
+
# [[Выпуклая оболочка в n-мерном пространстве]] (''15'')
−
# [[Тестирование с использованием Google Test]] (''5'')
+
## Убрать плашку вверху
−
## Ссылка на код битая, добавить пример кода с github
+
## Рассказать про QuickHull и вероятностный алгоритм (а только потом уже про сложный)
−
#:* Задачу в Шаблон
+
#:* Добавить категории и источники информации
 +
# [[Пересечение полуплоскостей, связь с выпуклыми оболочками]] (''10'')
 +
## Написать подробней
 +
## Почему соответствует выпуклой оболочке?
 +
 
 +
== 5. Поиск ==
 +
# [[К-d деревья и перечисление точек в произвольном прямоугольнике (статика)]] (''5'')
 +
## Мы ищем медиану по разным кординатам каждый раз, разве нам достаточно просто как-то посортить точки?
 +
## Более подробное доказательство асимптотики времени работы, разбор случаев, сказать, что оценка довольно грубая, на практике чуть быстрей, хотя всё равно медленно
 +
#:* Оформить правильно англоязычные термины
 +
#:* Оформить правильно источники информации
 +
#:* Отформатировать псевдокод
 +
#:* Функции в тексте взять в \mathrm
 +
#:* Неплохо бы для понимания добавить картинки из гуглящейся презентации
 
#:* Добавить категории
 
#:* Добавить категории
−
#:* Интервики
 
−
#:* Имя функции в \mathrm
 
−
== Базовые алгоритмы и структуры данных ==
 
 
# [[Квадродеревья | Квадродерево, сжатое квадродерево]] (''10'')
 
# [[Квадродеревья | Квадродерево, сжатое квадродерево]] (''10'')
 
## А зачем оно надо?
 
## А зачем оно надо?
Строка 47: Строка 103:
 
#:* Оформить правильно источники информации
 
#:* Оформить правильно источники информации
 
#:* Добавить категории
 
#:* Добавить категории
−
# [[Skip quadtree: определение, время работы | Skip quadtree: определение, время работы, запрос точек в прямоугольнике ]]
+
# [[ Skip quadtree: определение, время работы | Skip quadtree: определение, время работы, запрос точек в прямоугольнике ]]
−
# [[К-d деревья и перечисление точек в произвольном прямоугольнике (статика)]] (''5'')
 
−
## Мы ищем медиану по разным кординатам каждый раз, разве нам достаточно просто как-то посортить точки?
 
−
## Более подробное доказательство асимптотики времени работы, разбор случаев, сказать, что оценка довольно грубая, на практике чуть быстрей, хотя всё равно медленно
 
−
#:* Оформить правильно англоязычные термины
 
−
#:* Оформить правильно источники информации
 
−
#:* Отформатировать псевдокод
 
−
#:* Функции в тексте взять в \mathrm
 
−
#:* Неплохо бы для понимания добавить картинки из гуглящейся презентации
 
−
#:* Добавить категории
 
 
# [[Ортогональный поиск]]
 
# [[Ортогональный поиск]]
 
## Впихнуть в Range tree (берётся вместе со следующим конспектом)
 
## Впихнуть в Range tree (берётся вместе со следующим конспектом)
Строка 71: Строка 118:
 
#:* Оформить правильно источники информации
 
#:* Оформить правильно источники информации
 
#:* Добавить категории
 
#:* Добавить категории
 +
# [[Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)]] (''5'')
 +
## Чуть подробней написать про решение задачи, как находим, как упорядочиваем отрезки, добавить картинки опять же
 +
#:* Задачу в Шаблон
 +
#:* Правильно оформить англ. термины
 +
#:* Оформить правильно источники информации
 
# [[Дерево интервалов (interval tree) и пересечение точки с множеством интервалов]] (''5'')
 
# [[Дерево интервалов (interval tree) и пересечение точки с множеством интервалов]] (''5'')
 
## Неплохо бы добавить ссылку на код реализации, довольно простая структура
 
## Неплохо бы добавить ссылку на код реализации, довольно простая структура
Строка 87: Строка 139:
 
#:* Добавить категории
 
#:* Добавить категории
 
#:* Добавить источники информации
 
#:* Добавить источники информации
−
# [[Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)]] (''5'')
+
# [[ BSP-дерево ]]
−
## Чуть подробней написать про решение задачи, как находим, как упорядочиваем отрезки, добавить картинки опять же
 
−
#:* Задачу в Шаблон
 
−
#:* Правильно оформить англ. термины
 
−
#:* Оформить правильно источники информации
 
  
−
== Аффинное пространство ==
+
== 6. Триангуляция ==
−
=== Простые геометрические операции и алгоритмы ===
 
−
# [[Предикат "левый поворот"]] (''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'')
 
−
## См. обсуждения
 
−
## В некоторых местах не очень понятно, почему это правда - пояснить корректность алгоритма
 
−
## Про Чена очень мало, смотреть википедию русскую
 
−
#:* Определение жирным
 
−
#:* Дефисы на тире
 
−
#:* Все ссылки в конец, оформить правильно Источники информации
 
−
#:* Добавить в ссылки примеры кодов (из cg, ещё можно где-нибудь нагуглить)
 
−
#:* Опустить заголовки на 1, сделать конспект более структурированным
 
−
#:* Отформатировать псевдокоды
 
−
=== Продвинутые алгоритмы ===
 
−
# [[Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка (log^2 на добавление/удаление)]] (''20'')
 
−
## А что делать, когда у нас есть левая и правая оболочки?
 
−
## Не написано, как определять эти случаи, и вообще надо по-другому делать
 
−
## Пояснить подробней про сложные случаи
 
−
#:* Переименовать конспект без "достаточно"
 
−
#:* Добавить категории
 
−
# [[Выпуклая оболочка в n-мерном пространстве]] (''15'')
 
−
## Убрать плашку вверху
 
−
## Рассказать про QuickHull и вероятностный алгоритм (а только потом уже про сложный)
 
−
#:* Добавить категории и источники информации
 
 
# [[Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]] (''10'')
 
# [[Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]] (''10'')
 
## Переименовать конспект в просто триангуляцию и ушную триангуляцию, выпилить в отдельный конспект
 
## Переименовать конспект в просто триангуляцию и ушную триангуляцию, выпилить в отдельный конспект
Строка 160: Строка 150:
 
#:* Добавить источники информации
 
#:* Добавить источники информации
 
# [[Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой]]
 
# [[Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой]]
−
# [[Пересечение полуплоскостей, связь с выпуклыми оболочками]] (10)
+
 
−
## Написать подробней
+
== 7. ППЛГ и РСДС ==
−
## Почему соответствует выпуклой оболочке?
+
# [[Конфигурация]] (''10'')
−
# [[Алгоритм Бентли-Оттмана]]
+
## Информацию про DCEL, его свойства, простые примеры операций (соединение двух вершин ребром, то есть добавление диагонали)
−
# [[Пересечение множества отрезков | Пересечение множества отрезков ]] (''15'')
+
## Оставить только общий конспект про конфигурации и DCEL в частности
−
## Помёрджить с конспектом про Бентли-Оттмана
 
−
## Написать понятный конспект с описанием всех шагов и частных случаев
 
−
# [[Алгоритм Балабана]] <tex>^\star</tex>
 
−
# [[Конфигурация]]
 
−
# [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых]] (''20'')
 
−
## Объединить с предыдудущим конспектом
 
−
## Получше объяснить строение DCEL, можно дать псевдокоды простых операций (соединение двух вершин ребром, то есть добавление диагонали)
 
−
## Подробно расписать задачу Line Arrangment, со всеми случаями и доказательством времени работы
 
 
#:* Таблички сделать красивые
 
#:* Таблички сделать красивые
 
#:* Оформить правильно источники информации
 
#:* Оформить правильно источники информации
 
#:* Добавить категории
 
#:* Добавить категории
 +
# [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых]] (''15'')
 +
## Написать полный разбор задачи Line Arrangement со всякими подробностями типа точного вычисления предикатов
 
# [[Пересечение многоугольников (PSLG overlaying)]] (''25'')
 
# [[Пересечение многоугольников (PSLG overlaying)]] (''25'')
−
## Полностью переписать конспект, здесь лишь неадекватный перевод де Берга
+
## Полностью переписать конспект, здесь лишь непонятный перевод де Берга
 +
 
 +
== 8. Алгоритмы локализации ==
 +
# [[Принадлежность точки выпуклому и невыпуклому многоугольникам]] (''5'')
 +
## Картинка в случае выпуклого многоугольника
 +
## Более подробное объяснение корректности алгоритма в случае невыпуклого полигона
 +
## Пару слов про то, работает ли в полигонах с дырками
 +
#:* Убрать плашку вверху
 +
#:* Оформить правильно источники информации
 +
#:* Добавить категории
 +
#:* min и max заменить на \min и \max
 
# [[Локализация в ППЛГ методом полос (персистентные деревья) | Локализация в ППЛГ методом полос (персистентные деревья)]] (''5'')
 
# [[Локализация в ППЛГ методом полос (персистентные деревья) | Локализация в ППЛГ методом полос (персистентные деревья)]] (''5'')
 
## Добавить несколько больше информации в введение из лекций Станкевича
 
## Добавить несколько больше информации в введение из лекций Станкевича
Строка 202: Строка 196:
 
#:* Оформить правильно источники информации
 
#:* Оформить правильно источники информации
 
#:* Добавить категории
 
#:* Добавить категории
−
# [[Упрощение полигональной цепи]] (''5'')
+
 
−
## Добавить преимущества Дугласа-Пекера
+
== 9. Триангуляция Делоне и диаграмма Вороного ==
−
#:* Чуть-чуть поправить структуру конспекта
+
# [[ Триангуляция Делоне | Триангуляция Делоне ]] (''30'')
−
#:* Задачу в Шаблон
+
## Чуть подробней расписать первую теорему, расписать координаты в векторе, пояснить результат
 +
## Структурней описать алгоритм локализации
 +
## Подробные доказательства всех лем для локализации
 +
## Точнее и подробней про констрейнты рассказать
 +
## Доказать парочку якобы очевидных фактов
 +
#:* Увеличить дроби
 +
#:* Заменить знаки неравенст
 +
#:* Источники информации
 +
#:* Категории
 +
# [[ Диаграмма Вороного | Диаграмма Вороного ]] (''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'')
 
# [[Диаметр множества точек (вращающиеся калиперы)]] (''10'')
 
## Картинку с пояснением определения следующей стороны для вращения при помощи поворота
 
## Картинку с пояснением определения следующей стороны для вращения при помощи поворота
Строка 220: Строка 238:
 
#:* Задачу в шаблон
 
#:* Задачу в шаблон
 
#:* Оформить правильно источники информации
 
#:* Оформить правильно источники информации
−
# [[ Сумма Минковского (определение, вычисление) | Сумма Минковского (определение, вычисление) ]] (''20'')
 
−
## Подробней описание, что это такое и зачем надо
 
−
## Доказать получше экстремальность вершины в заданном направлении как сумму двух вершин в этом направлении
 
−
## Доказать выпуклость суммы минковского двух выпуклых фигур
 
−
#:* Отформатировать псевдокод
 
−
#:* Источники информации, категории
 
 
# [[Минимальная охватывающая окружность множества точек]] (''25'')
 
# [[Минимальная охватывающая окружность множества точек]] (''25'')
 
## Рассказать, почему выпуклая оболочка (или диаметр двух дальних точек не подходят или подходят)
 
## Рассказать, почему выпуклая оболочка (или диаметр двух дальних точек не подходят или подходят)
Строка 237: Строка 249:
 
#:* Оформить правильно источники информации
 
#:* Оформить правильно источники информации
 
#:* Добавить категории
 
#:* Добавить категории
−
# [[ Visibility graph и motion planning | Visibility graph и motion planning ]] (''25'')
+
# [[Пересечение окружностей]] (''10'')
−
## Сказать в лемму про разрешение графа ещё про невыпуклые вершины
+
## Добавить расчёт погрешностей (см. список тем)
−
## Добавить про упрощение путей по навигационным картам
+
## Переходы бы подробней описать
−
## В картинке про заметающий луч, кажется, бага - надо получше объяснить, что на ней нарисовано
+
#:* Увеличить дроби
−
## Ещё пояснить, почему мы рассматриваем только правую полуплоскость (и вообще как сортим вдоль луча, это мб нетривиально в некоторых случаях)
+
#:* Добавить категории
−
## Доказать, что после суммы минковского препятствий будет не очень много углов внутри полигонов
+
# [[Упрощение полигональной цепи]] (''5'')
 +
## Добавить преимущества Дугласа-Пекера
 +
#:* Чуть-чуть поправить структуру конспекта
 +
#:* Задачу в Шаблон
 
#:* Оформить правильно Источники информации
 
#:* Оформить правильно Источники информации
−
#:* Некоторые картинки можно красивей нарисовать
+
#:* Внутренние ссылки сделать примечаниями
 +
#:* Отформатировать псевдокод
 
#:* Заменить знаки неравенств
 
#:* Заменить знаки неравенств
−
#:* Отформатировать псевдокоды
+
# [[ Вычисление площади и объема ]] (''15'')
−
# [[ Триангуляция Делоне | Триангуляция Делоне ]] (''30'')
+
## Написать
−
## Чуть подробней расписать первую теорему, расписать координаты в векторе, пояснить результат
+
# [[ Пересечение выпуклых многоугольников ]] (''15'')
−
## Структурней описать алгоритм локализации
+
## Написать
−
## Подробные доказательства всех лем для локализации
+
 
−
## Точнее и подробней про констрейнты рассказать
+
== 12. Программирование ==
−
## Доказать парочку якобы очевидных фактов
+
# [[Запуск проекта визуализации cg]] (''10'')
−
#:* Увеличить дроби
+
## Небольшой туториал, как начать работу с библиотекой визуализации, что поставить и как запустить
−
#:* Заменить знаки неравенст
+
## Неплохо бы ещё скриншоты добавить (чтобы совсем всем всё было понятно)
−
#:* Источники информации
+
# [[CMake_Tutorial|Туториал по cmake]] (''15'')
−
#:* Категории
+
## Сделать конспект более формальным
−
# [[ Диаграмма Вороного | Диаграмма Вороного ]] (''30'')
+
## Как установить, что вообще надо (ссылки добавить)
−
## Написать адекватный конспект - инкрементальное построение ДВ, ДВ k-ого порядка, начать, конечно, следует с наивного алгоритма пересечения полуплоскостей
+
## Простые и последовательные примеры: сборка простого файла, нескольких файлов, как подключить буст, gmp, gtest
−
## Добавить про связь с триангуляцией делоне
+
## Объяснение происходящего в библиотеке визуализации cg
−
# [[Motorcycle graph]]
+
## Примеры полных скриптов
−
# [[Straight skeleton]]
+
#:* Добавить категории
 +
#:* Добавить ссылок
 +
# [[Тестирование с использованием Google Test]] (''5'')
 +
## Ссылка на код битая, добавить пример кода с github
 +
#:* Задачу в Шаблон
 +
#:* Добавить категории
 +
#:* Интервики
 +
#:* Имя функции в \mathrm

Версия 17:14, 23 февраля 2015

Нумерованные замечания — по содержанию, маркированные — по оформлению

1. Основание вычислительной геометрии

  1. Аффинное пространство
    1. Написать
  2. Ориентация и объем
    1. Написать
  3. Скалярное произведение и метрика
    1. Написать
  4. Однородные координаты
    1. Написать

2. Вычисление геометрических предикатов

  1. Представление чисел с плавающей точкой (5)
    1. Помёрджить с аналогичным конспектом по дискретке
    2. Добавить код получения машинного эпсилон в c++
    • Оформить правильно источники информации
    • Поправить категории
    • Дефисы заменить на тире
    • Заменить знаки неравенств
  2. Предикат "левый поворот" (10)
    1. Перенести расчёт погрешности из конспекта про вещественные числа сюда
    2. Сказать, почему в расчёте не используется деление, и что обычно с этим делают
    3. Статью написать именно про предикат поворота, про его сакральный смысл, а не про пересечение отрезков; можно добавить различных применений
    4. Добавить пример, простое правило для запоминания направления
    • Неплохо бы векторные картинки сделать вместо таких растровых
    • Добавить категории
    • Добавить источники информации
  3. Пересечение отрезков и поворот: определение, свойства, вычисление (15)
    1. Подробное и ясное объяснение шагов с картинками (взять часть информации из предиката поворота), вот здесь детальный разбор этой задачи
    2. Про аффинное пространство будет отдельный конспект (если кто-нибудь напишет), поэтому только небольшую справку в начале надо сделать
    3. Рассказать про нахождение самой точки пересечения двух отрезков, и какие проблемы с этим связаны
    • Переменные и константы в Tex
    • Интервики
    • Оформить правильно источники информации
    • Отформатировать псевдокод, оформить как функцию, принимающих два отрезка, код смотреть в cg
    • Добавить категории
  4. Adaptive precision arithmetic
  5. Интервальная арифметика (10)
    1. Какой-нибудь пример с кодом на c++ (желательно предикат левый поворот) и с объяснением происходящего
    2. И написать, что делать, если в интервальной арифметике посчиталось неточно (добавить просто пример с mpq_class)
    3. Пару мотивационных слов о том, как надо делать вычисления (про скатывание в рациональную), о скорости и т. д.
    • Англоязычные термины
    • В формулы можно добавить пробелы для лучшей читаемости
    • Оформить правильно Источники информации
    • Добавить категории

3. Пересечение отрезков

  1. Алгоритм Бентли-Оттмана
  2. Пересечение множества отрезков (15)
    1. Помёрджить с конспектом про Бентли-Оттмана
    2. Написать понятный конспект с описанием всех шагов и частных случаев
  3. Snap rounding (30)
    1. Написать полноценный конспект про SR по алгоритму на пучках, добавить наивный алгоритм
  4. Пересечение отрезков на сфере (10)
    1. Доделать конспект: описать всё формально, подробно и понятно
    • Задачу в Шаблон
    • Алгоритм красиво оформить
    • Источники информации
    • Категории

4. Выпуклые оболочки

  1. Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull (10)
    1. См. обсуждения
    2. В некоторых местах не очень понятно, почему это правда - пояснить корректность алгоритма
    3. Про Чена очень мало, смотреть википедию русскую
    • Определение жирным
    • Дефисы на тире
    • Все ссылки в конец, оформить правильно Источники информации
    • Добавить в ссылки примеры кодов (из cg, ещё можно где-нибудь нагуглить)
    • Опустить заголовки на 1, сделать конспект более структурированным
    • Отформатировать псевдокоды
  2. Динамическая выпуклая оболочка (log^2 на добавление/удаление) (20)
    1. А что делать, когда у нас есть левая и правая оболочки?
    2. Не написано, как определять эти случаи, и вообще надо по-другому делать
    3. Пояснить подробней про сложные случаи
    • Переименовать конспект без "достаточно"
    • Добавить категории
  3. Выпуклая оболочка в n-мерном пространстве (15)
    1. Убрать плашку вверху
    2. Рассказать про QuickHull и вероятностный алгоритм (а только потом уже про сложный)
    • Добавить категории и источники информации
  4. Пересечение полуплоскостей, связь с выпуклыми оболочками (10)
    1. Написать подробней
    2. Почему соответствует выпуклой оболочке?

5. Поиск

  1. К-d деревья и перечисление точек в произвольном прямоугольнике (статика) (5)
    1. Мы ищем медиану по разным кординатам каждый раз, разве нам достаточно просто как-то посортить точки?
    2. Более подробное доказательство асимптотики времени работы, разбор случаев, сказать, что оценка довольно грубая, на практике чуть быстрей, хотя всё равно медленно
    • Оформить правильно англоязычные термины
    • Оформить правильно источники информации
    • Отформатировать псевдокод
    • Функции в тексте взять в \mathrm
    • Неплохо бы для понимания добавить картинки из гуглящейся презентации
    • Добавить категории
  2. Квадродерево, сжатое квадродерево (10)
    1. А зачем оно надо?
    2. Про перечисление точек в прямоугольнике более формально написать, псевдокод добавить хороший, оценки сказать
    3. Время работы ортогонального поиска в сжатом квадродереве
    • Убрать текст про билеты вверху
    • Англоязычные термины
    • Внутренние ссылки оформить как примечания
    • Картинки наезжают на заголовки
    • Оформить правильно источники информации
    • Добавить категории
  3. Skip quadtree: определение, время работы, запрос точек в прямоугольнике
  4. Ортогональный поиск
    1. Впихнуть в Range tree (берётся вместе со следующим конспектом)
  5. Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) (20)
    1. Написать в одномерном случае сначала, что его можно решать проще, а в двумерном, что можно использовать простой вариант одномерного в узле
    2. Картинки очень нужны, без них слабо понятно
    3. Псевдокоды неплохо бы добавить
    4. Написать подробно Fractional Cascading с картинками (см. список тем)
    • Переименовать конспект в Range tree
    • Заменить знаки неравенств
    • Заменить вертикальную черту на \mid
    • Задачу в Шаблон
    • Все переменные и константы в Tex
    • Оформить правильно источники информации
    • Добавить категории
  6. Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) (5)
    1. Чуть подробней написать про решение задачи, как находим, как упорядочиваем отрезки, добавить картинки опять же
    • Задачу в Шаблон
    • Правильно оформить англ. термины
    • Оформить правильно источники информации
  7. Дерево интервалов (interval tree) и пересечение точки с множеством интервалов (5)
    1. Неплохо бы добавить ссылку на код реализации, довольно простая структура
    2. Можно сказать, как соптимизировать, если нам нужно только количество отрезков
    3. Картинки было бы неплохо добавить
    • Переименовать конспект в Interval tree
    • Определение жирным, англоязычные термины правильно оформить
    • Отформартировать псевдокод, описать структуру дерева подробней
    • Добавить Источники информации
    • Добавить категории
  8. Пересечение прямоугольника с множеством прямоугольников (PST) (5)
    1. Картинки добавить
    • Переименовать конспект в Priority search tree
    • Логичней сначала писать задачу, а потом давать определение структуры
    • Отформартировать псевдокоды
    • Добавить категории
    • Добавить источники информации
  9. BSP-дерево

6. Триангуляция

  1. Триангуляция многоугольника за n^2 (10)
    1. Переименовать конспект в просто триангуляцию и ушную триангуляцию, выпилить в отдельный конспект
    2. А зачем нужно два уха?
    3. Нужно подробней написать, почему работает за O(n^2), сейчас это непонятно из конспекта, кажется, что за куб
    • Интервики на число триангуляций (числа Каталана)
    • Отформатировать псевдокод
    • Добавить источники информации
  2. Триангуляция многоугольника заметающей прямой

7. ППЛГ и РСДС

  1. Конфигурация (10)
    1. Информацию про DCEL, его свойства, простые примеры операций (соединение двух вершин ребром, то есть добавление диагонали)
    2. Оставить только общий конспект про конфигурации и DCEL в частности
    • Таблички сделать красивые
    • Оформить правильно источники информации
    • Добавить категории
  2. ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых (15)
    1. Написать полный разбор задачи Line Arrangement со всякими подробностями типа точного вычисления предикатов
  3. Пересечение многоугольников (PSLG overlaying) (25)
    1. Полностью переписать конспект, здесь лишь непонятный перевод де Берга

8. Алгоритмы локализации

  1. Принадлежность точки выпуклому и невыпуклому многоугольникам (5)
    1. Картинка в случае выпуклого многоугольника
    2. Более подробное объяснение корректности алгоритма в случае невыпуклого полигона
    3. Пару слов про то, работает ли в полигонах с дырками
    • Убрать плашку вверху
    • Оформить правильно источники информации
    • Добавить категории
    • min и max заменить на \min и \max
  2. Локализация в ППЛГ методом полос (персистентные деревья) (5)
    1. Добавить несколько больше информации в введение из лекций Станкевича
    2. Добавить картинок из гуглящейся презенташки
    • Задачу в Шаблон
    • Убрать плашку вверху
    • Интервики на персистентые деревья
    • Добавить категории
  3. Локализация в ППЛГ. Алгоритм Киркпатрика (10)
    1. Добавить другой критерий выбора удаляемых вершин по степени (презенташка гуглится), доказать его корректность, сравнить с существующим
    2. Рассказать про перетриангуляцию (как эффективно и как всё в DCEL вообще происходит)
    • Отформатировать псевдокод
    • Пофиксить категории
    • Увеличить дроби
  4. Трапецоидная карта (20)
    1. Сказать, что в статике можно строить заметающей прямой трапецоидную карту (и сказать, как строить)
    2. Про мнимую оболочку сказать получше - окружаем прямоугольником отрезки
    3. Чуть переформулировать постановку (всё же решаем задачу локализации, а не поиска пути, но про него можно отдельно сказать)
    4. Сказать в начале, какие частные случаи не рассматриваем
    5. Более подробные псевдокоды, ну и вообще конспект сделать более структурированным
    6. Добавить худший случай для построения
    7. Доказательства асимптотик можно сделать попроще, используя регрессионный анализ
    • Задачу в Шаблон
    • Оформить правильно источники информации
    • Добавить категории

9. Триангуляция Делоне и диаграмма Вороного

  1. Триангуляция Делоне (30)
    1. Чуть подробней расписать первую теорему, расписать координаты в векторе, пояснить результат
    2. Структурней описать алгоритм локализации
    3. Подробные доказательства всех лем для локализации
    4. Точнее и подробней про констрейнты рассказать
    5. Доказать парочку якобы очевидных фактов
    • Увеличить дроби
    • Заменить знаки неравенст
    • Источники информации
    • Категории
  2. Диаграмма Вороного (30)
    1. Написать адекватный конспект - инкрементальное построение ДВ, ДВ k-ого порядка, начать, конечно, следует с наивного алгоритма пересечения полуплоскостей
    2. Добавить про связь с триангуляцией делоне
  3. Motorcycle graph
  4. Straight skeleton

10. Планирование движения (Motion planning)

  1. Сумма Минковского (определение, вычисление) (20)
    1. Подробней описание, что это такое и зачем надо
    2. Доказать получше экстремальность вершины в заданном направлении как сумму двух вершин в этом направлении
    3. Доказать выпуклость суммы минковского двух выпуклых фигур
    • Отформатировать псевдокод
    • Источники информации, категории
  2. Visibility graph и motion planning (25)
    1. Сказать в лемму про разрешение графа ещё про невыпуклые вершины
    2. Добавить про упрощение путей по навигационным картам
    3. В картинке про заметающий луч, кажется, бага - надо получше объяснить, что на ней нарисовано
    4. Ещё пояснить, почему мы рассматриваем только правую полуплоскость (и вообще как сортим вдоль луча, это мб нетривиально в некоторых случаях)
    5. Доказать, что после суммы минковского препятствий будет не очень много углов внутри полигонов
    • Оформить правильно Источники информации
    • Некоторые картинки можно красивей нарисовать
    • Заменить знаки неравенств
    • Отформатировать псевдокоды

11. Задачи

  1. Диаметр множества точек (вращающиеся калиперы) (10)
    1. Картинку с пояснением определения следующей стороны для вращения при помощи поворота
    2. Сказать, что поиск минимальной охватывающей окружности тут не прокатывает (с контрпримером)
    • Задачу в шаблон
    • Оформить правильно источники информации
  2. Минимальная охватывающая окружность множества точек (25)
    1. Рассказать, почему выпуклая оболочка (или диаметр двух дальних точек не подходят или подходят)
    2. Добавить реализацию через одну функцию
    3. Нормальное и понятное доказательство корректности с картинками
    4. Добавить оптимизации по скорости
    5. А зачем оно вообще надо?
    • Убрать плашку вверху
    • Заменить знаки неравенств
    • Отформатировать псевдокоды
    • Оформить правильно источники информации
    • Добавить категории
  3. Пересечение окружностей (10)
    1. Добавить расчёт погрешностей (см. список тем)
    2. Переходы бы подробней описать
    • Увеличить дроби
    • Добавить категории
  4. Упрощение полигональной цепи (5)
    1. Добавить преимущества Дугласа-Пекера
    • Чуть-чуть поправить структуру конспекта
    • Задачу в Шаблон
    • Оформить правильно Источники информации
    • Внутренние ссылки сделать примечаниями
    • Отформатировать псевдокод
    • Заменить знаки неравенств
  5. Вычисление площади и объема (15)
    1. Написать
  6. Пересечение выпуклых многоугольников (15)
    1. Написать

12. Программирование

  1. Запуск проекта визуализации cg (10)
    1. Небольшой туториал, как начать работу с библиотекой визуализации, что поставить и как запустить
    2. Неплохо бы ещё скриншоты добавить (чтобы совсем всем всё было понятно)
  2. Туториал по cmake (15)
    1. Сделать конспект более формальным
    2. Как установить, что вообще надо (ссылки добавить)
    3. Простые и последовательные примеры: сборка простого файла, нескольких файлов, как подключить буст, gmp, gtest
    4. Объяснение происходящего в библиотеке визуализации cg
    5. Примеры полных скриптов
    • Добавить категории
    • Добавить ссылок
  3. Тестирование с использованием Google Test (5)
    1. Ссылка на код битая, добавить пример кода с github
    • Задачу в Шаблон
    • Добавить категории
    • Интервики
    • Имя функции в \mathrm
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Shersh/Тикеты_к_вычислительной_геометрии_(термы_4_и_5)&oldid=44918»