Изменения

Перейти к: навигация, поиск

Вычислительная геометрия

242 байта добавлено, 15:27, 12 декабря 2016
Основание вычислительной геометрии
== Основание вычислительной геометрии ==
* [[ Аффинное пространство ]]
* [[ Ориентация и объем Объем ]]
* [[ Скалярное произведение и метрика ]]
* [[ Однородные координаты ]]
* [[ Двойственное пространство ]]
== Вычисление геометрических предикатов ==
== Пересечение отрезков ==
* [[ Алгоритм Бентли-Оттмана ]]
* [[ Пересечение множества отрезков ]]
* [[ Алгоритм Балабана ]]
* [[ Пересечение множества отрезков ]]
* [[ Snap rounding ]]
* [[ Пересечение отрезков на сфере ]]
== Поиск ==
* [[ Ортогональный поиск ]]* [[ Пересечение прямоугольника с множеством непересекающихся отрезков К-d деревья и перечисление точек в произвольном прямоугольнике (segment treeстатика) ]]
* [[ Квадродеревья | Квадродерево, сжатое квадродерево ]]
* [[ Skip quadtree: определение, время работы | Skip quadtree: определение, время работы, запрос точек в прямоугольнике ]]
* [[ К-d деревья и перечисление точек в произвольном прямоугольнике (статика) Ортогональный поиск ]]
* [[ Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) ]]
* [[ Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) ]]
* [[ Дерево интервалов (interval tree) и пересечение точки с множеством интервалов ]]
* [[ Пересечение прямоугольника с множеством прямоугольников (PST) | Пересечение прямоугольника с множеством прямоугольников (priority search tree) ]]
== Триангуляция ==
* [[ Триангуляция полигонов (ушная + монотонная) ]]
* [[ Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]]
* [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой ]]
== Алгоритмы локализации ==
* [[ Трапецоидная карта ]]
* [[ Алгоритм Киркпатрика детализации триангуляции ]]
* [[ Принадлежность точки выпуклому и невыпуклому многоугольникам ]]
* [[ Локализация в ППЛГ методом полос (персистентные деревья) ]]
== Триангуляция Делоне и диаграмма Вороного ==
* [[ Триангуляция Делоне ]]
* [[ Триангуляция Делоне на сфере ]]
* [[ Диаграмма Вороного ]]
* [[ Motorcycle graph ]]
== Организационные вопросы ==
* [[Участник:Shersh/Тикеты к вычислительной геометрии (термы 4 и 5) | Правки к конспектам (year 2013)]]* [https://docs.google.com/spreadsheet/ccc?key=0AiudLnRYFaaXdFJZdXBaSHJQT29wd0EwekxSZ0JTZkE&usp=drive_web#gid=4 Список новых теми дополнений] ---- * [[Список тем | Список тем (year 2010)]]
* [[Список тем (year 2012)]]
* [[Обсуждение:Вычислительная геометрия#Сдача конспектов | Сдача конспектов]]
113
правок

Навигация