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

Алгоритм Сазерленда-Коэна, как и в предыдущем случае, предусматривает нахождение точек пересечения отрезка со сторонами окна прямоугольной формы. Однако здесь не производится проверка корректности найденных точек пересечения. Найденная точка пересечения разбивает отрезок на две части: полностью невидимую относительно очередной стороны отсекателя и видимую часть. Невидимой будет та часть отрезка, которая заключена от вершины отрезка, невидимой относительно текущей стороны окна, до точки пересечения. Этот факт используется в алгоритме для определения части

отрезка, подлежащей отсечению. Это связано с тем, что точка, попадающая на ребро отсекателя, имеет нулевой код (она считается видимой), поэтому попарное логическое произведение кодов концов будет равно нулю.

В алгоритме предусматривается предварительный анализ сумм кодов концов отрезка и попарных логических произведений этих кодов с целью определения тривиально видимых и тривиально невидимых отрезков.

Если отрезок не является ни тривиально видимым, ни тривиально невидимым, то производится собственно его отсечение (рис.3.6.4). При этом предполагается, что невидимой относительно каждого ребра должна быть первая вершина отрезка. Поэтому в случае необходимости вершины меняются местами. Следует отметить, что одновременно обе вершины не могут быть невидимыми относительно одного текущего ребра отсекателя, так как этот факт позволил бы на предварительном этапе отбросить отрезок как тривиально невидимый.

Для удобства работы данные, задающие отсекатель, заносятся в массив "окно" O(4), в котором O₁=X_л, O₂=X_п, O₃=Y_н, O₄=Y_в. Отсечение производится в определенном порядке: левой, правой, нижней, верхней границами отсекателя. Поэтому для отыскания точек пересечения в выражения (3.6.1) следует на i-ом шаге подставлять i-ые элементы массива O. Такое задание исходных данных позволяет для горизонтального отрезка не проводить третий и четвертый этапы, а для вертикального отрезка - первый и второй этапы.

В алгоритме используется признак (флаг) Fl, определяющий расположение отрезка: Fl= -1 - отрезок вертикальный, Fl=0 - общего положения, Fl=1 - горизонтальный.

Сам алгоритм Сазерленда-Коэна можно представить в следующем виде:

1. Ввод координат отсекателя X_л (O₁), X_п (O₂), Y_н (O₃), Y_в (O₄).

2. Ввод координат концов отрезка P₁(X₁,Y₁), P₂(X ₂,Y₂).

3. Установка начального значения флага Fl=0.

4. Проверка вертикальности отрезка: если P_2.x-P_1.x=0 (вертикальный), то Fl= -1, иначе вычислить тангенс угла наклона отрезка m=(P_2.y -P_1.y)/(P_2.x-P_1.x).

5. Проверка горизонтальности отрезка: если m=0, то Fl=1.

6. Начало цикла по i от 1 до 4 отсечения отрезка по всем четырем сторонам отсекателя.

7. Обращение к алгоритму (подпрограмме) определения видимости отрезка P₁P₂ относительно заданного окна. Подпрограмма возвращает признак pr, принимающий следующие значения: pr=1 - отрезок видимый; pr= -1 - отрезок полностью невидимый; pr=0 - отрезок может быть частично видимым.

8. Анализ полученного признака видимости:

если pr= -1, то переход к п. 20;

если pr=1, то переход к п. 19.

9. Проверка видимости обеих вершин отрезка относительно текущей i-ой стороны окна: если T1i=T2_i, то переход к п.18.

10. Проверка видимости первой вершины: если T1_i=0 (вершина видима), то обмен местами вершин: R=P₁; P₁=P₂; P₂ =R.

11. Проверка вертикальности отрезка: если Fl= -1, то переход к п. 14.

12. Анализ номера шага отсечения: если i3, то переход к п. 14.

13. Вычисление координат точки пересечения с i-ым ребром отсекателя (левым или правым): P_1.y=m(O_i-P_1.x)+P_1.y; P_1.x=O_i. Переход к п. 18.

14. Проверка горизонтальности отрезка: если Fl=1, то переход к п. 18.

15. Проверка вертикальности отрезка: если Fl=-1, то переход к п.17.

16. Вычисление абсциссы точки пересечения отрезка общего положения со стороной отсекателя (верхней или нижней): P_1.x=(O_i-P_1.y)/m+P_1.x .

17. Присвоение ординате вершины отрезка ординаты стороны отсекателя: P_1.y=O_i .

18. Конец цикла по i (вычисление нового значения параметра цикла i=i+1, анализ его значения и переход на повторное выполнение цикла или выход из цикла).

19. Вычерчивание отрезка P₁P₂.

20. Конец.

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

Алгоритм определения видимости отрезка относительно окна можно представить следующим образом.

1. Вычисление кодов первой вершины отрезка T1.

2. Вычисление кодов второй вершины отрезка T2.

3. Вычисление суммы кодов первой вершины S₁= ,

4. Вычисление суммы кодов второй вершины S₂=

5. Определение полной видимости отрезка: если (S₁=0)&(S₂=0)=истина, то pr =1 и переход к п. 8.

6. Вычисление попарного логического произведения кодов концов отрезка: p= .

7. Определение полной невидимости отрезка: если p=1, то pr= -1, иначе pr=0.

8. Конец.

Логическую сумму можно вычислить или как арифметическую или как логическую сумму.