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

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

Существуют два общих алгоритма отсечения отрезков — алгоритм Коэна — Сазерленда и алгоритм Ляна – Барски.

Метод отсечения отрезков состоит из различных частей. Сначала осуществляются проверки на данном отрезке с целью определения, не лежит ли он вне видимой области. После этого вычисляются пересечения с одной или более границ.

Определение, какая часть прямой находится внутри или вне рассматриваемой области, осуществляется путём рассмотрения точек прямой по отношению к пересечениям.

Алгоритм Коэна — Сазерленда

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

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

Алгоритм Ляна – Барски

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

Алгоритм Кируса — Бека

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

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

Алгоритм Николл — Ли — Николла

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

Алгоритм быстрого отсечения

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

Алгоритм O(lg N)

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

Алгоритм Скалы

Алгоритм Скалы основан на однородных координатах и двойственности. Алгоритм может быть использован для отсечения прямой или отрезков для прямоугольного окна, а также для выпуклого многоугольника. Алгоритм основывается на классификации вершин отсекающего окна относительно полуплоскости, задаваемой прямой p : a x + b y + c = 0 {displaystyle p:ax+by+c=0} . Результат классификации определяет рёбра, пересекаемые прямой p. Алгоритм прост, легко реализуется и расширяется на выпуклые окна. Прямую или отрезок p можно вычислить из точек r1, r2, заданных в однородных координатах непосредственно, используя векторное произведение

p = r 1 × r 2 = ( x 1 , y 1 , w 1 ) × ( x 2 , y 2 , w 2 ) {displaystyle mathbf {p} =mathbf {r} _{1} imes mathbf {r} _{2}=(x_{1},y_{1},w_{1}) imes (x_{2},y_{2},w_{2})}

или

p = r 1 × r 2 = ( x 1 , y 1 , 1 ) × ( x 2 , y 2 , 1 ) {displaystyle mathbf {p} =mathbf {r} _{1} imes mathbf {r} _{2}=(x_{1},y_{1},1) imes (x_{2},y_{2},1)} .