Изменения

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

---- * [[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-мерном пространстве ]]* [[ Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]]* [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой ]]* [[ Пересечение полуплоскостей, связь с выпуклыми оболочками | Пересечение полуплоскостей, связь с выпуклыми оболочками ]]* [[ Пересечение множества отрезков | Пересечение множества отрезков ]]* [[ Snap rounding | Snap rounding ]]* [[ ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых | ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых ]]* [[ Пересечение многоугольников (PSLG overlaying) | Пересечение многоугольников (PSLG overlaying) ]]* [[ Локализация в ППЛГ методом полос (персистентные деревья) | Локализация в ППЛГ методом полос (персистентные деревья) ]]* [[ Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ. Алгоритм Киркпатрика ]]* [[ Трапецоидная карта | Трапецоидная карта ]]* [[ Пересечение отрезков на сфере | Пересечение отрезков на сфере ]] == Скалярное произведение и мера ==* [[ Диаметр множества точек (вращающиеся калиперы) | Диаметр множества точек (вращающиеся калиперы) ]]* [[ Сумма Минковского (определение, вычисление) | Сумма Минковского (определение, вычисление) ]]* [[ Минимальная охватывающая окружность множества точек | Минимальная охватывающая окружность множества точек ]]* [[ Visibility graph и motion planning | Visibility graph и motion planning ]]* [[ Триангуляция Делоне | Триангуляция Делоне ]]* [[ Диаграмма Вороного | Диаграмма Вороного ]]* [[ straight skeleton | straight skeleton Вычислительная геометрия]]