Список тем — различия между версиями
(→Конфигурации пространства. Определение и построение.) |
|||
| Строка 14: | Строка 14: | ||
===Конфигурации пространства. Определение и построение.=== | ===Конфигурации пространства. Определение и построение.=== | ||
* Предикат пересечения отрезков. | * Предикат пересечения отрезков. | ||
| + | *: [[Предикат_"левый_поворот"]] | ||
* Пересечение множества отрезков (Bentley-Ottmann). | * Пересечение множества отрезков (Bentley-Ottmann). | ||
| + | *: [[Алгоритм_Бентли-Оттмана]] | ||
* Представление конфигураций плоскости (DCEL). Конфигурация множества прямых на плоскости. Конфигурация множества отрезков на плоскости. | * Представление конфигураций плоскости (DCEL). Конфигурация множества прямых на плоскости. Конфигурация множества отрезков на плоскости. | ||
| + | *: [[Конфигурация]] | ||
===Конфигурации пространства. Локализация.=== | ===Конфигурации пространства. Локализация.=== | ||
Версия 04:06, 25 января 2012
Содержание
Устойчивая реализация алгоритмов вычислительной геометрии.
- Как устроены числа с плавающей точкой?
- Расчет погрешности вычисления предиката (на примере вычисления предиката поворота). Обратите внимание, что готовить эту тему следует по моей видеолекции, там я расписал вычисление погрешности гораздо аккуратнее.
- Интервальная арифметика. Длинная арифметика. ESSA.
TODO: по ESSA вообще ничего не нашел
- Adaptive precision арифметика.
Конфигурации пространства. Определение и построение.
- Предикат пересечения отрезков.
- Пересечение множества отрезков (Bentley-Ottmann).
- Представление конфигураций плоскости (DCEL). Конфигурация множества прямых на плоскости. Конфигурация множества отрезков на плоскости.
Конфигурации пространства. Локализация.
- Локализация в выпуклом многоугольнике. Локализация в многоугольнике общего вида. Геометрический хеш.
- Алгоритм Киркпатрика.
- Трапецоидная карта.
- Инкрементальная локализация на дереве отрезков.
- Метод полос.
Выпуклые оболочки на плоскости.
- Алгоритм Джарвиса.
- Алгоритм Эндрюса-Грэма.
- Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек).
- Выпуклая оболочка как аналог quick sort (без дополнительной памяти).
Типовые задачи
- Расписать погрешность предиката (например, поворот отрезка и точки пересечения двух отрезков).
- Пересечение множества окружностей разного радиуса.
- Выпуклая оболочка множества окружностей одинакового радиуса.
- Выпуклая оболочка множества окружностей разного радиуса.
