Алгоритм отсечения Сазерленда-Коэна

В алгоритме Сазерленда-Коэна отрезок тоже разбивается сторонами окна. Отличие состоит в том, что здесь не производится проверки попадания точки пересечения внутрь окна, вместо этого каждая из пары получающихся частей отрезка сохраняется или отбрасывается в результате анализа кодов ее концевых точек. Для определения той из девяти областей, которой принадлежит конец ребра, вводится четырехразрядный (битовый) код. Крайний правый бит кода считается первым. В соответствующий бит заносится 1 при выполнении следующих условий:

· для первого бита - если точка левее окна

· для второго бита - если точка правее окна

· для третьего бита - если точка ниже окна

· для четвертого бита - если точка выше окна

· В противном случае в бит заносится нуль.

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

Для каждой стороны окна выполнить:

1. Для каждого отрезка Р₁P₂ определить, не является ли он полностью видимым или может быть тривиально отвергнут как невидимый.

2. Если Р₁ вне окна, то продолжить выполнение, иначе поменять Р₁ и Р₂ местами.

3. Заменить Р₁ на точку пересечения Р₁Р₂ со стороной окна.

Этот алгоритм иллюстрирует следующий пример.

Рассмотрим вновь отсечение отрезка Р₁Р₂ окном, показанным на рис. 3.2. Коды концевых точек Р₁(- 3/2,1/6) и Р₂(1/2,3/2) равны (0001) и (1000) соответственно. Этот отрезок не является ни полностью видимым, ни тривиально невидимым. Отрезок пересекает левую сторону окна. Р₁ - вне окна.

Пересечение с левой стороной (х = -1) окна происходит в точке Р₁'(-1,1/2). Замена Р₁ на Р₁' дает новый отрезок от Р₁ (-1,1/2) до Р₂(1/2,3/2).

Коды концевых точек Р₁ и Р₂ теперь стали (0000) и (1000) соответственно. Отрезок не является ни полностью видимым, ни тривиально невидимым.

Отрезок не пересекается с правой стороной окна. Перейти к нижней стороне.

Коды концевых точек Р₁ и Р₂ остаются по-прежнему равными (0000) в (1000) соотвественно.Отрезок не является ни полностью видимым, ни тривиально невидимым.

Отрезок не пересекается с нижней стороной окна. Перейти к верхней стороне.

Коды концевых точек Р₁ и Р₂ остаются равными (0000) и (1000) соответственно. Отрезок не является ни полностью видимым, ни тривиально невидимым.

Отрезок пересекается с верхней стороной окна. Р1 - не снаружи окна. Поменяв Р₁ и Р₂ местами, мы получим новый отрезок от Р₁(1/2,3/2) до P₂(-1,1/2).

Точка пересечення отрезка с верхней стороной окна (y = 1) равна Р₁'(-1/4,1). Заменив Р₁ на P₁', получаем новый отрезок от Р₁(-1/4,1) до P₂(-1,1/2).

Теперь коды концевых точек Р₁ и Р₂ равны (0000) и (0000) соответственно. Oтрезок полностью видим.

Процедура завершена.

Начертить отрезок.

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