Изменения

* [[Представление чисел с плавающей точкой]]* [[Предикат "левый поворот"]]* [[Интервальная арифметика]]* [[Adaptive precision arithmetic]]* [[Алгоритм Бентли-Оттмана]]* [[Конфигурация]]* [[Трапецоидная карта]]* [[Алгоритм Киркпатрика детализации триангуляции]]* [[Пересечение окружностей]]== Основание вычислительной геометрии ==* [[Упрощение полигональной цепиАффинное пространство ]]* [[Ортогональный поискОриентация и объем ]]* [[Триангуляция полигонов (ушная + монотонная)Скалярное произведение и метрика ]]

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

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

== Поиск ==* [[CMake_Tutorial|Туториал по cmakeОртогональный поиск ]]* [[Тестирование Пересечение прямоугольника с использованием Google Testмножеством непересекающихся отрезков (segment tree) ]]== Базовые алгоритмы и структуры данных ==* [[Квадродеревья | Квадродерево, сжатое квадродерево]]

* [[ К-d деревья и перечисление точек в произвольном прямоугольнике (статика) | К-d деревья и перечисление точек в произвольном прямоугольнике (статика) ]]* [[ Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) | Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) ]]* [[ Дерево интервалов (interval tree) и пересечение точки с множеством интервалов | Дерево интервалов (interval tree) и пересечение точки с множеством интервалов ]]

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

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

* [[ Трапецоидная карта | Трапецоидная карта ]]* [[ Пересечение отрезков на сфере | Пересечение отрезков на сфере ]]* [[BSP-дерево]]

== Скалярное произведение Триангуляция Делоне и мера диаграмма Вороного ==* [[ Диаметр множества точек (вращающиеся калиперы) | Диаметр множества точек (вращающиеся калиперы) ]]* [[ Сумма Минковского (определение, вычисление) | Сумма Минковского (определение, вычисление) ]]* [[ Минимальная охватывающая окружность множества точек | Минимальная охватывающая окружность множества точек ]]* [[ Visibility graph и motion planning | Visibility graph и motion planning ]]* [[ Триангуляция Делоне | Триангуляция Делоне ]]* [[ Диаграмма Вороного | Диаграмма Вороного ]]* [[Motorcycle graph]]* [[Straight skeleton]]

== Добавьте в нужное место Планирование движения (Motion planning) ==* [[Алгоритм БалабанаСумма Минковского (определение, вычисление) ]]* [[ Visibility graph и motion planning ]] == Задачи ==* [[ Диаметр множества точек (вращающиеся калиперы) ]]* [[ Минимальная охватывающая окружность множества точек ]]* [[ Пересечение окружностей ]]* [[ Упрощение полигональной цепи ]]* [[ Вычисление площади и объема ]]* [[ Пересечение выпуклых многоугольников ]] == Программирование ==* [[ CMake_Tutorial|Туториал по cmake ]]* [[ Тестирование с использованием Google Test ]] == Организационные вопросы ==* [[Список тем]]* [[Список тем (year 2012)]]* [[Обсуждение:Вычислительная геометрия#Сдача конспектов | Сдача конспектов]]* [[Обсуждение:Вычислительная геометрия#Презентации | Сдача презентаций]]* [[Обсуждение:Вычислительная геометрия#Условия и чекеры | Условия и чекеры]]