Рис. 3.14. Отсечение прямых границами окна Существует много возможных расположений отрезка прямой по отношению к окну. Этот отрезок может находиться слева, справа, над и под окном; он может пересекать любую границу окна (или две) и т. д. Поэтому нам необходим систематизированный и эффективный метод, который идентифицировал бы существующую ситуацию и вычислял бы новые концевые точки для отсеченного отрезка. Эффективность здесь важна, поскольку в типичном изображении содержатся тысячи отрезков прямой, каждый из которых необходимо отсекать границами окна. Алгоритм Кохена-Сазерленда применяет к задаче быстрый метод «разделения» («divide-and-conquer» - разделяй и властвуй). Другие методы отсечения будут обсуждаться в главе 4.
3.3.2. Алгоритм отсечения Кохена-Сазерленда Алгоритм Кохена-Сазерленда быстро выявляет и отбрасывает два распространенных случая, называемых «тривиальный прием» («trivial accept*) и «тривиальное отклонение» («trivial reject*). Как показано на рис. 3.15, обе концевые точки отрезка АВ расположены внутри окна W, и поэтому весь отрезок АВ должен располагаться внутри W. Следовательно, отрезок АВ может быть тривиально принят"images/tmp8E4A-98.png" alt="Тривиальные прием или отклонение отрезка прямой">
Рис. 3.15. Тривиальные прием или отклонение отрезка прямой Проверка на тривиальный прием и тривиальное отклонение Мы хотим быстро выявлять такие случаи, когда отрезок прямой может быть тривиально принят или тривиально отклонен. С целью облегчения этой задачи для каждой концевой точки отрезка вычисляется «кодовое слово внутри/вне» («inside-outside code word»). Рисунок 3.16 показывает, как происходит