Вычислительная геометрия
Точки, отрезки, полигоны
Tesla Full Self-Driving обрабатывает LiDAR-облако из 100 000 точек 10 раз в секунду. Из этого хаоса за 100 мс вырастает выпуклая оболочка вокруг каждого препятствия - и автомобиль решает: объехать или затормозить. Основа - тот же cross product, который Гаусс использовал для вычисления площади земельных участков в 1795 году. Три примитива: точка, отрезок, полигон. Из них строится всё.
- **Unity/Unreal (GJK algorithm):** collision detection между хитбоксами - алгоритм Гилберта-Джонсона-Кирти использует выпуклые полигоны и cross product; работает десятки тысяч раз в кадр
- **SLAM в автономных машинах:** LiDAR-точки → выпуклые оболочки препятствий → маршрут в реальном времени; Tesla FSD, Waymo, робот Boston Dynamics
- **GPS trilateration:** пересечение трёх сфер (три отрезка в проекции) - базовый геометрический примитив в каждом смартфоне
- **AlphaFold2 (DeepMind):** предсказание структуры белка - задача вычислительной геометрии в 3D пространстве координат атомов
Точки и расстояния
**GPS-триангуляция** - это пересечение трёх сфер в трёхмерном пространстве, спроецированное в задачу на плоскости. Физический движок Unreal Engine - это collision detection между выпуклыми многогранниками, 60 раз в секунду. AlphaFold2 от DeepMind - предсказание 3D-координат атомов белка. Всё начинается с самого простого объекта - **точки** на плоскости и пары чисел (x, y).
**Точка** на плоскости - пара координат (x, y) ∈ R². Основные операции: расстояние между точками, вектор из одной точки в другую, проверка ориентации тройки точек.
**Cross product** (векторное произведение) - главный инструмент вычислительной геометрии. Для двух 2D-векторов u = (ux, uy) и v = (vx, vy): u × v = ux·vy - uy·vx. Результат - скаляр, знак которого показывает **ориентацию**. GJK-алгоритм в Unity и Unreal вызывает именно это вычисление тысячи раз в кадр при проверке столкновений.
| Cross product | Знак | Ориентация | Визуально |
|---|---|---|---|
| u × v > 0 | Положительный | CCW (против часовой) | r слева от p→q |
| u × v < 0 | Отрицательный | CW (по часовой) | r справа от p→q |
| u × v = 0 | Ноль | Коллинеарны | p, q, r на одной прямой |
Для точек P(0,0), Q(1,0), R(0,1): чему равен cross product (Q-P) × (R-P)?
Пересечение отрезков
Два отрезка на плоскости - пересекаются ли они? Задача кажется простой, но дьявол в деталях: коллинеарные отрезки, общие концы, касание в точке. Именно эти edge cases ломают наивные реализации в игровых движках и приводят к тому, что персонаж «проваливается» сквозь стену на высоком FPS. **Cross product** снова главный инструмент.
**Отрезок** AB пересекает отрезок CD, если точки C и D лежат по разные стороны от прямой AB, **и** точки A и B лежат по разные стороны от прямой CD. Проверка «по разные стороны» - через знак cross product.
**Вещественная арифметика ненадёжна!** Сравнение cross product с нулём через `==` может дать ошибку из-за floating point. В production-коде используют epsilon-сравнения или целочисленную арифметику.
Алгоритм работает за O(1) - константное время для одной пары отрезков. Но для n отрезков наивная проверка всех пар - O(n²). Как сделать лучше - узнаем в уроке про sweep line.
Два отрезка лежат на одной прямой и частично перекрываются. Какой из 4 orientation-тестов НЕ обнаружит пересечение?
Полигоны и формула шнурка
Участок земли, контур здания на карте, хитбокс персонажа в игре, предсказанный контур белка из AlphaFold2 - всё это **полигоны**. Как представить полигон в коде и вычислить его площадь за один проход?
**Простой полигон** - замкнутая ломаная без самопересечений. Представляется как упорядоченный список вершин (v₁, v₂, ..., vₙ). Рёбра: v₁v₂, v₂v₃, ..., vₙv₁.
Почему «формула шнурка»? Если выписать координаты в два столбца и соединить их крест-накрест - получается рисунок, напоминающий шнуровку ботинка.
| Операция | Сложность | Алгоритм |
|---|---|---|
| Площадь полигона | O(n) | Формула шнурка |
| Точка внутри полигона | O(n) | Ray casting |
| Периметр полигона | O(n) | Сумма длин рёбер |
| Триангуляция | O(n log n) | Ear clipping / Monotone |
Формула шнурка для полигона с вершинами (0,0), (2,0), (2,2), (0,2) даёт площадь:
Выпуклость полигонов
Натяните резиновую ленту вокруг набора гвоздей на доске. Форма ленты - **выпуклый полигон**. Все вершины снаружи, ни одна не вдавлена. Tesla FSD строит выпуклую оболочку вокруг каждого распознанного автомобиля и пешехода - именно потому, что для выпуклых работает O(log n) вместо O(n), а у машины нет времени ждать.
**Выпуклый полигон** - полигон, в котором отрезок, соединяющий любые две точки внутри, полностью лежит внутри полигона. Эквивалентно: все внутренние углы < 180°, или все последовательные тройки вершин имеют одинаковую ориентацию.
| Операция | Выпуклый полигон | Произвольный полигон |
|---|---|---|
| Точка внутри? | O(log n) - бинарный поиск | O(n) - ray casting |
| Пересечение двух полигонов | O(n + m) | O(n·m) в общем случае |
| Минимальное расстояние | O(log n) - rotating calipers | O(n) или O(n log n) |
| Площадь | O(n) - формула шнурка | O(n) - формула шнурка |
Выпуклость даёт алгоритмические преимущества: бинарный поиск по углам, метод вращающихся штангенциркулей (rotating calipers), быстрое пересечение. SLAM-системы в роботах Boston Dynamics и автопилоте Waymo строят выпуклые оболочки препятствий именно для скорости - следующий урок об этом.
Три примитива из начала урока - точка, отрезок, полигон - фундамент всего. Cross product - универсальный инструмент ориентации, работающий в GJK collision detection, GPS-триангуляции и SLAM-системах. Формула шнурка превращает координаты в площадь за один проход - Гаусс придумал в 1795, ГИС-системы используют сейчас.
Проверка пересечения отрезков - это простая задача, достаточно решить систему уравнений прямых
Пересечение отрезков полно edge cases: коллинеарные, перекрывающиеся, касающиеся в точке, с общими концами. Каждый случай требует отдельной ветки, а float-арифметика добавляет проблемы точности
Система уравнений для прямых не учитывает, что отрезки - ОГРАНИЧЕННЫЕ части прямых: нужно проверять, что точка пересечения лежит на обоих. Коллинеарные дают вырожденную систему (0/0) - отдельная логика. Именно из-за этих edge cases в реальных физических движках (Bullet, PhysX) проверка пересечения - несколько десятков строк кода, а не три.
Полигон с вершинами (0,0), (4,0), (4,3), (2,1), (0,3) - выпуклый?
Ключевые идеи
- **Cross product** u × v = ux·vy - uy·vx - один скаляр, три случая: CCW / CW / коллинеарно. Основа GJK collision detection в Unity/Unreal
- **Пересечение отрезков** - 4 orientation-теста для общего случая плюс отдельная ветка для коллинеарных; вещественная арифметика требует epsilon-сравнений
- **Формула шнурка** - площадь полигона за O(n) по координатам вершин; та же математика в ГИС-системах для кадастрового учёта
- **Выпуклые полигоны** - O(log n) point-in-polygon против O(n); SLAM-системы строят выпуклые оболочки препятствий именно для этой скорости
Связанные темы
Базовые примитивы - фундамент для всех алгоритмов вычислительной геометрии:
- Выпуклая оболочка — Использует ориентацию и cross product для построения минимального выпуклого полигона
- Пересечения отрезков (sweep line) — Эффективный поиск пересечений среди n отрезков - развитие темы пересечения
- Линейная алгебра для графики — Векторы, cross/dot product - общий математический фундамент
Вопросы для размышления
- Почему cross product важнее dot product в вычислительной геометрии? В каких именно задачах dot product незаменим (например, в освещении в шейдерах)?
- Формула шнурка для полигона с дыркой (кольцо): как адаптировать алгоритм, чтобы дырка вычиталась из площади?
- float-арифметика вносит ошибки при сравнении с нулём (epsilon). Как GJK-алгоритм в Unity справляется с этим в production-коде?
Связанные уроки
- alg-01-big-o — Геометрические алгоритмы анализируются теми же инструментами: O-нотация, worst/average case
- ds-01-arrays — Пространственные структуры (k-d tree, segment tree) хранят геометрические объекты для быстрых запросов
- la-01-vectors-intro — Векторное произведение для ориентации точек, скалярное для проекций - везде нужна линейная алгебра
- cgeom-02 — Базовые примитивы (точки, отрезки) - строительные блоки выпуклых оболочек и триангуляции Делоне
- la-04-lines-planes