4.2. Вирізання

Під словом вирізання (кліпінг) ми розуміємо обрізання форми згідно з периметром вікна. Алгоритми вирізання бувають дво- або тривимірні, їх застосовують для регулярних і нерегулярних областей[30].

Область вирізання є дуже простою але може набувати і складних форм. Це трапляється якщо вилучають сегменти, які частково видимі (рисування з областю вирізання), або якщо намагаються рисувати тоді, коли екран не знає меж обрізання (рисування без області обрізання).

Є багато алгоритмів вирізання. Звичайно, згідно з відповідним випадком, треба вибрати найліпший з алгоритмів. Далі вирізання розглянемо згідно з таким припущеннями. Вікно вирізання завжди повинно мати ортогональні боки, паралельні до осей координат; форма складатиметься з лінійних сегментів; точки і лінії поза вікном зникають (зображена лише та частина, яка є в межах вікна) [37].

4.2.1. Алгоритм серединної точки

Спочатку треба дослідити кожну точку (x, y) чи вона є всередині вікна, чи зовні, а чи є не нижче лівого нижнього кута з координатами і не вище правого верхнього згідно з нерівностями:

4.15. Лінії до вирізання 4.16. Лінії після обрізання

Розглянемо алгоритм серединної точки (поділу серединної точки). Припустимо, що точки і (рис. 4.15) є двома кінцями лінійного сегмента. Кожна точка на площині визначена двома параметрами ΙΧ та ΙΥ так

ΙΧ = -1,0+1, ΙΥ = -1,0+1.

Отже площину поділяємо на дев’ять ділянок.

Задамо відповідності і , тоді можна розглянути такий алгоритм.

• Якщо належать середині вікна, тоді вони зображені. В іншому випадку продовжуємо і переходимо до наступного кроку.

• Якщо або є поза вікном, то лінійний сегмент не зображений, що і буде закінченням алгоритму. В іншому випадку відбувається перехід до іншого кроку.

• Лінійний сегмент поділяють на дві частини, де координати серединної точки мають вигляд

.

Для кожної з половинок і повторюється алгоритм з першого кроку. Припинення роботи алгоритму відбувається після досягнення заданої точності рисування (рис 4.15, 4.16). Зазначимо, що цей алгоритм можна легко застосувати до програмного забезпечення, оскільки тут наявна єдина операція ділення на два.

4.2.2. Алгоритм Коена-Сазерленда

Розглянемо алгоритм Коена-Сазерленда. У випадку розширення границь заданого вікна ми присвоюємо площині відповідні атрибути:

• LEFT : ліворуч від лінії ;

• RIGHT: праворуч від лінії ;

• ΤΟΡ : вище від лінії ;

• BOTTOM: нижче від лінії

• ATTR( ): множина всіх характеристик точки .

На рис. 4.17 зображені точки з такими атрибутами

Рис. 4.17. Застосування алгоритму Коена - Сазерленда

Сегмент є повністю видимим, якщо , і повністю невидимим, якщо . Розглянемо такий алгоритм

Обчислюємо значення

якщо

то невидимий

вихід

якщо

M:= серединна точка of

обислюємо ATTR(M)

Якщо R or Τ ATTR(M)

В іншому випадку якщо L або B ATTR(M)

В іншому випадку якщо , можливо видимі

Повторити алгоритм для ,

В іншому випадку якщо видима, то повторити для

В іншому випадку якщо видимий, то повторити для

Кінець алгоритму

Розглянемо приклад (рис. 4.18.). Обрізати відрізок прямокутним вікном, застосовуючи алгоритм Коена - Сазерленда

Рис. 4.18. Приклад обрізання прямокутним вікном

;

;

можлива видима частина сегмента лінії;

серединна точка of ;

;

, мають можливо видиму частину;

Повторення алгоритму для , .

Лінійний сегмент ;

серединна точка of ;

;

;

Друк і повторення для ;

Лінійний сегмент ;

серединна точка на ;

;

;

Друк і повторення для ;

Процес повторюється, доки довжина сегмента не досягне визначеної точності.

Обчислимо точки перетину лінійного сегмента з вікном обрізання так.

Лінія, що проходить через точки , і є перетином вертикальними краями, має вигляд

,

де – нахил за даної лінії.

Аналогічний перетин горизонтальними краями має вигляд

Застосуємо алгоритм серединної точки, запишемо координати серединної точки, які обчислюють за формулами

.