Вычислительная геометрия — различия между версиями
Mcquay (обсуждение | вклад) м (→Вычисление геометрических предикатов) |
Mcquay (обсуждение | вклад) (Отмена правки 44902 участника Mcquay (обсуждение)) |
||
| Строка 6: | Строка 6: | ||
== Вычисление геометрических предикатов == | == Вычисление геометрических предикатов == | ||
| − | * [[ Пересечение отрезков и поворот: определение, свойства, вычисление | + | * [[ Представление чисел с плавающей точкой ]] |
| + | * [[ Предикат "левый поворот" ]] | ||
| + | * [[ Пересечение отрезков и поворот: определение, свойства, вычисление ]] | ||
* [[ Adaptive precision arithmetic ]] | * [[ Adaptive precision arithmetic ]] | ||
| − | |||
* [[ Интервальная арифметика ]] | * [[ Интервальная арифметика ]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
== Пересечение отрезков == | == Пересечение отрезков == | ||
Версия 09:11, 20 февраля 2015
Содержание
- 1 Основание вычислительной геометрии
- 2 Вычисление геометрических предикатов
- 3 Пересечение отрезков
- 4 Выпуклые оболочки
- 5 Поиск
- 6 Триангуляция
- 7 ППЛГ и РСДС
- 8 Алгоритмы локализации
- 9 Триангуляция Делоне и диаграмма Вороного
- 10 Планирование движения (Motion planning)
- 11 Задачи
- 12 Программирование
- 13 Организационные вопросы
Основание вычислительной геометрии
Вычисление геометрических предикатов
- Представление чисел с плавающей точкой
- Предикат "левый поворот"
- Пересечение отрезков и поворот: определение, свойства, вычисление
- Adaptive precision arithmetic
- Интервальная арифметика
Пересечение отрезков
- Алгоритм Бентли-Оттмана
- Алгоритм Балабана
- Пересечение множества отрезков
- Snap rounding
- Пересечение отрезков на сфере
Выпуклые оболочки
- Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull
- Динамическая выпуклая оболочка
- Выпуклая оболочка в n-мерном пространстве
- Пересечение полуплоскостей, связь с выпуклыми оболочками
Поиск
- Ортогональный поиск
- Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)
- Квадродерево, сжатое квадродерево
- Skip quadtree: определение, время работы, запрос точек в прямоугольнике
- К-d деревья и перечисление точек в произвольном прямоугольнике (статика)
- Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree)
- Дерево интервалов (interval tree) и пересечение точки с множеством интервалов
- Пересечение прямоугольника с множеством прямоугольников (priority search tree)
- BSP-дерево
Триангуляция
- Триангуляция полигонов (ушная + монотонная)
- Триангуляция многоугольника за n^2
- Триангуляция многоугольника заметающей прямой
ППЛГ и РСДС
- Конфигурация
- ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых
- Пересечение многоугольников (PSLG overlaying)
Алгоритмы локализации
- Трапецоидная карта
- Алгоритм Киркпатрика детализации триангуляции
- Принадлежность точки выпуклому и невыпуклому многоугольникам
- Локализация в ППЛГ методом полос (персистентные деревья)
- Локализация в ППЛГ. Алгоритм Киркпатрика
- Трапецоидная карта
Триангуляция Делоне и диаграмма Вороного
Планирование движения (Motion planning)
Задачи
- Диаметр множества точек (вращающиеся калиперы)
- Минимальная охватывающая окружность множества точек
- Пересечение окружностей
- Упрощение полигональной цепи
- Вычисление площади и объема
- Пересечение выпуклых многоугольников
