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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Вычисление геометрических предикатов)
м (rollbackEdits.php mass rollback)
 
(не показано 13 промежуточных версий 6 участников)
Строка 1: Строка 1:
 
== Основание вычислительной геометрии ==
 
== Основание вычислительной геометрии ==
 
* [[ Аффинное пространство ]]
 
* [[ Аффинное пространство ]]
* [[ Ориентация и объем ]]
+
* [[ Объем ]]
 
* [[ Скалярное произведение и метрика ]]
 
* [[ Скалярное произведение и метрика ]]
 
* [[ Однородные координаты ]]
 
* [[ Однородные координаты ]]
 +
* [[ Двойственное пространство ]]
  
 
== Вычисление геометрических предикатов ==
 
== Вычисление геометрических предикатов ==
* [[ Пересечение отрезков и поворот: определение, свойства, вычисление | Вычисление погрешности арифметического выражения на примере ориентации трех точек ]]
+
* [[ Представление чисел с плавающей точкой ]]
 +
* [[ Предикат "левый поворот" ]]
 +
* [[ Пересечение отрезков и поворот: определение, свойства, вычисление ]]
 
* [[ Adaptive precision arithmetic ]]
 
* [[ Adaptive precision arithmetic ]]
* [[ ESSA ]]
 
 
* [[ Интервальная арифметика ]]
 
* [[ Интервальная арифметика ]]
* [[ Рациональная арифметика ]]
 
----
 
* [[ Представление чисел с плавающей точкой ]]
 
* [[ Предикат "левый поворот" ]]
 
  
 
== Пересечение отрезков ==
 
== Пересечение отрезков ==
 
* [[ Алгоритм Бентли-Оттмана ]]
 
* [[ Алгоритм Бентли-Оттмана ]]
 +
* [[ Пересечение множества отрезков ]]
 
* [[ Алгоритм Балабана ]]
 
* [[ Алгоритм Балабана ]]
* [[ Пересечение множества отрезков ]]
 
 
* [[ Snap rounding ]]
 
* [[ Snap rounding ]]
 
* [[ Пересечение отрезков на сфере ]]
 
* [[ Пересечение отрезков на сфере ]]
Строка 29: Строка 27:
  
 
== Поиск ==
 
== Поиск ==
* [[ Ортогональный поиск ]]
+
* [[ К-d деревья и перечисление точек в произвольном прямоугольнике (статика) ]]
* [[ Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) ]]
 
 
* [[ Квадродеревья | Квадродерево, сжатое квадродерево ]]
 
* [[ Квадродеревья | Квадродерево, сжатое квадродерево ]]
 
* [[ Skip quadtree: определение, время работы | Skip quadtree: определение, время работы, запрос точек в прямоугольнике ]]
 
* [[ Skip quadtree: определение, время работы | Skip quadtree: определение, время работы, запрос точек в прямоугольнике ]]
* [[ К-d деревья и перечисление точек в произвольном прямоугольнике (статика) ]]
+
* [[ Ортогональный поиск ]]
 
* [[ Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) ]]
 
* [[ Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) ]]
 +
* [[ Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) ]]
 
* [[ Дерево интервалов (interval tree) и пересечение точки с множеством интервалов ]]
 
* [[ Дерево интервалов (interval tree) и пересечение точки с множеством интервалов ]]
 
* [[ Пересечение прямоугольника с множеством прямоугольников (PST) | Пересечение прямоугольника с множеством прямоугольников (priority search tree) ]]
 
* [[ Пересечение прямоугольника с множеством прямоугольников (PST) | Пересечение прямоугольника с множеством прямоугольников (priority search tree) ]]
Строка 40: Строка 38:
  
 
== Триангуляция ==
 
== Триангуляция ==
* [[ Триангуляция полигонов (ушная + монотонная) ]]
 
 
* [[ Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]]
 
* [[ Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]]
 
* [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой ]]
 
* [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой ]]
Строка 50: Строка 47:
  
 
== Алгоритмы локализации ==
 
== Алгоритмы локализации ==
* [[ Трапецоидная карта ]]
 
* [[ Алгоритм Киркпатрика детализации триангуляции ]]
 
 
* [[ Принадлежность точки выпуклому и невыпуклому многоугольникам ]]
 
* [[ Принадлежность точки выпуклому и невыпуклому многоугольникам ]]
 
* [[ Локализация в ППЛГ методом полос (персистентные деревья) ]]
 
* [[ Локализация в ППЛГ методом полос (персистентные деревья) ]]
Строка 59: Строка 54:
 
== Триангуляция Делоне и диаграмма Вороного ==
 
== Триангуляция Делоне и диаграмма Вороного ==
 
* [[ Триангуляция Делоне ]]
 
* [[ Триангуляция Делоне ]]
 +
* [[ Триангуляция Делоне на сфере ]]
 
* [[ Диаграмма Вороного ]]
 
* [[ Диаграмма Вороного ]]
 
* [[ Motorcycle graph ]]
 
* [[ Motorcycle graph ]]
Строка 80: Строка 76:
  
 
== Организационные вопросы ==
 
== Организационные вопросы ==
* [[Список тем]]
+
* [[Участник:Shersh/Тикеты к вычислительной геометрии (термы 4 и 5) | Правки к конспектам (year 2013)]]
 +
* [https://docs.google.com/spreadsheet/ccc?key=0AiudLnRYFaaXdFJZdXBaSHJQT29wd0EwekxSZ0JTZkE&usp=drive_web#gid=4 Список новых тем и дополнений]
 +
 
 +
----
 +
 
 +
* [[Список тем | Список тем (year 2010)]]
 
* [[Список тем (year 2012)]]
 
* [[Список тем (year 2012)]]
 
* [[Обсуждение:Вычислительная геометрия#Сдача конспектов | Сдача конспектов]]
 
* [[Обсуждение:Вычислительная геометрия#Сдача конспектов | Сдача конспектов]]

Текущая версия на 19:23, 4 сентября 2022

Основание вычислительной геометрии

Вычисление геометрических предикатов

Пересечение отрезков

Выпуклые оболочки

Поиск

Триангуляция

ППЛГ и РСДС

Алгоритмы локализации

Триангуляция Делоне и диаграмма Вороного

Планирование движения (Motion planning)

Задачи

Программирование

Организационные вопросы