Вычислительная геометрия — различия между версиями
Gromak (обсуждение | вклад) |
Igorjan94 (обсуждение | вклад) |
||
| Строка 26: | Строка 26: | ||
* [[Тестирование с использованием Google Test]] | * [[Тестирование с использованием Google Test]] | ||
== Базовые алгоритмы и структуры данных == | == Базовые алгоритмы и структуры данных == | ||
| − | * [[Skip quadtree]] | + | * [[ Skip quadtree: определение, время работы | Skip quadtree: определение, время работы ]] |
| − | * [[Квадродеревья и перечисление точек в произвольном прямоугольнике]] | + | * [[ Квадродеревья и перечисление точек в произвольном прямоугольнике (статика) | Квадродеревья и перечисление точек в произвольном прямоугольнике (статика) ]] |
| − | == | + | * [[ Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) | Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) ]] |
| − | + | * [[ Дерево интервалов (interval tree) и пересечение точки с множеством интервалов | Дерево интервалов (interval tree) и пересечение точки с множеством интервалов ]] | |
| + | * [[ Пересечение прямоугольника с множеством прямоугольников (PST) | Пересечение прямоугольника с множеством прямоугольников (PST) ]] | ||
| + | == Аффинное пространство == | ||
| + | * [[ Пересечение отрезков и поворот: определение, свойства, вычисление | Пересечение отрезков и поворот: определение, свойства, вычисление ]] | ||
| + | * [[ Принадлежность точки выпуклому и невыпуклому многоугольникам | Принадлежность точки выпуклому и невыпуклому многоугольникам ]] | ||
| + | * [[ Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) | Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) ]] | ||
| + | * [[ Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull | Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull ]] | ||
| + | * [[ Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) ]] | ||
| + | * [[ Выпуклая оболочка в n-мерном пространстве | Выпуклая оболочка в n-мерном пространстве ]] | ||
| + | * [[ Триангуляция многоугольника за n^2 | Триангуляция многоугольника за n^2 ]] | ||
| + | * [[ Триангуляция многоугольника заметающей прямой | Триангуляция многоугольника заметающей прямой ]] | ||
| + | * [[ Пересечение полуплоскостей, связь с выпуклыми оболочками | Пересечение полуплоскостей, связь с выпуклыми оболочками ]] | ||
| + | * [[ Пересечение множества отрезков | Пересечение множества отрезков ]] | ||
| + | * [[ Snap rounding | Snap rounding ]] | ||
| + | * [[ ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых | ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых ]] | ||
| + | * [[ Пересечение многоугольников (PSLG overlaying) | Пересечение многоугольников (PSLG overlaying) ]] | ||
| + | * [[ Локализация в ППЛГ методом полос (персистентные деревья) | Локализация в ППЛГ методом полос (персистентные деревья) ]] | ||
| + | * [[ Локализация в ППЛГ. Алгоритм Киркпатрика | Локализация в ППЛГ. Алгоритм Киркпатрика ]] | ||
| + | * [[ Трапецоидная карта | Трапецоидная карта ]] | ||
== Скалярное произведение и мера == | == Скалярное произведение и мера == | ||
| − | [[Диаметр множества точек (вращающиеся калиперы)]] | + | * [[ Диаметр множества точек (вращающиеся калиперы) | Диаметр множества точек (вращающиеся калиперы) ]] |
| + | * [[ Сумма Минковского (определение, вычисление) | Сумма Минковского (определение, вычисление) ]] | ||
| + | * [[ Минимальная охватывающая окружность множества точек | Минимальная охватывающая окружность множества точек ]] | ||
| + | * [[ Visibility graph и motion planning | Visibility graph и motion planning ]] | ||
| + | * [[ Триангуляция Делоне | Триангуляция Делоне ]] | ||
| + | * [[ Диаграмма Вороного | Диаграмма Вороного ]] | ||
| + | * [[ straight skeleton | straight skeleton ]] | ||
| + | * [[ WRP + continuous Dijkstra (специально для Сени и Юрика :) | WRP + continuous Dijkstra (специально для Сени и Юрика :) ]] | ||
Версия 19:24, 4 января 2014
- Представление чисел с плавающей точкой
- Предикат "левый поворот"
- Интервальная арифметика
- Adaptive precision arithmetic
- Алгоритм Бентли-Оттмана
- Конфигурация
- Трапецоидная карта
- Алгоритм Киркпатрика детализации триангуляции
- Пересечение окружностей
- Упрощение полигональной цепи
- Ортогональный поиск
- Алгоритмы построения выпуклых оболочек множества точек на плоскости
- Триангуляция полигонов (ушная + монотонная)
Базовые алгоритмы и структуры данных
- Skip quadtree: определение, время работы
- Квадродеревья и перечисление точек в произвольном прямоугольнике (статика)
- Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree)
- Дерево интервалов (interval tree) и пересечение точки с множеством интервалов
- Пересечение прямоугольника с множеством прямоугольников (PST)
Аффинное пространство
- Пересечение отрезков и поворот: определение, свойства, вычисление
- Принадлежность точки выпуклому и невыпуклому многоугольникам
- Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)
- Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull
- Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление)
- Выпуклая оболочка в n-мерном пространстве
- Триангуляция многоугольника за n^2
- Триангуляция многоугольника заметающей прямой
- Пересечение полуплоскостей, связь с выпуклыми оболочками
- Пересечение множества отрезков
- Snap rounding
- ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых
- Пересечение многоугольников (PSLG overlaying)
- Локализация в ППЛГ методом полос (персистентные деревья)
- Локализация в ППЛГ. Алгоритм Киркпатрика
- Трапецоидная карта
