Просмотр исходного текста страницы Вычислительная геометрия

== Основание вычислительной геометрии ==
* [[ Аффинное пространство ]]
* [[ Ориентация и объем ]]
* [[ Скалярное произведение и метрика ]]
* [[ Однородные координаты ]]
* [[ Двойственное пространство ]]

== Вычисление геометрических предикатов ==
* [[ Представление чисел с плавающей точкой ]]
* [[ Предикат "левый поворот" ]]
* [[ Пересечение отрезков и поворот: определение, свойства, вычисление ]]
* [[ Adaptive precision arithmetic ]]
* [[ Интервальная арифметика ]]

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

== Выпуклые оболочки ==
* [[ Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull ]]
* [[ Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка ]]
* [[ Выпуклая оболочка в n-мерном пространстве ]]
* [[ Пересечение полуплоскостей, связь с выпуклыми оболочками ]]

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

== Триангуляция ==
* [[ Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]]
* [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой ]]

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

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

== Триангуляция Делоне и диаграмма Вороного ==
* [[ Триангуляция Делоне ]]
* [[ Триангуляция Делоне на сфере ]]
* [[ Диаграмма Вороного ]]
* [[ Motorcycle graph ]]
* [[ Straight skeleton ]]

== Планирование движения (Motion planning) ==
* [[ Сумма Минковского (определение, вычисление) ]]
* [[ Visibility graph и motion planning ]]

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

== Программирование ==
* [[ CMake_Tutorial|Туториал по cmake ]]
* [[ Тестирование с использованием Google Test ]]

== Организационные вопросы ==
* [[Участник:Shersh/Тикеты к вычислительной геометрии (термы 4 и 5) | Правки к конспектам (year 2013)]]
* [https://docs.google.com/spreadsheet/ccc?key=0AiudLnRYFaaXdFJZdXBaSHJQT29wd0EwekxSZ0JTZkE&usp=drive_web#gid=4 Список новых тем и дополнений]

----

* [[Список тем | Список тем (year 2010)]]
* [[Список тем (year 2012)]]
* [[Обсуждение:Вычислительная геометрия#Сдача конспектов | Сдача конспектов]]
* [[Обсуждение:Вычислительная геометрия#Презентации | Сдача презентаций]]
* [[Обсуждение:Вычислительная геометрия#Условия и чекеры | Условия и чекеры]]

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