Пересечение треугольников

Когда два треугольника на плоскости накладываются друг на друга, возникает область пересечения – многоугольник, состоящий из всех точек, принадлежащих обоим фигурам одновременно. Задача нахождения этой области и её площади критически важна в компьютерной графике, игровых движках, системах автоматизированного проектирования и геоинформационных системах.

Что такое пересечение треугольников

Пересечение двух треугольников – это геометрическая область, содержащая все точки, которые принадлежат одновременно обоим треугольникам. Результатом пересечения всегда является выпуклый многоугольник с количеством вершин от 0 до 6.

Возможные варианты пересечения:

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

Алгоритмы проверки пересечения треугольников

Тест разделяющей оси (SAT)

Тест разделяющей оси – самый быстрый способ проверить, пересекаются ли два выпуклых многоугольника. Для треугольников алгоритм работает за константное время O(1).

Принцип работы:

1. Для каждого треугольника возьмите 3 нормали к сторонам (всего 6 осей)
2. Спроецируйте оба треугольника на каждую ось
3. Если на какой-либо оси проекции не пересекаются – треугольники не пересекаются
4. Если проекции пересекаются на всех 6 осях – треугольники пересекаются

Формула проекции точки на ось:

proj = x · nx + y · ny

где (nx, ny) – единичный вектор нормали оси, (x, y) – координаты вершины.

Проверка перекрытия проекций:

overlap = min(max1, max2) - max(min1, min2)

Если overlap < 0 на любой оси – пересечения нет.

Метод барицентрических координат

Альтернативный способ проверки – использование барицентрических координат для определения, лежит ли точка внутри треугольника.

Точка P находится внутри треугольника ABC, если её барицентрические координаты (u, v, w) удовлетворяют условиям:

u ≥ 0, v ≥ 0, w ≥ 0, u + v + w = 1

где:

P = u·A + v·B + w·C

Этот метод удобен для проверки, принадлежит ли вершина одного треугольника другому.

Как найти точки пересечения сторон

Для вычисления точной площади пересечения необходимо найти все точки пересечения сторон треугольников.

Решение системы линейных уравнений

Каждая сторона треугольника задаётся уравнением прямой. Для сторон AB и CD:

Уравнение прямой через две точки:

(y - y1) / (y2 - y1) = (x - x1) / (x2 - x1)

В параметрической форме:

P(t) = A + t · (B - A), где 0 ≤ t ≤ 1

Точка пересечения двух прямых:

Для прямых:

• L1: P = A + t · (B - A)
• L2: Q = C + s · (D - C)

Решаем систему:

Ax + t · (Bx - Ax) = Cx + s · (Dx - Cx)
Ay + t · (By - Ay) = Cy + s · (Dy - Cy)

Решение:

t = ((Cx - Ax) · (Dy - Cy) - (Cy - Ay) · (Dx - Cx)) / ((Bx - Ax) · (Dy - Cy) - (By - Ay) · (Dx - Cx))

s = ((Cx - Ax) · (By - Ay) - (Cy - Ay) · (Bx - Ax)) / ((Bx - Ax) · (Dy - Cy) - (By - Ay) · (Dx - Cx))

Если 0 ≤ t ≤ 1 и 0 ≤ s ≤ 1 – отрезки пересекаются, точка пересечения:

X = Ax + t · (Bx - Ax)
Y = Ay + t · (By - Ay)

Проверка принадлежности отрезку

Найденная точка пересечения прямых может не лежать на отрезках. Обязательно проверяйте:

0 ≤ t ≤ 1 И 0 ≤ s ≤ 1

Только при выполнении этого условия точка является точкой пересечения сторон треугольников.

Алгоритм Сазерленда-Ходжмана для вычисления пересечения

Алгоритм Сазерленда-Ходжмана – стандартный метод отсечения многоугольника по выпуклому окну. Для пересечения треугольников один треугольник используется как окно отсечения для другого.

Пошаговый процесс:

1. Возьмите вершины первого треугольника как входной список
2. Для каждой стороны второго треугольника (рассматриваемой как отсекающая прямая):
   • Пройдите по всем вершинам текущего списка
   • Если вершина внутри – добавьте в выходной список
   • Если ребро пересекает границу – добавьте точку пересечения
3. Повторите для всех 3 сторон второго треугольника
4. Результирующий список вершин – многоугольник пересечения

Проверка «внутри» для стороны:

Для стороны AB и точки P используйте векторное произведение:

cross = (Bx - Ax) · (Py - Ay) - (By - Ay) · (Px - Ax)

Если cross ≥ 0 для всех сторон (при обходе против часовой стрелки) – точка внутри.

Расчёт площади пересечения треугольников

После нахождения всех вершин многоугольника пересечения площадь вычисляется по формуле гауссовых координат (формула шнуровки).

Формула площади многоугольника

Для многоугольника с вершинами (x₁, y₁), (x₂, y₂), …, (xₙ, yₙ):

S = 0.5 · |Σ(xi · yi+1 - xi+1 · yi)|

где сумма берётся по i от 1 до n, и xn+1 = x₁, yn+1 = y₁.

Развёрнутая форма для n вершин:

S = 0.5 · |(x1·y2 - x2·y1) + (x2·y3 - x3·y2) + ... + (xn·y1 - x1·yn)|

Пример расчёта

Даны треугольники:

• T1: A(0, 0), B(4, 0), C(0, 4)
• T2: D(2, 0), E(6, 0), F(2, 4)

Шаг 1: Находим точки пересечения сторон Шаг 2: Получаем вершины пересечения: (2, 0), (4, 0), (2, 2), (0, 4) – проверяем принадлежность Шаг 3: Применяем формулу площади

Для четырёхугольника с вершинами (2, 0), (4, 0), (2, 2), (0, 2):

S = 0.5 · |(2·0 - 4·0) + (4·2 - 2·0) + (2·2 - 0·2) + (0·0 - 2·2)|
S = 0.5 · |0 + 8 + 4 - 4| = 0.5 · 8 = 4

Площадь пересечения = 4 кв. ед.

Особые случаи пересечения

Полное вложение

Если все вершины одного треугольника лежат внутри другого, площадь пересечения равна площади меньшего треугольника.

Проверка:

Все 3 вершины T1 внутри T2 → S = площадь(T1)
Все 3 вершины T2 внутри T1 → S = площадь(T2)

Касание без перекрытия

Если треугольники имеют общую точку или сторону, но не пересекаются внутренними областями, площадь пересечения = 0.

Совпадающие стороны

При совпадении сторон пересечение образует многоугольник с вырожденными рёбрами. Обрабатывайте как обычное пересечение, площадь считается корректно.

Применение на практике

Компьютерная графика

В рендеринге пересечение треугольников используется для:

• Z-буферизации и определения видимости
• Тенирования и расчёта освещённых областей
• Текстурирования и наложения карт

Игровые движки

Обнаружение коллизий между объектами, представленными треугольными мешами:

• Физические взаимодействия
• Определение попаданий (hitscan)
• Оптимизация через иерархические структуры (BVH, octree)

ГИС и картография

Наложение полигональных слоёв:

• Расчёт перекрытия земельных участков
• Анализ зон покрытия
• Топологические операции

CAD-системы

Булевы операции над 3D-моделями:

• Пересечение объёмов
• Проверка конфликтов конструкций
• Расчёт материалов

Оптимизация вычислений

Для ускорения расчётов пересечения множества треугольников применяйте:

Пространственное разбиение:

• Квадродерево для 2D
• BVH (Bounding Volume Hierarchy) для 3D
• Сетка (uniform grid)

Отсечение на ранних этапах:

• Проверка по ограничивающим прямоугольникам (AABB)
• Проверка по описанным окружностям
• Быстрый отказ через SAT перед точным расчётом

Векторизация:

• SIMD-инструкции для параллельных вычислений
• GPU-ускорение для массовых проверок

Сравнение методов вычисления

Для большинства задач рекомендуется комбинация: SAT для быстрой проверки + Сазерленд-Ходжман для точного расчёта площади.

Примечание: Все формулы приведены для евклидовой плоскости. Для сферической геометрии или других метрик требуются модификации алгоритмов.