Вычислительная геометрия — различия между версиями
Kabanov (обсуждение | вклад) м |
|||
| Строка 1: | Строка 1: | ||
| − | |||
* [[Представление чисел с плавающей точкой]] | * [[Представление чисел с плавающей точкой]] | ||
* [[Предикат "левый поворот"]] | * [[Предикат "левый поворот"]] | ||
| Строка 11: | Строка 10: | ||
* [[Упрощение полигональной цепи]] | * [[Упрощение полигональной цепи]] | ||
* [[Ортогональный поиск]] | * [[Ортогональный поиск]] | ||
| − | |||
* [[Триангуляция полигонов (ушная + монотонная)]] | * [[Триангуляция полигонов (ушная + монотонная)]] | ||
| Строка 50: | Строка 48: | ||
* [[ Трапецоидная карта | Трапецоидная карта ]] | * [[ Трапецоидная карта | Трапецоидная карта ]] | ||
* [[ Пересечение отрезков на сфере | Пересечение отрезков на сфере ]] | * [[ Пересечение отрезков на сфере | Пересечение отрезков на сфере ]] | ||
| + | |||
| + | == Построение выпуклых оболочек == | ||
| + | * [[Алгоритм Эндрю-Грэхема]] | ||
== Скалярное произведение и мера == | == Скалярное произведение и мера == | ||
| Строка 59: | Строка 60: | ||
* [[ Диаграмма Вороного | Диаграмма Вороного ]] | * [[ Диаграмма Вороного | Диаграмма Вороного ]] | ||
* [[ straight skeleton | straight skeleton ]] | * [[ straight skeleton | straight skeleton ]] | ||
| + | |||
| + | [[Категория: Вычислительная геометрия]] | ||
Версия 23:50, 6 июля 2014
- Представление чисел с плавающей точкой
- Предикат "левый поворот"
- Интервальная арифметика
- Adaptive precision arithmetic
- Алгоритм Бентли-Оттмана
- Конфигурация
- Трапецоидная карта
- Алгоритм Киркпатрика детализации триангуляции
- Пересечение окружностей
- Упрощение полигональной цепи
- Ортогональный поиск
- Триангуляция полигонов (ушная + монотонная)
Содержание
Базовые алгоритмы и структуры данных
- Skip quadtree: определение, время работы
- К-d деревья и перечисление точек в произвольном прямоугольнике (статика)
- Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree)
- Дерево интервалов (interval tree) и пересечение точки с множеством интервалов
- Пересечение прямоугольника с множеством прямоугольников (PST)
Аффинное пространство
- Пересечение отрезков и поворот: определение, свойства, вычисление
- Принадлежность точки выпуклому и невыпуклому многоугольникам
- Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)
- Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull
- Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление)
- Выпуклая оболочка в n-мерном пространстве
- Триангуляция многоугольника за n^2
- Триангуляция многоугольника заметающей прямой
- Пересечение полуплоскостей, связь с выпуклыми оболочками
- Пересечение множества отрезков
- Snap rounding
- ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых
- Пересечение многоугольников (PSLG overlaying)
- Локализация в ППЛГ методом полос (персистентные деревья)
- Локализация в ППЛГ. Алгоритм Киркпатрика
- Трапецоидная карта
- Пересечение отрезков на сфере
