Вычислительная геометрия — различия между версиями
Tiss93 (обсуждение | вклад) (→Скалярное произведение и мера) |
Gromak (обсуждение | вклад) м |
||
| Строка 38: | Строка 38: | ||
* [[ Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) ]] | * [[ Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) ]] | ||
* [[ Выпуклая оболочка в n-мерном пространстве | Выпуклая оболочка в n-мерном пространстве ]] | * [[ Выпуклая оболочка в n-мерном пространстве | Выпуклая оболочка в n-мерном пространстве ]] | ||
| − | * [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника за n^2 ]] | + | * [[ Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]] |
* [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой ]] | * [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой ]] | ||
* [[ Пересечение полуплоскостей, связь с выпуклыми оболочками | Пересечение полуплоскостей, связь с выпуклыми оболочками ]] | * [[ Пересечение полуплоскостей, связь с выпуклыми оболочками | Пересечение полуплоскостей, связь с выпуклыми оболочками ]] | ||
Версия 17:50, 19 января 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)
- Локализация в ППЛГ методом полос (персистентные деревья)
- Алгоритм Киркпатрика детализации триангуляции
- Трапецоидная карта
