Участник:Shersh/Тикеты к вычислительной геометрии (термы 4 и 5)

Нумерованные замечания — по содержанию, маркированные — по оформлению

Модель вычислений

Арифметика

1. Представление чисел с плавающей точкой
2. Предикат "левый поворот"
3. Интервальная арифметика
4. Adaptive precision arithmetic

Технические подробности

1. Запуск проекта визуализации cg (10)
   1. Небольшой туториал, как начать работу с библиотекой визуализации, что поставить и как запустить
   2. Неплохо бы ещё скриншоты добавить (чтобы совсем всем всё было понятно)
2. Туториал по cmake (20)
   1. Сделать конспект более формальным
   2. Как установить, что вообще надо (ссылки добавить)
   3. Простые и последовательные примеры: сборка простого файла, нескольких файлов, как подключить буст, gmp, gtest
   4. Объяснение происходящего в библиотеке визуализации cg
   5. Примеры полных скриптов

   • Добавить категории

3. Тестирование с использованием Google Test (5)
   1. Ссылка на код битая, добавить пример кода с github

   • Задачу в Шаблон
   • Добавить категории
   • Интервики
   • Имя функции в \mathrm

Аффинное пространство

• Алгоритм Бентли-Оттмана
• Трапецоидная карта
• Алгоритм Киркпатрика детализации триангуляции
• Пересечение окружностей
• Упрощение полигональной цепи
• Ортогональный поиск
• Триангуляция полигонов (ушная + монотонная)

1. Пересечение отрезков и поворот: определение, свойства, вычисление
2. Принадлежность точки выпуклому и невыпуклому многоугольникам
3. Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)
4. Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull
5. Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление)
6. Выпуклая оболочка в n-мерном пространстве
7. Триангуляция многоугольника за n^2
8. Триангуляция многоугольника заметающей прямой
9. Пересечение полуплоскостей, связь с выпуклыми оболочками
10. Пересечение множества отрезков
11. Snap rounding
12. Конфигурация
13. ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых
14. Пересечение многоугольников (PSLG overlaying)
15. Локализация в ППЛГ методом полос (персистентные деревья)
16. Локализация в ППЛГ. Алгоритм Киркпатрика
17. Трапецоидная карта
18. Пересечение отрезков на сфере
19. BSP-дерево

Скалярное произведение и мера (проверяется)

1. Диаметр множества точек (вращающиеся калиперы)
2. Сумма Минковского (определение, вычисление)
3. Минимальная охватывающая окружность множества точек
4. Visibility graph и motion planning
5. Триангуляция Делоне
6. Диаграмма Вороного
7. Motorcycle graph
8. Straight skeleton