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

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

В этом алгоритме отрезок разбивается сторонами окна. Каждая из пары получившихся частей отрезка сохраняется или отбрасывается в результате анализа кодов её концевых точек (рис.11). Если P₁P₂ разбивается левой стороной окна, то получается два новых отрезка – P₁P₁’ и P₁’P₂. Ключом к алгоритму Сазерленда-Коэна является информация о том, что одна из концевых точек отрезка лежит вне окна. Поэтому тот отрезок, который заключен между этой точкой и точкой пересечения, можно отвергнуть как невидимый. Фактически это означает замену исходной концевой точки на точку пересечения. Содержание алгоритма формулируется так.

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

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

• если P₁ вне окна, то продолжить выполнение, иначе поменять P₁ и P₂ местами;

• заменить P₁ на точку пересечения отрезка P₁P₂ со стороной окна.

5.3. Алгоритм разбиения средней точкой

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

В алгоритме используются коды концевых точек отрезка и проверки, выявляющие полную видимость отрезков (a), и тривиально невидимых (b). Те отрезки, которые с помощью таких простых проверок нельзя отнести к одной из двух категорий (c, g, f), разбиваются на две равные части. Затем те же проверки применяются к каждой из половин до тех пор, пока не будет обнаружено пересечение со стороной окна или длина разделенного отрезка не станет пренебрежимо малой, т.е. пока он не выродится в точку. После вырождения определяется видимость полученной точки. В результате процесс обнаружения пересечения сводится к двоичному поиску. Данный алгоритм можно записать следующим образом.

Для каждой концевой точки отрезка:

• если концевая точка видима, то она будет наиболее удаленной видимой точкой. Процесс завершен. Иначе – продолжить;

• если отрезок тривиально характеризуется как невидимый, то выходная информация не формируется. Процесс завершен. Иначе – продолжить;

• грубо оценить наиболее удаленную видимую точку путем деления отрезка P₁P₂ средней точкой P_m. Применить вышеизложенные тесты к двум частям P₁P_m и P_mP₂. Если P_mP₂ тривиально отвергается как невидимый, то средняя точка дает верхнюю оценку для наиболее удаленной видимой точки. Продолжить процедуру с отрезком P₁P_m. Иначе - средняя точка дает оценку снизу для наиболее удаленной видимой точки. Продолжить процедуру с P₂P_m. Если отрезок становится настолько мал, что его средняя точка совпадает с его концами с машинной или предельно заданной точностью, то надо оценить её видимость и закончить процесс.