Вычислительная геометрия — различия между версиями
(→Базовые алгоритмы и структуры данных) |
м (rollbackEdits.php mass rollback) |
||
| (не показано 16 промежуточных версий 6 участников) | |||
| Строка 1: | Строка 1: | ||
| − | + | == Основание вычислительной геометрии == | |
| − | + | * [[ Аффинное пространство ]] | |
| − | + | * [[ Объем ]] | |
| − | + | * [[ Скалярное произведение и метрика ]] | |
| − | + | * [[ Однородные координаты ]] | |
| − | + | * [[ Двойственное пространство ]] | |
| − | |||
| − | * [[ | ||
| − | * [[ | ||
| − | * [[ | ||
| − | * [[ | ||
| − | * [[ | ||
| − | + | == Вычисление геометрических предикатов == | |
| + | * [[ Представление чисел с плавающей точкой ]] | ||
| + | * [[ Предикат "левый поворот" ]] | ||
| + | * [[ Пересечение отрезков и поворот: определение, свойства, вычисление ]] | ||
| + | * [[ Adaptive precision arithmetic ]] | ||
| + | * [[ Интервальная арифметика ]] | ||
| − | * [[ | + | == Пересечение отрезков == |
| − | * [[ | + | * [[ Алгоритм Бентли-Оттмана ]] |
| − | * [[ | + | * [[ Пересечение множества отрезков ]] |
| − | * [[ | + | * [[ Алгоритм Балабана ]] |
| − | * [[ | + | * [[ Snap rounding ]] |
| + | * [[ Пересечение отрезков на сфере ]] | ||
| − | - | + | == Выпуклые оболочки == |
| + | * [[ Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull ]] | ||
| + | * [[ Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка ]] | ||
| + | * [[ Выпуклая оболочка в n-мерном пространстве ]] | ||
| + | * [[ Пересечение полуплоскостей, связь с выпуклыми оболочками ]] | ||
| − | + | == Поиск == | |
| − | * [[ | + | * [[ К-d деревья и перечисление точек в произвольном прямоугольнике (статика) ]] |
| − | + | * [[ Квадродеревья | Квадродерево, сжатое квадродерево ]] | |
| − | * [[Квадродеревья | Квадродерево, сжатое квадродерево]] | ||
* [[ Skip quadtree: определение, время работы | Skip quadtree: определение, время работы, запрос точек в прямоугольнике ]] | * [[ Skip quadtree: определение, время работы | Skip quadtree: определение, время работы, запрос точек в прямоугольнике ]] | ||
| − | * [[ | + | * [[ Ортогональный поиск ]] |
| − | * [[ Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) | + | * [[ Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) ]] |
| − | * [[ | + | * [[ Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) ]] |
| + | * [[ Дерево интервалов (interval tree) и пересечение точки с множеством интервалов ]] | ||
* [[ Пересечение прямоугольника с множеством прямоугольников (PST) | Пересечение прямоугольника с множеством прямоугольников (priority search tree) ]] | * [[ Пересечение прямоугольника с множеством прямоугольников (PST) | Пересечение прямоугольника с множеством прямоугольников (priority search tree) ]] | ||
| + | * [[ BSP-дерево ]] | ||
| − | == | + | == Триангуляция == |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
* [[ Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]] | * [[ Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]] | ||
* [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой ]] | * [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой ]] | ||
| − | + | ||
| − | + | == ППЛГ и РСДС == | |
| − | * [[ | + | * [[ Конфигурация ]] |
| − | * [[ | + | * [[ ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых ]] |
| − | * [[ Пересечение многоугольников (PSLG overlaying) | + | * [[ Пересечение многоугольников (PSLG overlaying) ]] |
| − | * [[ | + | |
| + | == Алгоритмы локализации == | ||
| + | * [[ Принадлежность точки выпуклому и невыпуклому многоугольникам ]] | ||
| + | * [[ Локализация в ППЛГ методом полос (персистентные деревья) ]] | ||
* [[ Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ. Алгоритм Киркпатрика ]] | * [[ Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ. Алгоритм Киркпатрика ]] | ||
| − | * [[ | + | * [[ Трапецоидная карта ]] |
| − | * [[ | + | |
| − | * [[ | + | == Триангуляция Делоне и диаграмма Вороного == |
| + | * [[ Триангуляция Делоне ]] | ||
| + | * [[ Триангуляция Делоне на сфере ]] | ||
| + | * [[ Диаграмма Вороного ]] | ||
| + | * [[ Motorcycle graph ]] | ||
| + | * [[ Straight skeleton ]] | ||
| + | |||
| + | == Планирование движения (Motion planning) == | ||
| + | * [[ Сумма Минковского (определение, вычисление) ]] | ||
| + | * [[ Visibility graph и motion planning ]] | ||
| − | == | + | == Задачи == |
| − | * [[ Диаметр множества точек (вращающиеся калиперы | + | * [[ Диаметр множества точек (вращающиеся калиперы) ]] |
| − | + | * [[ Минимальная охватывающая окружность множества точек ]] | |
| − | * [[ Минимальная охватывающая окружность множества точек | + | * [[ Пересечение окружностей ]] |
| − | + | * [[ Упрощение полигональной цепи ]] | |
| − | * [[ | + | * [[ Вычисление площади и объема ]] |
| − | * [[ | + | * [[ Пересечение выпуклых многоугольников ]] |
| − | * [[ | ||
| − | * [[ | ||
| − | == | + | == Программирование == |
| − | * [[ | + | * [[ CMake_Tutorial|Туториал по cmake ]] |
| + | * [[ Тестирование с использованием Google Test ]] | ||
| + | |||
| + | == Организационные вопросы == | ||
| + | * [[Участник:Shersh/Тикеты к вычислительной геометрии (термы 4 и 5) | Правки к конспектам (year 2013)]] | ||
| + | * [https://docs.google.com/spreadsheet/ccc?key=0AiudLnRYFaaXdFJZdXBaSHJQT29wd0EwekxSZ0JTZkE&usp=drive_web#gid=4 Список новых тем и дополнений] | ||
| + | |||
| + | ---- | ||
| + | |||
| + | * [[Список тем | Список тем (year 2010)]] | ||
| + | * [[Список тем (year 2012)]] | ||
| + | * [[Обсуждение:Вычислительная геометрия#Сдача конспектов | Сдача конспектов]] | ||
| + | * [[Обсуждение:Вычислительная геометрия#Презентации | Сдача презентаций]] | ||
| + | * [[Обсуждение:Вычислительная геометрия#Условия и чекеры | Условия и чекеры]] | ||
[[Категория: Вычислительная геометрия]] | [[Категория: Вычислительная геометрия]] | ||
Текущая версия на 19:23, 4 сентября 2022
Содержание
- 1 Основание вычислительной геометрии
- 2 Вычисление геометрических предикатов
- 3 Пересечение отрезков
- 4 Выпуклые оболочки
- 5 Поиск
- 6 Триангуляция
- 7 ППЛГ и РСДС
- 8 Алгоритмы локализации
- 9 Триангуляция Делоне и диаграмма Вороного
- 10 Планирование движения (Motion planning)
- 11 Задачи
- 12 Программирование
- 13 Организационные вопросы
Основание вычислительной геометрии
- Аффинное пространство
- Объем
- Скалярное произведение и метрика
- Однородные координаты
- Двойственное пространство
Вычисление геометрических предикатов
- Представление чисел с плавающей точкой
- Предикат "левый поворот"
- Пересечение отрезков и поворот: определение, свойства, вычисление
- Adaptive precision arithmetic
- Интервальная арифметика
Пересечение отрезков
- Алгоритм Бентли-Оттмана
- Пересечение множества отрезков
- Алгоритм Балабана
- Snap rounding
- Пересечение отрезков на сфере
Выпуклые оболочки
- Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull
- Динамическая выпуклая оболочка
- Выпуклая оболочка в n-мерном пространстве
- Пересечение полуплоскостей, связь с выпуклыми оболочками
Поиск
- К-d деревья и перечисление точек в произвольном прямоугольнике (статика)
- Квадродерево, сжатое квадродерево
- Skip quadtree: определение, время работы, запрос точек в прямоугольнике
- Ортогональный поиск
- Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree)
- Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)
- Дерево интервалов (interval tree) и пересечение точки с множеством интервалов
- Пересечение прямоугольника с множеством прямоугольников (priority search tree)
- BSP-дерево
Триангуляция
ППЛГ и РСДС
- Конфигурация
- ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых
- Пересечение многоугольников (PSLG overlaying)
Алгоритмы локализации
- Принадлежность точки выпуклому и невыпуклому многоугольникам
- Локализация в ППЛГ методом полос (персистентные деревья)
- Локализация в ППЛГ. Алгоритм Киркпатрика
- Трапецоидная карта
Триангуляция Делоне и диаграмма Вороного
- Триангуляция Делоне
- Триангуляция Делоне на сфере
- Диаграмма Вороного
- Motorcycle graph
- Straight skeleton
Планирование движения (Motion planning)
Задачи
- Диаметр множества точек (вращающиеся калиперы)
- Минимальная охватывающая окружность множества точек
- Пересечение окружностей
- Упрощение полигональной цепи
- Вычисление площади и объема
- Пересечение выпуклых многоугольников
