Алгоритм, описанный в предыдущем разделе, аналогичен тому, который предложили Коэн и Сазерленд. В алгоритме двумерного отсечения отрезок отсекался поочередно каждой из сторон окна, а для полученных точек пересечения проверялась их принадлежность внутренней области окна, т. е. корректность пересечения. Эта процедура применялась сначала к отрезку P1P2 и получался отрезок P'1P2, а затем к отрезку P'1P2 и получался результирующий отрезок P'1P'2.
В алгоритме Сазерленда - Коэна отрезок тоже разбивается сторонами окна. Отличие состоит в том, что здесь не производятся проверки попадания точки пересечения внутрь окна, вместо этого каждая из пары получающихся частей отрезка сохраняется или отбрасывается в результате анализа кодов ее концевых точек. Рассмотрение отрезка P1P2 на рис. 3 показывает трудность реализации этой идеи. Если P1P2 разбивается левой стороной окна, то получается два новых отрезка P1P'1 и P'1P2. Коды концевых точек каждого из этих отрезков таковы, что оба они могут быть частично видимы. Следовательно, ни один из них нельзя отвергнуть как невидимый или оставить как видимый. Ключом к алгоритму Сазерленда - Коэна является информацию о том, что одна из концевых точек отрезка лежит вне окна. Поэтому тот отрезок, который заключен между этой точкой и точкой пересечения, можно отвергнуть как невидимый. Фактически это означает замену исходной концевой точки на точку пересечения.
Для каждой стороны окна выполнить:
Для каждого отрезка P1P2 определить, не является ли он полностью видимым или может быть тривиально отвергнут как невидимый.
Если P1 вне окна, то продолжить выполнение, иначе поменять P1 и P2 местами.
Заменить
P1 на точку пересечения P1P2 со стороной окна.Этот алгоритм иллюстрирует следующий пример.
Рассмотрим отсечение отрезка P1P2 окном, показанным на рис. 3. Коды концевых точек P1 (- 3/2, 1/6) и P2 (1/2, 3/2) равны (0001) и (1000) соответственно. Этот отрезок не является ни полностью видимым, ни тривиально невидимым.
Отрезок пересекает левую сторону окна. P1 - вне окна.
Пересечение с левой стороны (x = -1) окна происходит в точке P'1 (-1, 1/2). Замена P1 на P'1 дает новый отрезок от P1 (-1, 1/2) до P2 (1/2, 3/2).
Коды концевых точек
P1 и P2 теперь стали (0000) и (1000). Отрезок не является ни полностью видимым, ни тривиально невидимым.Отрезок не пересекается с правой стороной окна. Перейти к нижней стороне.
Коды концевых точек
P1 и P2 остаются по-прежнему равными (0000) и (1000). Отрезок не является ни полностью видимым, ни тривиально невидимым.Отрезок не пересекается с нижней стороной окна. Перейти к верхней.
Коды концевых точек
P1 и P2 остаются равными (0000) и (1000). Отрезок не является ни полностью видимым, ни тривиально невидимым.Отрезок не пересекается с верхней стороной окна.
P1 - не снаружи окна. Поменяв P1 на P2 местами, получили новый отрезок от P1 (1/2, 3/2) до P2 (-1, 1/2).Точка пересечение с верхней стороной окна (
y = -1) равна P'1 (-1/4, 1). Заменив P1 на P'1, получаем новый отрезок от P1 (-1/4, 1) до P2 (-1, 1/2).Теперь коды концевых точек
P1 и P2 равны (0000) и (0000). Отрезок полностью видим.Процедура завершена.
Начертить отрезок.
Алгоритм двумерного отсечения Сазерленда - Коэна.