Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
KonspektKG_Ukr (1).doc
Скачиваний:
1
Добавлен:
01.07.2025
Размер:
1 Мб
Скачать
☆

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

Дані припущення використовує алгоритм відсікання Коена -Ca3рленда. Цей алгоритм особливо ефективний у двох крайніх випадках: 1) велике вікно, що містить більшість примітивів; 2) відносно маленьке вікно і велике, насичене зображення, у якому більшість примітивів лежить поза вікном. В обох випадках більшість відрізків можна прийняти або відбросити цілком.

Вихідним для роботи алгоритму є масив відрізків структури даних, кінцям яких привласнені коди в відповідності з мал.7.16. При цьому очевидно, що усередину вікна потраплять відрізки, у яких обидві кодові комбінації кінців дорівнюють 0000 (мал.7.16, правило I). Класифікувати за правилом 2 можна відрізки, у яких поразрядний логічний добуток (&) кодів їхніх кінців не дорівнює 0.

Наприклад, відрізок LM ( L=IOOI, M=OOOI) дає добуток &<>0. Отже відрізок LM, утім як і усі відрізки для який виконується умова: & <> 0, (7.23 )

відкидається і не включається у файл вікна, інакше кажучи, він невидимий. Відрізки, для яких не виконується умова ( 7.23) підлягають додатковому аналізу і можливому відсіканню.

Змістовне формулювання алгоритма:

  1. Присвоєння .кодів кінцям відрізка відповідно до мал.7.16. Прорахунок поразрядних логічних добутків (& i, i=l, n ) пар кінцевих кодів для усіх відрізків. Тут n - безліч відрізків у структурі даних.

  2. Аналіз поточного відрізка на видимість (обидві кодові комбінації його кінців рівні 0000). Якщо умова виконується - включення відрізка у файл вікна і перехід до наступного відрізку. Якщо ні - перехід до наступного пункту алгоритму.

  3. Аналіз відрізка на предмет його перебування цілком поза вікном (&i <> 0, i=l,n;). Якщо умова виконується - відрізок відкидається і переходимо до розгляду наступного відрізка no пункту 2. Якщо нi - перехід до наступного пункту алгоритму.

4. Аналіз «підозрілих» відрізків (&i = 0, і=l,n) за принципом «розділяй і пануй». Розглянемо цю інтерактивну процедуру на прикладі відрізка IJ:

4.1. Сторони вікна продляють до перетинання з відрізком IJ (мал.7.15) 0100 IJ 0010

4.2. Знаходяться крапки перетинання відрізка зі сторонами вікна або їх продовженнями в наступному порядку В, H, П, Л. Після цього зовнішня частина відрізка ( I I’ ) відтинається - гранична крапка з відповідним кодом стає кінцевою ( I’ 0000 ) : 0000 I’J 0010

4.3. Перетворений відрізок (I' J) аналізується no правилам I і 2;

4.4. Якщо правила не підтверджуються, тo аналогічно шукається крапка перетину з залишившимися сторонами вікна П,Л- J’ 0000

  1. Зовнішня частина J’J відкидається і J’ стає кінцевою крапкою відрізку 0000 I’J’ 0000.

  2. Частина, що залишилася, I’J’ направляється на перевірку за правилами 1 i 2. Правило 1 у даному випадку підтверджується. Відрізок I’J’ - видимий і переписується у файл вікна. У такий спосіб у файл вікна потрапила тільки видима у вікні ( I’J’) частина відрізка I J, обидві кінцеві крапки якого лежать поза вікном.

5.Вибір наступного відрізка і перехід до пункту 2.

Пункт 4 даного алгоритму буде працювати і з відрізками GH і КО. • Доказ цього надамо читачу.

Схема алгоритму Коэна - Сазерленда в операторній формі представлена на мал.7.17.

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]