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

Можно рассмотреть теперь, как выполнить анализ принадлежности отрезка видовой области или его части.

Эта задача решена в алгоритме Коэна-Сазерленда.

Когда решается задача отсечения отрезка или линии, то считают - точка линии, лежащая на границе окна, принадлежит окну. Точки, лежащие внутри отсекающего окна, должны удовлетворять условию

x_л ≤ x ≤ x_пр или x_min x_max

y_{н в} y_min y_max

Пространство разбивается на 9 областей. Область в центре – экранная область вывода изображения. Каждая подобласть кодируется бинарным 4-х битным кодом, в₀ в₁ в₂ в₃ (или с₁с₂с₃с₄ – обозначить их можно как угодно).

Для каждого отрезка определяют коды концов (К1, К2). Образование 4-х битного КОДА ясно из рисунка. 4-х битный код присваивается каждой конечной точке отрезка. Если конечная точка лежит ...

то соответствующему коду присваивается значение равное 1.

Иначе биту присваивают нулевое значение.

Машинный анализ кодов посредством побитовых бинарных операций дает три возможных результата.

1. Отрезок выводится целиком: коды P1 и P2 концов отрезка равны 0000 – (Код Р1) ИЛИ (Код Р2) = 0000. Здесь ИЛИ – бинарная операция.

2. Отрезок отбрасывается без вычислений: оба конца отрезка находятся выше, ниже, правее или левее окна вывода. Соответствующие биты в кодах равны 1: (Код P1) И (Код P2) = ...

Здесь символ И – бинарная операция логического умножения.

3. Отрезок нельзя принять и нельзя отбросить. Результат бинарной операции ИЛИ равен 0000: Потребуется определить ту его часть, которая находиться за границей окна и отсечь ее, либо отсекать по частям до тех пор, пока коды концов не укажут на один из тривиальных случаев (см. п. 2) нахождения отрезка целиком за пределами окна.

Пример 1. Анализ положения отрезков

На рис. ниже приведен анализ положения отрезков для отсечения их прямоугольным окном вывода. Требуется принять решение о месте нахождения отрезков и отделить те из них, для которых потребуется дополнительный анализ и проверка.

Для каждого отрезка определяют коды концов (К1, К2). По найденным кодам выполняется экспресс-анализ (побитовый опрос И и ИЛИ):

- Если К1 и К2 0, отрезок лежит вне поля вывода и отбрасывается (и – бинарная операция).

- Если К1 или К2 = 0, отрезок полностью лежит внутри поля вывода, отсечение не нужно и отрезок полностью прорисовывается.

- Если К1 и К2 =0, отрезок частично лежит внутри поля вывода, необходимо его отсечение по полю вывода, или требуется дополнительная проверка на невидимость отрезка.

D

Пример 2. Отсечение отрезка (рис ниже)

Задан отрезок Р₁Р₂.

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

Cod (P₁) = 1010; Cod (P₂) = 0101

Перенесём точку P₁ в точку R (X = X_min). Cod (R) = 0010. Отрезок P₁R можно отсечь, т.к. побитовая бинарная операция дала результат

1010 1010

и 0101

0010 0000

0010, т.е. эта часть отрезка лежит левее линии X – X_min.

Проверка отрезка по нижней границе Y_min:

RS: Cod R = (0010); Cod S = (0010) – это тривиальный случай и эту часть отрезка также можно отсечь. Он целиком лежит ниже нижней границы окна вывода (y = y_min)

Аналогично рассматривается перемещение точки P₂ к точке Q в сторону границы ВС окна:

Cod (P₂) = 0101 Cod Q = 0100

Бинарная операция И: 0101=0100

и 0100

0100

Отрезок P₂Q должен быть отсечён.

Cod (Q) = 0100, Cod ( T)= 0100; И = 0100

0100

0100

Отрезок должен быть отсечен.

Cod (S) 0000; Cod T (0000) – отрезок ST видим, и должен быть отрисован.

Пример 3: Анализ положения отрезка по отношению к видовому окну.

Отрезок по отношению к области вывода может быть расположен таким образом, что однозначно невозможно сказать, попадает он в окно или нет.

Надо выполнить перенос точек.

Коды конечных точек: Cod (P₁) = 1010; Cod (P₂) = 0100

Перенесём точку P₁ в точку Q, тогда

Cod (Q) = 0010 ; Cod (P₂) = 0100

Перенесём точку P₂ в точку T:

Cod (Q) = 0010 ; Cod (T) = 0100

Теперь перенесём точку Т в точку S:

Cod (Q) = 0010; Cod (S) = 0010

Это условие соответствует условию тривиальной невидимости – обе точки находятся ниже окна и отрезок P₁P₂ (или его усечённый вид QS) чертить не требуется.

Известны и другие алгоритмы: алгоритм средней точки, алгоритм Кируса-Бека. Последний построен на параметрическом представлении отрезка : P_s(t) = P₁+ (P₂ – P₁) ∙t t [0,1]. Алгоритм позволяет выполнять отсечение не только прямоугольным окном, но и любым выпуклым многоугольником.