Изменения

[[Категория: Вычислительная геометрия]]== Основание вычислительной геометрии ==* [[Представление чисел с плавающей точкойАффинное пространство ]]* [[Предикат "левый поворот"Объем ]]* [[Интервальная арифметикаСкалярное произведение и метрика ]]* [[Adaptive precision arithmeticОднородные координаты ]]* [[Алгоритм Бентли-ОттманаДвойственное пространство ]]* [[Конфигурация]]== Вычисление геометрических предикатов ==* [[Трапецоидная картаПредставление чисел с плавающей точкой ]]* [[Алгоритм Киркпатрика детализации триангуляцииПредикат "левый поворот" ]]* [[Пересечение окружностейотрезков и поворот: определение, свойства, вычисление ]]* [[Упрощение полигональной цепи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--дерево ]]

* [[CMake_Tutorial|Туториал по cmake]]* [[Тестирование с использованием Google Test]]== Базовые алгоритмы и структуры данных Триангуляция ==* [[ Skip quadtree: определение, время работы | Skip quadtree: определение, время работы ]]* [[ К-d деревья и перечисление точек в произвольном прямоугольнике (статика) | К-d деревья и перечисление точек в произвольном прямоугольнике (статика) ]]* [[ Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) | Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) ]]* [[ Дерево интервалов (interval tree) и пересечение точки с множеством интервалов | Дерево интервалов (interval tree) и пересечение точки с множеством интервалов ]]* [[ Пересечение прямоугольника с множеством прямоугольников (PST) | Пересечение прямоугольника с множеством прямоугольников (PST) ]]== Аффинное пространство ==* [[ Пересечение отрезков и поворот: определение, свойства, вычисление | Пересечение отрезков и поворот: определение, свойства, вычисление ]]* [[ Принадлежность точки выпуклому и невыпуклому многоугольникам | Принадлежность точки выпуклому и невыпуклому многоугольникам ]]* [[ Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) | Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) ]]* [[ Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull | Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull ]]* [[ Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) ]]* [[ Выпуклая оболочка в n-мерном пространстве | Выпуклая оболочка в n-мерном пространстве ]]

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

* [[ Трапецоидная карта | Трапецоидная карта ]]

== Скалярное произведение Триангуляция Делоне и мера диаграмма Вороного ==* [[ Диаметр множества точек (вращающиеся калиперы) | Диаметр множества точек (вращающиеся калиперы) Триангуляция Делоне ]]* [[ Триангуляция Делоне на сфере ]]* [[ Диаграмма Вороного ]]* [[ Motorcycle graph ]]* [[ Сумма Минковского Straight skeleton ]] == Планирование движения (определение, вычислениеMotion planning) | ==* [[ Сумма Минковского (определение, вычисление) ]]* [[ Минимальная охватывающая окружность Visibility graph и motion planning ]] == Задачи ==* [[ Диаметр множества точек | (вращающиеся калиперы) ]]* [[ Минимальная охватывающая окружность множества точек ]]* [[ Visibility graph Пересечение окружностей ]]* [[ Упрощение полигональной цепи ]]* [[ Вычисление площади и объема ]]* [[ Пересечение выпуклых многоугольников ]] == Программирование ==* [[ CMake_Tutorial|Туториал по cmake ]]* [[ Тестирование с использованием Google Test ]] == Организационные вопросы ==* [[Участник:Shersh/Тикеты к вычислительной геометрии (термы 4 и motion planning 5) | Visibility graph Правки к конспектам (year 2013)]]* [https://docs.google.com/spreadsheet/ccc?key=0AiudLnRYFaaXdFJZdXBaSHJQT29wd0EwekxSZ0JTZkE&usp=drive_web#gid=4 Список новых тем и motion planning дополнений] ---- * [[Список тем | Список тем (year 2010)]]* [[Список тем (year 2012)]]* [[ Триангуляция Делоне Обсуждение:Вычислительная геометрия#Сдача конспектов | Триангуляция Делоне Сдача конспектов]]* [[ Диаграмма Вороного Обсуждение:Вычислительная геометрия#Презентации | Диаграмма Вороного Сдача презентаций]]* [[ straight skeleton Обсуждение:Вычислительная геометрия#Условия и чекеры | straight skeleton Условия и чекеры]] [[Категория: Вычислительная геометрия]]