Участник:Shersh/Тикеты к вычислительной геометрии (термы 4 и 5)
< Участник:Shersh
Версия от 20:16, 18 февраля 2015; Shersh (обсуждение | вклад)
Нумерованные замечания — по содержанию, маркированные — по оформлению
Содержание
Модель вычислений
Арифметика
- Представление чисел с плавающей точкой (5)
- Помёрджить с аналогичным конспектом по дискретке
- Добавить код получения машинного эпсилон в c++
- Оформить правильно источники информации
- Поправить категории
- Дефисы заменить на тире
- Заменить знаки неравенств
- Интервальная арифметика (10)
- Какой-нибудь пример с кодом на c++ (желательно предикат левый поворот) и с объяснением происходящего
- И написать, что делать, если в интервальной арифметике посчиталось неточно (добавить просто пример с mpq_class)
- Пару мотивационных слов о том, как надо делать вычисления (про скатывание в рациональную), о скорости и т. д.
- Англоязычные термины
- В формулы можно добавить пробелы для лучшей читаемости
- Оформить правильно Источники информации
- Добавить категории
- Adaptive precision arithmetic
Технические подробности
- Запуск проекта визуализации cg (10)
- Небольшой туториал, как начать работу с библиотекой визуализации, что поставить и как запустить
- Неплохо бы ещё скриншоты добавить (чтобы совсем всем всё было понятно)
- Туториал по cmake (15)
- Сделать конспект более формальным
- Как установить, что вообще надо (ссылки добавить)
- Простые и последовательные примеры: сборка простого файла, нескольких файлов, как подключить буст, gmp, gtest
- Объяснение происходящего в библиотеке визуализации cg
- Примеры полных скриптов
- Добавить категории
- Добавить ссылок
- Тестирование с использованием Google Test (5)
- Ссылка на код битая, добавить пример кода с github
- Задачу в Шаблон
- Добавить категории
- Интервики
- Имя функции в \mathrm
Базовые алгоритмы и структуры данных
- Квадродерево, сжатое квадродерево (10)
- А зачем оно надо?
- Про перечисление точек в прямоугольнике более формально написать, псевдокод добавить хороший, оценки сказать
- Время работы ортогонального поиска в сжатом квадродереве
- Убрать текст про билеты вверху
- Англоязычные термины
- Внутренние ссылки оформить как примечания
- Картинки наезжают на заголовки
- Оформить правильно источники информации
- Добавить категории
- Skip quadtree: определение, время работы, запрос точек в прямоугольнике
- К-d деревья и перечисление точек в произвольном прямоугольнике (статика) (5)
- Мы ищем медиану по разным кординатам каждый раз, разве нам достаточно просто как-то посортить точки?
- Более подробное доказательство асимптотики времени работы, разбор случаев, сказать, что оценка довольно грубая, на практике чуть быстрей, хотя всё равно медленно
- Оформить правильно англоязычные термины
- Оформить правильно источники информации
- Отформатировать псевдокод
- Функции в тексте взять в \mathrm
- Неплохо бы для понимания добавить картинки из гуглящейся презентации
- Добавить категории
- Ортогональный поиск
- Впихнуть в Range tree (берётся вместе со следующим конспектом)
- Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) (20)
- Написать в одномерном случае сначала, что его можно решать проще, а в двумерном, что можно использовать простой вариант одномерного в узле
- Картинки очень нужны, без них слабо понятно
- Псевдокоды неплохо бы добавить
- Написать подробно Fractional Cascading с картинками (см. список тем)
- Переименовать конспект в Range tree
- Заменить знаки неравенств
- Заменить вертикальную черту на \mid
- Задачу в Шаблон
- Все переменные и константы в Tex
- Оформить правильно источники информации
- Добавить категории
- Дерево интервалов (interval tree) и пересечение точки с множеством интервалов (5)
- Неплохо бы добавить ссылку на код реализации, довольно простая структура
- Можно сказать, как соптимизировать, если нам нужно только количество отрезков
- Картинки было бы неплохо добавить
- Переименовать конспект в Interval tree
- Определение жирным, англоязычные термины правильно оформить
- Отформартировать псевдокод, описать структуру дерева подробней
- Добавить Источники информации
- Добавить категории
- Пересечение прямоугольника с множеством прямоугольников (PST) (5)
- Картинки добавить
- Переименовать конспект в Priority search tree
- Логичней сначала писать задачу, а потом давать определение структуры
- Отформартировать псевдокоды
- Добавить категории
- Добавить источники информации
- Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) (5)
- Чуть подробней написать про решение задачи, как находим, как упорядочиваем отрезки, добавить картинки опять же
- Задачу в Шаблон
- Правильно оформить англ. термины
- Оформить правильно источники информации
Аффинное пространство
Простые геометрические операции и алгоритмы
- Предикат "левый поворот" (10)
- Перенести расчёт погрешности из конспекта про вещественные числа сюда
- Сказать, почему в расчёте не используется деление, и что обычно с этим делают
- Статью написать именно про предикат поворота, про его сакральный смысл, а не про пересечение отрезков; можно добавить различных применений
- Добавить пример, простое правило для запоминания направления
- Неплохо бы векторные картинки сделать вместо таких растровых
- Добавить категории
- Добавить источники информации
- Пересечение отрезков и поворот: определение, свойства, вычисление (15)
- Подробное и ясное объяснение шагов с картинками (взять часть информации из предиката поворота), вот здесь детальный разбор этой задачи
- Про аффинное пространство будет отдельный конспект (если кто-нибудь напишет), поэтому только небольшую справку в начале надо сделать
- Рассказать про нахождение самой точки пересечения двух отрезков, и какие проблемы с этим связаны
- Переменные и константы в Tex
- Интервики
- Оформить правильно источники информации
- Отформатировать псевдокод, оформить как функцию, принимающих два отрезка, код смотреть в cg
- Добавить категории
- Пересечение отрезков на сфере (10)
- Доделать конспект: описать всё формально, подробно и понятно
- Задачу в Шаблон
- Алгоритм красиво оформить
- Источники информации
- Категории
- Пересечение окружностей (10)
- Добавить расчёт погрешностей (см. список тем)
- Переходы бы подробней описать
- Увеличить дроби
- Добавить категории
- Принадлежность точки выпуклому и невыпуклому многоугольникам (5)
- Картинка в случае выпуклого многоугольника
- Более подробное объяснение корректности алгоритма в случае невыпуклого полигона
- Пару слов про то, работает ли в полигонах с дырками
- Убрать плашку вверху
- Оформить правильно источники информации
- Добавить категории
- min и max заменить на \min и \max
- Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull (10)
- См. обсуждения
- В некоторых местах не очень понятно, почему это правда - пояснить корректность алгоритма
- Про Чена очень мало, смотреть википедию русскую
- Определение жирным
- Дефисы на тире
- Все ссылки в конец, оформить правильно Источники информации
- Добавить в ссылки примеры кодов (из cg, ещё можно где-нибудь нагуглить)
- Опустить заголовки на 1, сделать конспект более структурированным
- Отформатировать псевдокоды
Продвинутые алгоритмы
- Динамическая выпуклая оболочка (log^2 на добавление/удаление)
- Выпуклая оболочка в n-мерном пространстве
- Триангуляция многоугольника за n^2
- Триангуляция многоугольника заметающей прямой
- Пересечение полуплоскостей, связь с выпуклыми оболочками
- Алгоритм Бентли-Оттмана
- Пересечение множества отрезков (15)
- Помёрджить с конспектом про Бентли-Оттмана
- Написать понятный конспект с описанием всех шагов и частных случаев
- Алгоритм Балабана
- Конфигурация
- ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых
- Пересечение многоугольников (PSLG overlaying)
- Локализация в ППЛГ методом полос (персистентные деревья)
- Локализация в ППЛГ. Алгоритм Киркпатрика
- Трапецоидная карта
- Упрощение полигональной цепи
- Snap rounding
- BSP-дерево
