Список тем

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

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

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

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

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

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

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

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

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

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

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

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