Вычислительная геометрия — различия между версиями
Shersh (обсуждение | вклад) (→Организационные вопросы: добавлены орг. вопросы для year2013) |
м (rollbackEdits.php mass rollback) |
||
(не показано 5 промежуточных версий 4 участников) | |||
Строка 1: | Строка 1: | ||
== Основание вычислительной геометрии == | == Основание вычислительной геометрии == | ||
* [[ Аффинное пространство ]] | * [[ Аффинное пространство ]] | ||
− | * [[ | + | * [[ Объем ]] |
* [[ Скалярное произведение и метрика ]] | * [[ Скалярное произведение и метрика ]] | ||
* [[ Однородные координаты ]] | * [[ Однородные координаты ]] | ||
+ | * [[ Двойственное пространство ]] | ||
== Вычисление геометрических предикатов == | == Вычисление геометрических предикатов == | ||
Строка 53: | Строка 54: | ||
== Триангуляция Делоне и диаграмма Вороного == | == Триангуляция Делоне и диаграмма Вороного == | ||
* [[ Триангуляция Делоне ]] | * [[ Триангуляция Делоне ]] | ||
+ | * [[ Триангуляция Делоне на сфере ]] | ||
* [[ Диаграмма Вороного ]] | * [[ Диаграмма Вороного ]] | ||
* [[ Motorcycle graph ]] | * [[ Motorcycle graph ]] |
Текущая версия на 19:23, 4 сентября 2022
Основание вычислительной геометрии
Вычисление геометрических предикатов
Пересечение отрезков
Выпуклые оболочки
Поиск
- К-d деревья и перечисление точек в произвольном прямоугольнике (статика)
- Квадродерево, сжатое квадродерево
- Skip quadtree: определение, время работы, запрос точек в прямоугольнике
- Ортогональный поиск
- Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree)
- Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)
- Дерево интервалов (interval tree) и пересечение точки с множеством интервалов
- Пересечение прямоугольника с множеством прямоугольников (priority search tree)
- BSP-дерево