Вычислительная геометрия — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 26: Строка 26:
 
* [[Тестирование с использованием Google Test]]
 
* [[Тестирование с использованием Google Test]]
 
== Базовые алгоритмы и структуры данных ==
 
== Базовые алгоритмы и структуры данных ==
* [[Skip quadtree]]
+
* [[ Skip quadtree: определение, время работы | Skip quadtree: определение, время работы ]]
* [[Квадродеревья и перечисление точек в произвольном прямоугольнике]]
+
* [[ Квадродеревья и перечисление точек в произвольном прямоугольнике (статика) | Квадродеревья и перечисление точек в произвольном прямоугольнике (статика) ]]
== Афинное пространство ==
+
* [[ Перечисление точек в произвольном прямоугольнике за 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 | Триангуляция многоугольника за 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 ]]
 +
* [[ WRP + continuous Dijkstra (специально для Сени и Юрика :) | WRP + continuous Dijkstra (специально для Сени и Юрика :) ]]

Версия 19:24, 4 января 2014



Базовые алгоритмы и структуры данных

Аффинное пространство

Скалярное произведение и мера