Конспект раздела: вычислительная геометрия

Одна мысль на весь раздел

Почти всё в разделе решает одно число - поворот трёх точек (B − A) × (C − A) - и его родственник, определитель «точка в окружности». Алгоритмы отличаются тем, в каком порядке они задают эти вопросы: сортировка, заметающая прямая, случайная вставка, дерево разбиения. А правильность держится на том, что сами вопросы считаются точно.

ПРЕДИКАТЫ - ТОЧНО                   КОНСТРУКЦИИ - КАК УГОДНО
сторона точки от прямой             точка пересечения
пересекаются ли отрезки             центр окружности
внутри ли точка                     расстояние, площадь
точка в окружности                  координаты для рисования

Дерево решений

задача про точки и отрезки?
├── решение по одной тройке  → поворот в целых
├── «внутри ли»
│   ├── выпуклый             → двоичный поиск по вееру, log n
│   ├── любой многоугольник  → луч, полуоткрытое ребро, n
│   └── много запросов       → локализация: полосы, трапеции
├── оболочка                 → Эндрю n log n; Чан n log h
│   └── на ней               → калиперы h; точка внутри log h
├── пересечения отрезков
│   ├── есть ли              → Шамос-Хой n log n
│   └── все                  → Бентли-Оттман (n + k) log n
├── «кто ближе»
│   ├── малая размерность    → kd-дерево
│   ├── всё разбиение        → Вороной, Форчун n log n
│   └── большая размерность  → приближённые: LSH, HNSW
├── треугольники
│   ├── по точкам            → Делоне: перевороты, вставка
│   └── по многоугольнику    → уши n²; монотонные n log n
├── точки в прямоугольнике
│   ├── равномерные данные   → сетка
│   ├── статичные            → дерево диапазонов log² n
│   └── изменяются           → kd-дерево, R-дерево
└── порядок отрисовки        → BSP, обход сзади вперёд

Как части связаны

поворот ─► пересечение отрезков ─► простой ли многоугольник
   │              └─► заметающая прямая ─► Бентли-Оттман
   │                        │                   └─► наложение карт
   │                        └─► Форчун: статус - береговая линия
   ├─► оболочка ◄─ парабола ◄─ сортировка: граница n log n
   │      └─► на параболоиде: нижняя оболочка = Делоне ◄─► Вороной
   │                         └─► остовное дерево внутри Делоне
   ├─► уши ─► триангуляция ─► три цвета ─► галерея
   └─► двойственность: огибающая прямых = оболочка точек (m, c)

случайный порядок: окружность O(n), Делоне O(n log n),
                   трапецоидная карта, BSP O(n log n) кусков

Числа раздела, которые стоит помнить

поворот: |значение| <= 8M²; float точен до M = 2^25, int64 - до 2^30
сетка у y = x с шагом 2^-53: 114 неверных знаков float из 256
оболочка: Джарвис n · h, Эндрю 2n − 4 поворота на параболе
случайные точки: h ~ (8/3) ln n в квадрате, ~ n^(1/3) в круге
триангуляция точек: 2n − 2 − h треугольников, 3n − 3 − h рёбер
Вороной: вершин <= 2n − 5 (ровно 2n − 2 − h в общем положении)
многоугольник: n − 2 треугольника; галерея ⌊n/3⌋, прямоугольная ⌊n/4⌋
kd-дерево: прямоугольник √n + k; в восьмимерии ближайший - 2/3 узлов
дерево диапазонов: log² n + k запрос, n (log n + 1) памяти
квадродерево: глубина <= log₂(S / c) + 1,5

Границы, общие для всех результатов

Почти все оценки сформулированы для общего положения: никаких трёх точек на прямой и четырёх на окружности, разные x у событий. Реальные данные этому не подчиняются, и правильная реализация не запрещает вырожденные случаи, а обрабатывает их - договором о порядке равных событий и точными предикатами. Нижние границы n · log n живут в модели «решения сравнениями и знаками многочленов»: маленькие целые координаты и малое число вершин их обходят. Приближённые оценки времени для случайных алгоритмов - про ожидание, а не про каждый запуск.

Ловушки джокера

Решение по float. Знак поворота около прямой - шум, определитель окружности - тем более.

eps вместо точности. Отношение «почти на прямой» не транзитивно, и ответ зависит от порядка обхода.

Края пересечений. Т-образное касание, общий конец, наложение, луч через вершину.

Обход не в ту сторону. Площадь со знаком минус и все проверки «выпуклый угол» вывернуты.

Вход как пришёл. Отсортированный вход - худший порядок для инкрементных алгоритмов.

Структура не по данным. Сетка на скоплениях, kd-дерево в больших размерностях, дерево диапазонов на изменяющихся данных.

Сортировка там, где нужен разрез. Стены, заслоняющие друг друга по кругу, не упорядочить - их режут.

От набора точек к карте и маршруту

Задача	Инструмент	Условие или граница
Связная карта областей	DCEL и наложение	Храни ориентированные полурёбра и компоненты границ.
Оболочка в пространстве	Горизонт и граф конфликтов	Ожидаемое O(n log n) требует случайного порядка и локального обновления конфликтов.
Наихудшее расстояние	Дальняя диаграмма Вороного	У охватывающего круга возможны два опорных пункта, не только три.
Диапазонный запрос	PST и дерево разбиения	Три стороны дают O(log n+k); у простого симплексного дерева сохраняй ε в показателе.
Путь робота	Граф видимости	Для переносимой без вращения формы используй P+(-R) и явную модель столкновения.

Проверь, что можешь объяснить

Почему почти всё в разделе сводится к повороту и определителю окружности - и почему их надо считать точно, а точки пересечения можно и в float? Почему оболочка не дешевле сортировки и как это обходят? Что держит в статусе заметающая прямая в задачах о пересечениях и в алгоритме Форчуна? Как связаны Вороной, Делоне и оболочка на параболоиде? Почему у многоугольника есть уши и откуда ⌊n/3⌋ охранников? Как выбрать между сеткой, квадродеревом, kd-деревом и деревом диапазонов? Почему обход BSP-дерева рисует сцену правильно для любой точки зрения?