Вычислительная геометрия — различия между версиями
Mcquay (обсуждение | вклад) м (→Вычисление геометрических предикатов) |
м (rollbackEdits.php mass rollback) |
||
| (не показано 13 промежуточных версий 6 участников) | |||
| Строка 1: | Строка 1: | ||
== Основание вычислительной геометрии == | == Основание вычислительной геометрии == | ||
* [[ Аффинное пространство ]] | * [[ Аффинное пространство ]] | ||
| − | * [[ | + | * [[ Объем ]] |
* [[ Скалярное произведение и метрика ]] | * [[ Скалярное произведение и метрика ]] | ||
* [[ Однородные координаты ]] | * [[ Однородные координаты ]] | ||
| + | * [[ Двойственное пространство ]] | ||
== Вычисление геометрических предикатов == | == Вычисление геометрических предикатов == | ||
| − | * [[ Пересечение отрезков и поворот: определение, свойства, вычисление | + | * [[ Представление чисел с плавающей точкой ]] |
| + | * [[ Предикат "левый поворот" ]] | ||
| + | * [[ Пересечение отрезков и поворот: определение, свойства, вычисление ]] | ||
* [[ Adaptive precision arithmetic ]] | * [[ Adaptive precision arithmetic ]] | ||
| − | |||
* [[ Интервальная арифметика ]] | * [[ Интервальная арифметика ]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
== Пересечение отрезков == | == Пересечение отрезков == | ||
* [[ Алгоритм Бентли-Оттмана ]] | * [[ Алгоритм Бентли-Оттмана ]] | ||
| + | * [[ Пересечение множества отрезков ]] | ||
* [[ Алгоритм Балабана ]] | * [[ Алгоритм Балабана ]] | ||
| − | |||
* [[ Snap rounding ]] | * [[ Snap rounding ]] | ||
* [[ Пересечение отрезков на сфере ]] | * [[ Пересечение отрезков на сфере ]] | ||
| Строка 29: | Строка 27: | ||
== Поиск == | == Поиск == | ||
| − | * [[ | + | * [[ К-d деревья и перечисление точек в произвольном прямоугольнике (статика) ]] |
| − | |||
* [[ Квадродеревья | Квадродерево, сжатое квадродерево ]] | * [[ Квадродеревья | Квадродерево, сжатое квадродерево ]] | ||
* [[ Skip quadtree: определение, время работы | Skip quadtree: определение, время работы, запрос точек в прямоугольнике ]] | * [[ Skip quadtree: определение, время работы | Skip quadtree: определение, время работы, запрос точек в прямоугольнике ]] | ||
| − | * [[ | + | * [[ Ортогональный поиск ]] |
* [[ Перечисление точек в произвольном прямоугольнике за 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
Основание вычислительной геометрии
Вычисление геометрических предикатов
Пересечение отрезков
Выпуклые оболочки
Поиск
- К-d деревья и перечисление точек в произвольном прямоугольнике (статика)
- Квадродерево, сжатое квадродерево
- Skip quadtree: определение, время работы, запрос точек в прямоугольнике
- Ортогональный поиск
- Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree)
- Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)
- Дерево интервалов (interval tree) и пересечение точки с множеством интервалов
- Пересечение прямоугольника с множеством прямоугольников (priority search tree)
- BSP-дерево
