Список тем

Материал из Викиконспекты
Перейти к: навигация, поиск

Устойчивая реализация алгоритмов вычислительной геометрии.

  • Как устроены числа с плавающей точкой?
  • Расчет погрешности вычисления предиката (на примере вычисления предиката поворота).

Обратите внимание, что готовить эту тему следует по моей видеолекции, там я расписал вычисление погрешности гораздо аккуратнее.

  • Интервальная арифметика.Длинная арифметика. ESSA.
  • Adaptive precision арифметика.

Конфигурации пространства. Определение и построение.

  • Предикат пересечения отрезков.
  • Пересечение множества отрезков (Bentley-Ottmann).
  • Представление конфигураций плоскости (DCEL). Конфигурация множества прямых на плоскости. Конфигурация множества отрезков на плоскости.

Конфигурации пространства. Локализация.

  • Локализация в выпуклом многоугольнике. Локализация в многоугольнике общего вида. Геометрический хеш.
  • Алгоритм Киркпатрика.
  • Трапецоидная карта.
  • Инкрементальная локализация на дереве отрезков.
  • Метод полос.

Выпуклые оболочки на плоскости.

  • Алгоритм Джарвиса.
  • Алгоритм Эндрюса-Грэма.
  • Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек).
  • Выпуклая оболочка как аналог quick sort (без дополнительной памяти).

Типовые задачи

  • Расписать погрешность предиката (например, поворот отрезка и точки пересечения двух отрезков).
  • Пересечение множества окружностей разного радиуса.
  • Выпуклая оболочка множества окружностей одинакового радиуса.
  • Выпуклая оболочка множества окружностей разного радиуса.