Отсечение отрезков

Алгоритм Коэна — Сазерленда (назван именами Дэнни Коэна и Ивана Сазерленда) — это алгоритм отсечения прямой. Алгоритм делит двумерное пространство на 9 областей, из которых только средняя часть видима.

В 1967 году работа по моделированию полёта Дэнни Коэна привела к развитию алгоритмов отсечения отрезков для двухмерной и трёхмерной компьютерной графики, созданных совместно с Иваном Сазерлендом.

Алгоритм Ляна – Барски использует параметрическое уравнение прямой и неравенства, описывающие области отсекающего блока для определения пересечения прямой и отсекающего блока. С этими пересечениями становится ясно, какую часть прямой следует отрисовывать. Алгоритм существенно эффективнее алгоритма Коэна — Сазерленда, но алгоритм Коэна — Сазерленда делает тривиальные принятия или отвержения быстрее, так что его имеет смысл использовать, если бо́льшая часть прямых и отрезков следует полностью удалить из окна отсечения.

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

Алгоритм Кируса — Бека в основном предназначен для отсечения прямой в параметрическом виде относительно выпуклого многоугольника в двумерном пространстве или выпуклого многогранника в трёхмерном пространстве[2].

Алгоритм Алгоритм Николл — Ли — Николла (Тина М. Николл, Робин А. Николл) является алгоритмом быстрого отсечения отрезков, который сокращает шанс отсечения отрезка несколько раз, что может происходить в алгоритме Коэна — Сазерленда. Отсекающее окно делится на несколько различных областей, зависящих от позиции начальной точки прямой, требующей отсечения.

Этот алгоритм похож на алгоритм Коэна — Сазерленда. Начальная и конечная позиции классифицируются по тому, в какой порции из 9 областей они находятся. Большой оператор-переключатель переключает в специальный обработчик для каждого отдельного случая. В отличие от этого алгоритма, алгоритм Коэна — Сазерленда может отрабатывать несколько раз один и тот же случай[3].

Алгоритм классифицирует вершины по прямой, заданной в явном виде p: ax + by + c = 0. Так как многоугольник предполагается выпуклым, а вершины упорядочены по часовой стрелке или против часовой стрелки, можно применить двоичный поиск, приводящий к сложности O(lg N)[4].

Алгоритм Ска́лы основан на однородных координатах и двойственности[5]. Алгоритм может быть использован для отсечения прямой или отрезков для прямоугольного окна, а также для выпуклого многоугольника. Алгоритм основывается на классификации вершин отсекающего окна относительно полуплоскости, задаваемой прямой ${\displaystyle p:ax+by+c=0}$. Результат классификации определяет рёбра, пересекаемые прямой p. Алгоритм прост, легко реализуется и расширяется на выпуклые окна. Прямую или отрезок p можно вычислить из точек r₁, r₂, заданных в однородных координатах непосредственно, используя векторное произведение

${\displaystyle \mathbf {p} =\mathbf {r} _{1}\times \mathbf {r} _{2}=(x_{1},y_{1},w_{1})\times (x_{2},y_{2},w_{2})}$

или

${\displaystyle \mathbf {p} =\mathbf {r} _{1}\times \mathbf {r} _{2}=(x_{1},y_{1},1)\times (x_{2},y_{2},1)}$.

• Отсечение