2D-геометрия и отсечение
Растеризация отвечает на вопрос "какие пиксели закрасить". Эта статья — про геометрию до пикселей — где лежит точка относительно линии, попала ли мышь в полигон, какой кусок отрезка виден в окне. Те же идеи лежат в основе 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 для сеток.