113
правок
Изменения
→Основание вычислительной геометрии
== Вычисление геометрических предикатов ==* [[ Представление чисел с плавающей точкой ]]* [[ Предикат "левый поворот" ]]* [[ Пересечение отрезков и поворот: определение, свойства, вычисление ]]* [[ Adaptive precision arithmetic ]]* [[ Интервальная арифметика ]] == Пересечение отрезков ==* [[ Алгоритм Бентли----Оттмана ]]* [[ Пересечение множества отрезков ]]* [[ Алгоритм Балабана ]]* [[ Snap rounding ]]* [[ Пересечение отрезков на сфере ]]
== Выпуклые оболочки ==* [[Список темСтатические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull ]]* [[Список тем Динамическая выпуклая оболочка (year 2012достаточно 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]]
* [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой ]]
* [[ Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ. Алгоритм Киркпатрика ]]
* [[ Трапецоидная карта | Трапецоидная карта ]]* [[ Пересечение отрезков на сфере | Пересечение отрезков на сфере ]]
== Построение выпуклых оболочек Триангуляция Делоне и диаграмма Вороного ==* [[Алгоритм Эндрю-ГрэхемаТриангуляция Делоне ]]* [[ Триангуляция Делоне на сфере ]]* [[ Диаграмма Вороного ]]* [[ 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)]]* [[ Visibility graph и motion planning | Visibility graph и motion planning Список тем (year 2012)]]* [[ Триангуляция Делоне Обсуждение:Вычислительная геометрия#Сдача конспектов | Триангуляция Делоне Сдача конспектов]]* [[ Диаграмма Вороного Обсуждение:Вычислительная геометрия#Презентации | Диаграмма Вороного Сдача презентаций]]* [[ straight skeleton Обсуждение:Вычислительная геометрия#Условия и чекеры | straight skeleton Условия и чекеры]]
[[Категория: Вычислительная геометрия]]