Операции над полигонами

Фреза ЧПУ прокладывает маршрут вокруг детали - но как убедиться, что инструмент диаметром 6 мм не заедет туда, куда не должен? Как Photoshop за миллисекунды вычисляет объединение сотни слоёв? Как игровой движок мгновенно определяет, врезался ли персонаж в стену? Все эти задачи решаются пятью фундаментальными операциями над полигонами.

• **CNC machining:** toolpath генерируется как смещение контура детали внутрь на радиус фрезы; неправильное смещение - брак или поломка инструмента.
• **PCB routing (KiCad, Altium):** зоны запрета трассировки строятся как сумма Минковского проводников и минимального зазора (clearance); булевы операции объединяют медные полигоны.
• **Физические движки (Bullet, Box2D):** GJK использует сумму Минковского неявно - collision detection за O(n) без явного построения суммы.

Булевы операции над полигонами

Фотошоп объединяет слои, AutoCAD вычитает отверстие из детали, игровой движок вычисляет видимую область карты - все эти операции сводятся к четырём булевым операциям над полигонами: объединению (union), пересечению (intersection), разности (difference) и симметрической разности (XOR). Общая идея: вычислить точки пересечения рёбер двух полигонов, разметить рёбра как «внутренние» или «внешние», обойти контур результата.

Сложность: O((n+m+k) log(n+m)), где k - число пересечений рёбер (до O(nm) в худшем случае). Реализации: Clipper2 (C++/Python), CGAL Polygon_set_2, Shapely (Python, использует GEOS). Сложность реализации высока из-за вырожденных случаев: совпадающие рёбра, вершины на рёбрах, самопересечения.

**Правило заполнения (fill rule):** для полигонов с отверстиями важно отличать «внутри» от «снаружи». Even-odd rule: луч из точки пересекает контур чётное число раз - снаружи; нечётное - внутри. Non-zero winding rule: считает знаковое число пересечений (с учётом направления обхода). Большинство современных движков используют non-zero.

Алгоритм Sutherland-Hodgman

Алгоритм Sutherland-Hodgman (1974) решает специальную задачу: обрезать произвольный полигон по выпуклому прямоугольнику (или любому выпуклому полигону). Это базовая операция в растеризации 3D-графики: клипинг треугольника по frustum перед проекцией. Ключевая идея: обрезать по одной полуплоскости за раз.

Сложность: O(n·m), где n - вершины subject-полигона, m - вершины clip-полигона. Для прямоугольника m = 4, значит O(4n) = O(n). Результат всегда выпуклый при выпуклом clip-полигоне. Для невыпуклого clip-полигона Sutherland-Hodgman даёт неверный результат - нужен Weiler-Atherton или общий булев алгоритм.

**4 случая пересечения ребра с полуплоскостью:** оба внутри (добавить current), оба снаружи (ничего), зашли (добавить пересечение + current), вышли (добавить только пересечение). Это полное перечисление - другие случаи невозможны.

Смещение полигонов (Polygon Offsetting)

Инструмент ЧПУ (CNC) диаметром 6 мм не может пройти точно по контуру детали - он сдвигается на 3 мм (радиус фрезы). Так возникает задача смещения полигона: сдвинуть каждое ребро на расстояние d по нормали, пересечь сдвинутые рёбра. Простая идея скрывает серьёзные сложности.

При смещении вогнутого полигона внутрь может возникнуть несколько несвязных частей или вырожденные петли - самопересечения нужно удалять через булеву операцию. Библиотека Clipper2 реализует «правильное» смещение: она вычисляет offset и автоматически убирает самопересечения через union.

**Применения:** CNC toolpath (смещение внутрь на радиус фрезы), PCB routing (clearance zone вокруг проводников), robot motion planning (расширение препятствий на радиус робота), архитектурное проектирование (setback lines от границ участка).

Сумма Минковского и обнаружение коллизий

Объект A движется по плоскости и не должен столкнуться с препятствием B. Вместо проверки «пересекаются ли A и B» для каждой позиции - вычислить один раз **конфигурационное пространство препятствия (C-obstacle)** = A ⊕ (-B). Тогда A не пересекает B тогда и только тогда, когда центр A не лежит в C-obstacle.

Связь со смещением полигонов: смещение полигона P на расстояние d = сумма Минковского P ⊕ B(0, d), где B(0, d) - круг радиуса d. Именно поэтому углы при смещении получают дуговые скругления: дуга - это вклад кругового диска.

**Обнаружение коллизий в игровых движках:** вместо полной суммы Минковского используется GJK (Gilbert-Johnson-Keerthi) алгоритм, который проверяет, содержит ли сумма Минковского A ⊕ (-B) начало координат (= пересекаются ли A и B) за O(n+m) шагов без явного построения суммы.

Ключевые идеи

• **Булевы операции (union/intersection/difference):** sweep line O((n+m+k) log n); ключевые примитивы: пересечение рёбер + классификация inside/outside по правилу заполнения.
• **Sutherland-Hodgman:** O(n·m) клипинг по выпуклому полигону; 4 случая per ребро; корректен только для выпуклых clip-полигонов.
• **Polygon offsetting:** сдвиг рёбер по нормали + удаление самопересечений через union; применяется в CNC, PCB, motion planning.
• **Сумма Минковского:** A ⊕ B = {a+b}; для выпуклых O(n+m); C-obstacle для планирования пути = obstacle ⊕ (-robot); GJK проверяет коллизию без явного построения.

Связанные темы

Операции над полигонами используют и порождают другие геометрические алгоритмы:

• Sweep line алгоритмы — Булевы операции реализуются через sweep line; те же идеи используются в алгоритмах пересечения отрезков
• Motion planning и конфигурационные пространства — C-obstacle через сумму Минковского - основа геометрического планирования движения роботов

Вопросы для размышления

• Смещение полигона наружу на d эквивалентно сумме Минковского с диском радиуса d. Как изменится форма смещённого полигона, если вместо диска использовать квадрат? Где это может быть полезно?
• GJK проверяет коллизию за O(n+m), не строя явно сумму Минковского. Какое свойство суммы Минковского (коллизия ↔ начало координат внутри A⊕(-B)) делает это возможным?
• Для невыпуклых полигонов сумма Минковского имеет O(n²m²) сложность - экспоненциальный взрыв. Как современные игровые движки справляются с невыпуклыми объектами на практике?

Связанные уроки

• alg-01-big-o