2D-геометрия и отсечение

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Программистам CG

Растеризация отвечает на вопрос «какие пиксели закрасить». Эта статья — про геометрию до пикселей: где лежит точка относительно линии, попала ли мышь в полигон, какой кусок отрезка виден в окне. Те же идеи лежат в основе UI hit-test, 2D-игр, GIS и CAD.

Маршрут

Координаты и матрицы — векторная графика. Отрисовка линий и заливка — растеризация. 3D-аналоги (луч–треугольник, frustum) — пространственные структуры и 3D.

---

2D-геометрия и отсечение

Прямая, отрезок и классификация точек

Прямую на плоскости задают уравнением ax + by + c = 0 или параметрически P(t) = A + t(B − A). Для отрезка параметр t ограничен отрезком [0, 1].

★ Ориентированная плоскость (в 2D — прямая с выбором «левая/правая» полуплоскость) — знак выражения ax + by + c в точке говорит, с какой стороны она лежит. Так проверяют попадание в выпуклый многоугольник и строят отсечение.

★ Барицентрические координаты — представление точки внутри треугольника как взвешенной суммы вершин; все три веса неотрицательны ⟺ точка внутри. Удобно для интерполяции атрибутов и hit-test треугольника.

---

Пересечения

Задача	Идея
Две прямые	Решить систему линейных уравнений; параллельность ⟺ нулевой знаменатель
Два отрезка	Найти пересечение прямых, проверить t ∈ [0,1] на обоих
Луч–отрезок	Ограничить t ≥ 0 на луче
Точка в многоугольнике	Even-odd — число пересечений луча чётное/нечётное; non-zero winding — сумма оборотов контура

Выпуклая оболочка (convex hull) — минимальный выпуклый контур вокруг набора точек. Классический алгоритм Грэхема сортирует точки по полярному углу относительно нижней и обходит стеком, удаляя «внутренние» вершины.

Триангуляция Делоне и диаграмма Вороного — dual-друг-другу структуры: Delaunay максимизирует минимальный угол треугольников; Voronoi делит плоскость на зоны ближайшего сайта. Применяются в сетках, интерполяции, игровой карте.

---

Отсечение по окну и выпуклому контуру

Перед растеризацией рисуют только то, что попадает в окно просмотра (viewport) — прямоугольник или, в 3D, усечённую пирамиду (view frustum).

Алгоритм Лянга–Барского (отрезок vs AABB окна)

Для отрезка и осевого прямоугольника окна параметр t ∈ [0,1] режется пересечениями с четырьмя границами. Вычисляют p и q для каждой грани; если есть p = 0 и q < 0 — отрезок параллелен снаружи; иначе обновляют t_enter, t_leave. Если t_enter ≤ t_leave — видимая часть есть.

Алгоритм Цируса–Бека (отрезок vs выпуклый многоугольник)

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

Сазерленд–Ходжман (многоугольник vs выпуклое окно)

Исходный многоугольник последовательно обрезают каждой границей окна: на каждом шаге строят новый контур из пересечений рёбер с границей. Работает для произвольных (в т.ч. невыпуклых) входных полигонов при выпуклом окне.

---

Практика

• Canvas / SVG — hit-test и clipping делает движок; понимание алгоритмов помогает при кастомных редакторах и WebGL-оверлеях.
• Игры 2D — AABB спрайтов, отсечение по тайловой карте, spatial hash.
• Карты — point-in-polygon для клика по региону; Delaunay/Voronoi для сеток.

---