Работа №5 Задание

Реализовать в виде программы алгоритм двумерного внутреннего отсечения Сазерленда-Коэна

Обзор теории

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

Алгоритм, описанный в предыдущем разделе, аналогичен тому, который предложили Коэн и Сазерленд. В алгоритме двумерного отсечения отрезок отсекался поочередно каждой из сторон окна, а для полученных точек пересечения проверялась их принадлежность внутренней области окна, т. е. корректность пересечения. Эта процедура применялась сначала к отрезку P₁P₂ и получался отрезок P'₁P₂, а затем к отрезку P'₁P₂ и получался результирующий отрезокP'₁P'₂.

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

Алгоритм Сазерленда - Коэна формулируется следующим образом:

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

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

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

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

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

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

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

Отрезок пересекает левую сторону окна. P₁ - вне окна.

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

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

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

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

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

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

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

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

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

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

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

Алгоритм двумерного отсечения Сазерленда — Коэна:

Окно — массив 1 х 4, содержащий координаты (хл, хп, ун, ув) сторон окна

Рр Р2 — концевые точки отрезка с координатами (PjX, P,y) и (Р2х, Р2у) соответственно

Т1код, Т2код — массивы 1 х 4, содержащие коды точек Р, и Р2

Флаг — индикатор координатной ориентации отрезка, равный' — 1, при вертикальности, 0, при горизонтальности инициализация Флаг

Флаг = 1 проверка вертикальности и горизонтальности отрезка

if Р2х - Р,х = 0 then

Флаг = - 1

else

вычисление наклона

Наклон = (Р2у - Р^,у)/(Р2х - Р^,х)

if Наклон = 0 then Флаг = 0

end if

для каждой стороны окна

for i = 1 to 4

call Коэн (Р,, Р2, Окно; Видимость)

if Видимость = да then 2

if Видимость = нет then 3

проверка пересечения отрезка и стороны окна

if Т1кодE - i) = Т2кодE - i) thenl

проверка нахождения Р, вне окна; если Р} внутри окна, то

поменять Р, /./ Р2 местами

if Т1кодE - i) = 0 then

Раб = Р;

Pi = р2

Р2 = Раб

end if

поиск пересечений отрезка со сторонами окна выбор соответствующей подпрограммы вычисления пересечения контроль вертикальности отрезка

if Флаг < > - 1 и i ^ 2 then

Р,у = Наклон * (OkhOj — Р,х) + Р,у

Р,х = j

else

if Флаг < > 0 then

if Флаг < > -1 then

PjX = A/Наклон) * (Okhoj - P,y) + P,x

end if

P,y = Окно{

end if

end if

1 next i

начертить видимый отрезок

2 Draw P,P2

3 finish

подпрограмма определения видимости отрезка

subroutine Коэн (Р,, Р2, Окно; Видимость)

Р,, Р2 — концевые точки отрезка с координатами (Р,х, Р,у) и

(Р2х, Р2у) соответственно.

Окно — массив 1 х 4, содержащий координаты (хл, хп, ун, ув)

сторон окна

Видимость — признак видимости отрезка равный: «нет»,

«частично», «да», если отрезок соответственно:

полностью невидим, видим частично или полностью видим

вычисление кодов концевых точек отрезка

call Конец (Р,, Окно; Т1код, Сумма1)

call Конец (Р2, Окно; Т2код, Сумма2)

предположим, что отрезок частично видим

Видимость = частично

проверка полной видимости отрезка

if Сумма 1 = 0 и Сумма 2 = 0 then

Видимость = да

else

проверка тривиальной невидимости отрезка

call Логическое (Т1код, Т2код, Произвел)

if Произвел < > 0 then Видимость = нет

end if

отрезок может оказаться частично видимым

return

подпрограмма вычисления кодов концевой точки отрезка

subroutine Конец (Р, Окно; Ткод, Сумма)

Рх, Ру — координаты точки Р

Окно — массив 1x4, содержащий координаты (хл, хп, ун, ув)

сторон окна

Ткод — массив 1 х 4, содержащий коды концевой точки

Сумма — сумма всех элементов массива Ткод

вычисление кодов концевой точки

if Рх < хл then ТкодD) = 1 else ТкодD) = 0

if Рх > хп then Ткод(З) = 1 else Ткод(З) = 0

if ру < Ун tnen ТкодB) = 1 else ТкодB) = 0

if Ру > Ув then ТкодA) = 1 else ТкодA) = 0

вычисление суммы

Сумма = 0

for i = I to 4

Сумма = Сумма + ТкодО)

next i

return

подпрограмма вычисления логического произведения

subroutine Логическое (Т1код, Т2код; Произвел)

Т1код, Т2код — массивы 1 х 4, содержащие коды первой и второй концевых точек соответственно

Произвел — сумма побитовых логических произведений

Произвел = О

for i = 1 to 4

Произвел = Произвел + Целая часть ((Т1код@ + Т2кодО))/2)

next i

return