Список тем — различия между версиями
(→Конфигурации пространства. Определение и построение.) |
(→Конфигурации пространства. Локализация.) |
||
| Строка 23: | Строка 23: | ||
* Локализация в выпуклом многоугольнике. Локализация в многоугольнике общего вида. Геометрический хеш. | * Локализация в выпуклом многоугольнике. Локализация в многоугольнике общего вида. Геометрический хеш. | ||
| + | *: [http://en.wikipedia.org/wiki/Geometric_hashing Wikipedia — Geometric hashing] — на лекции не был, посмотрите, мало ли это не то. | ||
* Алгоритм Киркпатрика. | * Алгоритм Киркпатрика. | ||
| + | *: [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%B8%D1%80%D0%BA%D0%BF%D0%B0%D1%82%D1%80%D0%B8%D0%BA%D0%B0 Википедия — Алгорити Киркпатика] — что это делает здесь, казалось бы, это надо в выпуклые оболочки. | ||
* Трапецоидная карта. | * Трапецоидная карта. | ||
* Инкрементальная локализация на дереве отрезков. | * Инкрементальная локализация на дереве отрезков. | ||
Версия 10:58, 25 января 2012
Содержание
Устойчивая реализация алгоритмов вычислительной геометрии.
- Как устроены числа с плавающей точкой?
- Расчет погрешности вычисления предиката (на примере вычисления предиката поворота). Обратите внимание, что готовить эту тему следует по моей видеолекции, там я расписал вычисление погрешности гораздо аккуратнее.
- Интервальная арифметика. Длинная арифметика. ESSA.
TODO: по ESSA вообще ничего не нашел
- Adaptive precision арифметика.
Конфигурации пространства. Определение и построение.
- Предикат пересечения отрезков.
- Пересечение множества отрезков (Bentley-Ottmann).
- Представление конфигураций плоскости (DCEL). Конфигурация множества прямых на плоскости. Конфигурация множества отрезков на плоскости.
Конфигурации пространства. Локализация.
- Локализация в выпуклом многоугольнике. Локализация в многоугольнике общего вида. Геометрический хеш.
- Wikipedia — Geometric hashing — на лекции не был, посмотрите, мало ли это не то.
- Алгоритм Киркпатрика.
- Википедия — Алгорити Киркпатика — что это делает здесь, казалось бы, это надо в выпуклые оболочки.
- Трапецоидная карта.
- Инкрементальная локализация на дереве отрезков.
- Метод полос.
Выпуклые оболочки на плоскости.
- Алгоритм Джарвиса.
- Алгоритм Эндрюса-Грэма.
- Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек).
- Выпуклая оболочка как аналог quick sort (без дополнительной памяти).
Типовые задачи
- Расписать погрешность предиката (например, поворот отрезка и точки пересечения двух отрезков).
- Пересечение множества окружностей разного радиуса.
- Выпуклая оболочка множества окружностей одинакового радиуса.
- Выпуклая оболочка множества окружностей разного радиуса.
