Геометрия
Геометрия в Computer Science
Graham scan, Delaunay triangulation, ray casting-это не академические алгоритмы, а ежедневные инструменты: геозоны в Uber, mesh generation в Blender, навигационные карты в играх. LeetCode Hard: задачи на convex hull регулярно встречаются в FAANG-интервью.
- **Geofencing:** point-in-polygon для определения зоны доставки или парковки
- **Навигация в играх:** Delaunay triangulation для построения navigation mesh
- **Spatial indexing:** R-tree на основе bounding rectangles регионов Вороного
- **FEM/3D-печать:** Delaunay mesh для конечно-элементного анализа
Предварительные знания
CCW-тест и пересечение отрезков
CCW (counter-clockwise) тест-базовый примитив вычислительной геометрии: определяет ориентацию тройки точек. На нём строятся почти все алгоритмы.
**CCW(A, B, C)** = знак cross product (B−A)×(C−A): > 0-против часовой стрелки (CCW) = 0-коллинеарны < 0-по часовой стрелке (CW) **Пересечение отрезков AB и CD:** пересекаются ⟺ CCW(A,B,C) ≠ CCW(A,B,D) И CCW(C,D,A) ≠ CCW(C,D,B)
CCW(A=(0,0), B=(1,0), C=(0,1)) = ?
Алгоритмы выпуклой оболочки
Выпуклая оболочка-наименьший выпуклый многоугольник, содержащий все точки. Алгоритм Грэхема (Graham scan)-классическое O(n log n) решение.
**Graham scan O(n log n):** 1. Выбрать самую нижнюю (левую) точку P₀ 2. Отсортировать остальные по полярному углу относительно P₀ 3. Обойти точки, добавляя в стек: если при добавлении следующей точки нет левого поворота-удалять из стека **Jarvis march O(nh):** по одной точке, всегда выбирая самый правый поворот.
Сложность алгоритма Грэхема для n точек:
Точка в полигоне
Проверка, лежит ли точка внутри произвольного многоугольника-классическая задача вычислительной геометрии с двумя основными алгоритмами.
**Ray casting:** пускаем луч из точки вправо, считаем пересечения со сторонами. Чётное число-снаружи, нечётное-внутри. **Winding number:** считаем, сколько раз полигон "обматывается" вокруг точки. 0-снаружи, ≠0-внутри. Winding number корректен для самопересекающихся полигонов; ray casting-проще.
Ray casting пустил луч из точки P, луч пересёк 3 стороны полигона. Точка P:
Диаграмма Вороного и триангуляция Делоне
Диаграмма Вороного разбивает плоскость на ячейки по принципу: каждая ячейка содержит точки, ближайшие к данному узлу. Триангуляция Делоне-двойственная структура.
**Диаграмма Вороного:** - Ячейка узла p: {x : d(x,p) ≤ d(x,q) для всех q} - Алгоритм Fortune: O(n log n) **Триангуляция Делоне:** - Каждый описывающий круг треугольника не содержит других точек - Максимизирует минимальный угол-"наилучшая" триангуляция **Связь:** Делоне-двойственный граф к Вороному.
Триангуляция Делоне максимизирует:
Ключевые идеи
- **CCW test:** знак cross product-основной примитив всех геометрических алгоритмов
- **Graham scan O(n log n):** sort by angle → stack с удалением правых поворотов
- **Point-in-polygon:** ray casting (нечётные пересечения) или winding number
- **Делоне/Вороной:** O(n log n); Делоне = лучший mesh, Вороной = nearest neighbor
Связанные темы
Вычислительная геометрия объединяет все предыдущие темы:
- Векторная геометрия — CCW test = знак cross product двух рёберных векторов
- Площади и периметры — Shoelace formula-примитив для ориентации и площади
- Геометрия на собеседовании — Convex hull, closest pair, max rectangle-классика интервью
Вопросы для размышления
- Почему алгоритм Fortune для диаграммы Вороного O(n log n), а не O(n²)?
- Как winding number обрабатывает самопересекающиеся полигоны правильно, а ray casting-нет?
- Как построить k-d tree на основе точек и чем он отличается от R-tree для пространственных запросов?