Список тем — различия между версиями
| Строка 1: | Строка 1: | ||
===Устойчивая реализация алгоритмов вычислительной геометрии.=== | ===Устойчивая реализация алгоритмов вычислительной геометрии.=== | ||
* Как устроены числа с плавающей точкой? | * Как устроены числа с плавающей точкой? | ||
| − | * Расчет погрешности вычисления предиката (на примере вычисления предиката поворота). | + | *: [[Представление_вещественных_чисел]] |
| − | Обратите внимание, что готовить эту тему следует по моей видеолекции, там я расписал вычисление погрешности гораздо аккуратнее. | + | *: [[Представление_чисел_с_плавающей_точкой]] |
| − | * Интервальная арифметика.Длинная арифметика. ESSA. | + | * Расчет погрешности вычисления предиката (на примере вычисления предиката поворота). Обратите внимание, что готовить эту тему следует по моей видеолекции, там я расписал вычисление погрешности гораздо аккуратнее. |
| + | *: [http://compsciclub.ru/node/1563 презентация в csклубе] | ||
| + | * Интервальная арифметика. Длинная арифметика. ESSA. | ||
| + | *: [[Интервальная_арифметика]] | ||
| + | *: {{TODO |t=по ESSA вообще ничего не нашел}} | ||
* Adaptive precision арифметика. | * Adaptive precision арифметика. | ||
| + | *: [[Adaptive_precision_arithmetic]] | ||
| + | *: [http://www.cs.cmu.edu/~quake/robust.html статья Шевчука] | ||
===Конфигурации пространства. Определение и построение.=== | ===Конфигурации пространства. Определение и построение.=== | ||
Версия 04:02, 25 января 2012
Содержание
Устойчивая реализация алгоритмов вычислительной геометрии.
- Как устроены числа с плавающей точкой?
- Расчет погрешности вычисления предиката (на примере вычисления предиката поворота). Обратите внимание, что готовить эту тему следует по моей видеолекции, там я расписал вычисление погрешности гораздо аккуратнее.
- Интервальная арифметика. Длинная арифметика. ESSA.
TODO: по ESSA вообще ничего не нашел
- Adaptive precision арифметика.
Конфигурации пространства. Определение и построение.
- Предикат пересечения отрезков.
- Пересечение множества отрезков (Bentley-Ottmann).
- Представление конфигураций плоскости (DCEL). Конфигурация множества прямых на плоскости. Конфигурация множества отрезков на плоскости.
Конфигурации пространства. Локализация.
- Локализация в выпуклом многоугольнике. Локализация в многоугольнике общего вида. Геометрический хеш.
- Алгоритм Киркпатрика.
- Трапецоидная карта.
- Инкрементальная локализация на дереве отрезков.
- Метод полос.
Выпуклые оболочки на плоскости.
- Алгоритм Джарвиса.
- Алгоритм Эндрюса-Грэма.
- Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек).
- Выпуклая оболочка как аналог quick sort (без дополнительной памяти).
Типовые задачи
- Расписать погрешность предиката (например, поворот отрезка и точки пересечения двух отрезков).
- Пересечение множества окружностей разного радиуса.
- Выпуклая оболочка множества окружностей одинакового радиуса.
- Выпуклая оболочка множества окружностей разного радиуса.
