Участник:Shersh/Тикеты к вычислительной геометрии (термы 4 и 5) — различия между версиями
Shersh (обсуждение | вклад) |
Shersh (обсуждение | вклад) |
||
Строка 2: | Строка 2: | ||
== Модель вычислений == | == Модель вычислений == | ||
=== Арифметика === | === Арифметика === | ||
− | # [[Представление чисел с плавающей точкой]] | + | # [[Представление чисел с плавающей точкой]] (''5'') |
− | # | + | ## Помёрджить с аналогичным конспектом по дискретке |
− | # [[Интервальная арифметика]] | + | ## Добавить код получения машинного эпсилон в c++ |
+ | #:* Оформить правильно источники информации | ||
+ | #:* Поправить категории | ||
+ | #:* Дефисы заменить на тире | ||
+ | #:* Заменить знаки неравенств | ||
+ | # [[Интервальная арифметика]] (''10'') | ||
+ | ## Какой-нибудь пример с кодом на c++ (желательно предикат левый поворот) и с объяснением происходящего | ||
+ | ## И написать, что делать, если в интервальной арифметике посчиталось неточно (добавить просто пример с mpq_class) | ||
+ | ## Пару мотивационных слов о том, как надо делать вычисления (про скатывание в рациональную), о скорости и т. д. | ||
+ | #:* Англоязычные термины | ||
+ | #:* В формулы можно добавить пробелы для лучшей читаемости | ||
+ | #:* Оформить правильно Источники информации | ||
+ | #:* Добавить категории | ||
# [[Adaptive precision arithmetic]] | # [[Adaptive precision arithmetic]] | ||
=== Технические подробности === | === Технические подробности === | ||
Строка 10: | Строка 22: | ||
## Небольшой туториал, как начать работу с библиотекой визуализации, что поставить и как запустить | ## Небольшой туториал, как начать работу с библиотекой визуализации, что поставить и как запустить | ||
## Неплохо бы ещё скриншоты добавить (чтобы совсем всем всё было понятно) | ## Неплохо бы ещё скриншоты добавить (чтобы совсем всем всё было понятно) | ||
− | # [[CMake_Tutorial|Туториал по cmake]] ('' | + | # [[CMake_Tutorial|Туториал по cmake]] (''15'') |
## Сделать конспект более формальным | ## Сделать конспект более формальным | ||
## Как установить, что вообще надо (ссылки добавить) | ## Как установить, что вообще надо (ссылки добавить) | ||
Строка 24: | Строка 36: | ||
#:* Имя функции в \mathrm | #:* Имя функции в \mathrm | ||
== Базовые алгоритмы и структуры данных == | == Базовые алгоритмы и структуры данных == | ||
+ | # [[Квадродеревья | Квадродерево, сжатое квадродерево]] | ||
+ | # [[ Skip quadtree: определение, время работы | Skip quadtree: определение, время работы, запрос точек в прямоугольнике ]] | ||
+ | # [[ К-d деревья и перечисление точек в произвольном прямоугольнике (статика) | К-d деревья и перечисление точек в произвольном прямоугольнике (статика) ]] | ||
+ | # [[ Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) | Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) ]] | ||
+ | # [[ Дерево интервалов (interval tree) и пересечение точки с множеством интервалов | Дерево интервалов (interval tree) и пересечение точки с множеством интервалов ]] | ||
+ | # [[ Пересечение прямоугольника с множеством прямоугольников (PST) | Пересечение прямоугольника с множеством прямоугольников (priority search tree) ]] | ||
+ | # [[ Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) | Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) ]] | ||
== Аффинное пространство == | == Аффинное пространство == | ||
− | + | === Простые геометрические операции и алгоритмы === | |
− | + | # [[Предикат "левый поворот"]] (''10'') | |
− | + | ## Перенести расчёт погрешности из конспекта про вещественные числа сюда | |
− | + | ## Сказать, почему в расчёте не используется деление, и что обычно с этим делают | |
− | * | + | ## Статью написать именно про предикат поворота, про его сакральный смысл, а не про пересечение отрезков; можно добавить различных применений |
− | * | + | ## Добавить пример, простое правило для запоминания направления |
− | * | + | #:* Неплохо бы векторные картинки сделать вместо таких растровых |
− | # [[ Пересечение отрезков и поворот: определение, свойства, вычисление | + | #:* Добавить категории |
− | # [[ | + | #:* Добавить источники информации |
− | # [[ | + | # [[Пересечение отрезков и поворот: определение, свойства, вычисление]] |
− | + | # [[Пересечение отрезков на сфере]] | |
− | # [[ Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка ( | + | # [[Пересечение окружностей]] |
− | # [[ Выпуклая оболочка в n-мерном пространстве | + | # [[Принадлежность точки выпуклому и невыпуклому многоугольникам]] |
+ | # [[ Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull]] | ||
+ | === Продвинутые алгоритмы === | ||
+ | # [[Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка (log^2 на добавление/удаление)]] | ||
+ | # [[Выпуклая оболочка в n-мерном пространстве]] | ||
+ | # [[Алгоритм Бентли-Оттмана]] | ||
+ | # [[Алгоритм Балабана]] | ||
+ | # [[Трапецоидная карта]] | ||
+ | # [[Алгоритм Киркпатрика детализации триангуляции]] | ||
+ | # [[Упрощение полигональной цепи]] | ||
+ | # [[Ортогональный поиск]] | ||
+ | # [[Триангуляция полигонов (ушная + монотонная)]] | ||
# [[ Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]] | # [[ Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]] | ||
# [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой ]] | # [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой ]] | ||
Строка 49: | Строка 79: | ||
# [[ Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ. Алгоритм Киркпатрика ]] | # [[ Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ. Алгоритм Киркпатрика ]] | ||
# [[ Трапецоидная карта | Трапецоидная карта ]] | # [[ Трапецоидная карта | Трапецоидная карта ]] | ||
− | + | ||
# [[BSP-дерево]] | # [[BSP-дерево]] | ||
== Скалярное произведение и мера (проверяется) == | == Скалярное произведение и мера (проверяется) == |
Версия 18:09, 18 февраля 2015
Нумерованные замечания — по содержанию, маркированные — по оформлению
Содержание
Модель вычислений
Арифметика
- Представление чисел с плавающей точкой (5)
- Помёрджить с аналогичным конспектом по дискретке
- Добавить код получения машинного эпсилон в c++
- Оформить правильно источники информации
- Поправить категории
- Дефисы заменить на тире
- Заменить знаки неравенств
- Интервальная арифметика (10)
- Какой-нибудь пример с кодом на c++ (желательно предикат левый поворот) и с объяснением происходящего
- И написать, что делать, если в интервальной арифметике посчиталось неточно (добавить просто пример с mpq_class)
- Пару мотивационных слов о том, как надо делать вычисления (про скатывание в рациональную), о скорости и т. д.
- Англоязычные термины
- В формулы можно добавить пробелы для лучшей читаемости
- Оформить правильно Источники информации
- Добавить категории
- Adaptive precision arithmetic
Технические подробности
- Запуск проекта визуализации cg (10)
- Небольшой туториал, как начать работу с библиотекой визуализации, что поставить и как запустить
- Неплохо бы ещё скриншоты добавить (чтобы совсем всем всё было понятно)
- Туториал по cmake (15)
- Сделать конспект более формальным
- Как установить, что вообще надо (ссылки добавить)
- Простые и последовательные примеры: сборка простого файла, нескольких файлов, как подключить буст, gmp, gtest
- Объяснение происходящего в библиотеке визуализации cg
- Примеры полных скриптов
- Добавить категории
- Тестирование с использованием Google Test (5)
- Ссылка на код битая, добавить пример кода с github
- Задачу в Шаблон
- Добавить категории
- Интервики
- Имя функции в \mathrm
Базовые алгоритмы и структуры данных
- Квадродерево, сжатое квадродерево
- Skip quadtree: определение, время работы, запрос точек в прямоугольнике
- К-d деревья и перечисление точек в произвольном прямоугольнике (статика)
- Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree)
- Дерево интервалов (interval tree) и пересечение точки с множеством интервалов
- Пересечение прямоугольника с множеством прямоугольников (priority search tree)
- Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)
Аффинное пространство
Простые геометрические операции и алгоритмы
- Предикат "левый поворот" (10)
- Перенести расчёт погрешности из конспекта про вещественные числа сюда
- Сказать, почему в расчёте не используется деление, и что обычно с этим делают
- Статью написать именно про предикат поворота, про его сакральный смысл, а не про пересечение отрезков; можно добавить различных применений
- Добавить пример, простое правило для запоминания направления
- Неплохо бы векторные картинки сделать вместо таких растровых
- Добавить категории
- Добавить источники информации
- Пересечение отрезков и поворот: определение, свойства, вычисление
- Пересечение отрезков на сфере
- Пересечение окружностей
- Принадлежность точки выпуклому и невыпуклому многоугольникам
- Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull
Продвинутые алгоритмы
- Динамическая выпуклая оболочка (log^2 на добавление/удаление)
- Выпуклая оболочка в n-мерном пространстве
- Алгоритм Бентли-Оттмана
- Алгоритм Балабана
- Трапецоидная карта
- Алгоритм Киркпатрика детализации триангуляции
- Упрощение полигональной цепи
- Ортогональный поиск
- Триангуляция полигонов (ушная + монотонная)
- Триангуляция многоугольника за n^2
- Триангуляция многоугольника заметающей прямой
- Пересечение полуплоскостей, связь с выпуклыми оболочками
- Пересечение множества отрезков
- Snap rounding
- Конфигурация
- ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых
- Пересечение многоугольников (PSLG overlaying)
- Локализация в ППЛГ методом полос (персистентные деревья)
- Локализация в ППЛГ. Алгоритм Киркпатрика
- Трапецоидная карта