Вычислительная геометрия

Основание вычислительной геометрии

• Аффинное пространство
• Ориентация и объем
• Скалярное произведение и метрика
• Однородные координаты

Вычисление геометрических предикатов

• Представление чисел с плавающей точкой
• Предикат "левый поворот"
• Пересечение отрезков и поворот: определение, свойства, вычисление
• Adaptive precision arithmetic
• Интервальная арифметика

Пересечение отрезков

• Алгоритм Бентли-Оттмана
• Алгоритм Балабана
• Пересечение множества отрезков
• Snap rounding
• Пересечение отрезков на сфере

Выпуклые оболочки

• Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull
• Динамическая выпуклая оболочка
• Выпуклая оболочка в n-мерном пространстве
• Пересечение полуплоскостей, связь с выпуклыми оболочками

Поиск

• Ортогональный поиск
• Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)
• Квадродерево, сжатое квадродерево
• Skip quadtree: определение, время работы, запрос точек в прямоугольнике
• К-d деревья и перечисление точек в произвольном прямоугольнике (статика)
• Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree)
• Дерево интервалов (interval tree) и пересечение точки с множеством интервалов
• Пересечение прямоугольника с множеством прямоугольников (priority search tree)
• BSP-дерево

Триангуляция

• Триангуляция полигонов (ушная + монотонная)
• Триангуляция многоугольника за n^2
• Триангуляция многоугольника заметающей прямой

ППЛГ и РСДС

• Конфигурация
• ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых
• Пересечение многоугольников (PSLG overlaying)

Алгоритмы локализации

• Трапецоидная карта
• Алгоритм Киркпатрика детализации триангуляции
• Принадлежность точки выпуклому и невыпуклому многоугольникам
• Локализация в ППЛГ методом полос (персистентные деревья)
• Локализация в ППЛГ. Алгоритм Киркпатрика
• Трапецоидная карта

Триангуляция Делоне и диаграмма Вороного

• Триангуляция Делоне
• Диаграмма Вороного
• Motorcycle graph
• Straight skeleton

Планирование движения (Motion planning)

• Сумма Минковского (определение, вычисление)
• Visibility graph и motion planning

Задачи

• Диаметр множества точек (вращающиеся калиперы)
• Минимальная охватывающая окружность множества точек
• Пересечение окружностей
• Упрощение полигональной цепи
• Вычисление площади и объема
• Пересечение выпуклых многоугольников

Программирование

• Туториал по cmake
• Тестирование с использованием Google Test

Организационные вопросы

• Список тем
• Список тем (year 2012)
• Сдача конспектов
• Сдача презентаций
• Условия и чекеры