Вычислительная геометрия
Версия от 09:09, 20 февраля 2015; Mcquay (обсуждение | вклад) (→Вычисление геометрических предикатов)
Основание вычислительной геометрии
Вычисление геометрических предикатов
- Вычисление погрешности арифметического выражения на примере ориентации трех точек
- Adaptive precision arithmetic
- ESSA
- Интервальная арифметика
- Рациональная арифметика
Пересечение отрезков
Выпуклые оболочки
Поиск
- Ортогональный поиск
- Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)
- Квадродерево, сжатое квадродерево
- Skip quadtree: определение, время работы, запрос точек в прямоугольнике
- К-d деревья и перечисление точек в произвольном прямоугольнике (статика)
- Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree)
- Дерево интервалов (interval tree) и пересечение точки с множеством интервалов
- Пересечение прямоугольника с множеством прямоугольников (priority search tree)
- BSP-дерево
