WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Відсікання відрізків (Реферат) - Реферат

Відсікання відрізків (Реферат) - Реферат

З цих восьми випадків легко симетрично згенерувати всі інші випадки.

Головна різниця FC-алгоритму від алгоритмц Коена-Сазерленда полягає у впорядкуванні дій по відсіканню. Ефективність алгоритму Коена-Сазерленда обмежується послідовним характером і фіксованим порядком дій по відсіканню. Як приклад (див. рис. 4) відрізок RW буде відсікатися в порядку: зверху, знизу, праворуч і зліва. Число ж відсікань для визначення видимості рівно 2 - знизу і зліва. В FC-алгоритмі, напроти, для кожного значення LineCode є свій набір дій по відсіканню. Для приведеного вище прикладу необхідно тільки одне відсікання для визначення невидимості відрізка RW. Крім того, підвищення ефективності FC-алгоритму в порівнянні з CS-алгоритмом відповідає відсутності непотрібних циклів і переобчислень кодів кінцевих точок.

Двомірний алгоритм Ліанга-Барскі

В 1982 г. Ліанг і Барскі запропонували алгоритми відсікання прямокутним вікном з використанням параметричного представлення для двох, трьох і чотирьохмірного відсікання.

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

Xлев

x

Xправ

Yверх

y

Yниз

(1)

Рис. 5. Внутрішня частина вікна відсікання

Продовжимо кожну з чотирьох границь вікна до нескінчених прямих. Кожна з таких прямих ділить площину на 2 області. Назвемо "видимою частиною" ту, в якій знаходиться вікно відсікання, як це показано на рис. 6. Видимій частині відповідає внутрішня сторона лінії границі. Невидимій частині площини відповідає зовнішня сторона лінії границі.

Рис. 6. Видима частина лінії границі

Таким чином, вікно відсікання може бути визначено як область, яка знаходиться на внутрішній стороні всіх ліній границь.

Відрізок прямої, що відсікається, може бути перетворений в параметричне представлення наступним чином. Нехай кінцеві точки відрізка V0 і V1 з координатами (x0,y0) і (x1,y1), відповідно. Тоді параметричне представлення лінії може бути задано наступним чином:

x = x0 + dx t; y = y0 + dy t,

(2)

де dx = x1 - x0; dy = y1 - y0.

(3)

Або в загальному вигляді для відрізка, заданого точками V0 і V1:

V(t) = V0 + (V1 - V0) t

(4)

Для точок V0 і V1 параметр t дорівнює 0 і 1, відповідно. Змінюючи t від 0 до 1 рухаємося по відрізку V0V1 від точки V0 до точки V1. Змінюючи t в інтервалі від - до +, отримаємо безмежну пряму, орієнтація якої - від точки V0 до точки V1.

Повернемося до формального розгляду алгоритму відсікання.

Підставляючи параметричне представлення, яке задане рівняннями (2) і (3), в нерівність (1), отримаємо наступні співвідношення для частин безмежної лінії, яка знаходиться у вікні відсікання:

-dxt

x0 - Xлів

і

dxt

Xправ - x0,

-dyt

y0 - Yниж

і

dyt

Yверх - y0.

(5)

Відмітимо, що співвідношення (5) – це нерівності, які описують внутрішню частину вікна відсікання, в той же час як рівність визначає його границі.

Розглядаючи нерівності (5), бачимо, що вони мають однакову форму вигляду:

Pit  Qi для i = 1,2,3,4.

(6)

де

P1

=

-dx;

Q1

=

x0

-

Xлів;

P2

=

dx;

Q2

=

Xправ

-

x0;

P3

=

-dy;

Q3

=

y0

-

Yниж;

P4

=

dy;

Q4

=

Yверх

-

y0.

(7)

Відмітимо, що кожне з нерівностей (6) відповідає одній з граничних ліній (лівій, правій, нижній і верхній, відповідно) і описує її видиму сторону. (Наприклад, для i=1 маємо: P1t  Q1  -dxt  x0 - Xлів x0 + dxt  Xлів).

Перетворимо V0V1 в безмежну пряму. Тоді кожна нерівність задає діапазон значень параметра t, для яких ця безмежна лінія знаходиться на видимій стороні відповідної лінії границі. Більш того, конкретне значення параметру t для точки перетину є t = Qi/Pi. Причому знак Qi показує на якій стороні відповідної лінії границі знаходиться точка V0. А саме, якщо Qi  0, тоді V0 знаходиться на видимій стороні лінії границі, включаючи і її. Якщо ж Qi < 0, тоді V0 знаходиться на невидимій стороні.

Розглянемо Pi у співвідношеннях (7). Ясно, що будь-яке Pi може бути менше 0, більше 0 і рівне 0.

Pi < 0

Якщо Pi < 0, тоді:

t  Qi / Pi.

(8)

Для пояснення на рис. 7 показаний перетин з лівою і правою границями при Pi < 0.

Рис. 7. Перетин безмежної лінії, яка визначається точками V0V1 і йде з невидимої на видиму сторону, з лівою і правою границями.

Діапазон значень параметру t, для яких безмежна лінія знаходиться на видимій стороні відповідної граничної лінії, має мінімум в точці перетину направленої безмежної лінії, яка задана вектором V0V1 і йде з невидимої на видиму сторону граничної лініх (так як тільки на границі t рівне Qi / Pi, а в іншій частині видимої сторони більше).

Pi > 0

Якщо Pi > 0, тоді:

t  Qi / Pi.

(9)

Для пояснення на рис. 8 показаний перетин з лівою і правою границями при Pi > 0.

Рис. 8. Перетин безмежної лінії, яка визначається точками V0V1 і йде з видимої на невидиму сторону, з лівою і правою границями.

Так як значення параметру t тільки на границі рівний Qi/Pi, а в іншій видимій частині менше Qi/Pi, то значення параметру t має максимум на границі.

Pi = 0

Якщо Pi = 0, тоді:

0  Qi.

(10)

Відмітимо, що тут нема залежності від t, тобто нерівність виконується для всіх t, якщо Qi  0 і не має рішення при Qi < 0. Для пояснення на рис. 9 ілюструється випадок Pi = 0.

Рис. 9. Відносне розміщення безмежної лінії, яка задана точками V0V1 і йде паралельно лівій і правій границям.

Геометрично, якщо Pi = 0, то нема точок перетину безмежної лінії, яка визначається точками V0V1, з лініями границі. Більш того, якщо Qi < 0, то безмежна лінія знаходиться на зовнішній стороні лінії границі, а при Qi  0 знаходиться на внутрішній стороні (включаючи її). В останньому випадку відрізок V0V1 може бути видимий або ні в залежності від того де знаходяться точки V0V1 на безмежній лінії. В попередньому ж випадку нема видимого сегмента, так як безмежна лінія поза вікном, тобто це випадок тривіального відкидання.

Всі ці випадки представлені на схемі:

Рис. 10. Схема алгоритму Ліанга-Барскі

Loading...

 
 

Цікаве