Материал: 252_337

Розглянемо необхідні перетворення у тій послідовності, у якій їх необхідно виконувати.

1. Поворот точки М навколо осі абсцис:

А

у* = у coscp + г sin(p;

2* = -у Sin(p + 2 COSCp.

2. Поворот точки М навколо осі ординат: х* = х coscj) - 2 sincb;

*

2* = X Sin<|) + 2 COS(j).

3. Поворот точки M навколо осі аплікат: х* = х cosx + у sin/; у* = -х sinx + у cosx;

*

2=2.

4. Розтягування або стиснення вздовж координатних осей можна задати так:

х* = ах; у* = fiy; г* = yz.

5. Відображення відносно площини хОу задається формулами:

х* = х: у* = у;г* = -г.

6. Відображення відносно площини уОг задається формулами:

7. Відображення відносно площини гОх задається формулами:

Завдання

1.Розробити та реалізувати у вигляді програми алгоритм пе­ ретворення точок на площині, задавши такі вхідні дані: ко­ ординати точки М(х; у), кут повороту ер, коефіцієнти розтя­ гування (стиснення) а, 8 та необхідність відображення відносно осі абсцис і ординат.

2.Розробити та реалізувати у вигляді програми алгоритм пе­ ретворення точок у просторі, задавши такі вхідні дані: коор­ динати точки М(х; у), кути повороту навколо осей абсцис ер, ординат ф, аплікат %; коефіцієнти розтягування (стиснення) a, р, у; необхідність відображення відносно осей абсцис, ор­ динат та аплікат.

3.Виконати завдання 1-2 для різних значень вхідних даних. Результат виконання програми вивести у файл.

302

Алгоритм екранної побудови відрізка. Алгоритм Брєзєнхєма

Найчастіше для представлення графічної інформації на ек­ рані монітора використовують растрову та векторну графіку.

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

Якщо у растровій графіці основним елементом зображення є точка, то у векторній - лінія. Така лінія може бути як прямою, так і кривою, замкненою або відкритою. Отже, особливістю векторного представлення графічного зображення є те, що воно складається з ліній. Кожна лінія у векторному представленні має дві або більше опорних точок - вузлів. Загальна форма лінії задається через опорні точки, а саме між кожними двома вуз­ лами будується сегмент лінії. Слід зауважити, що у растровій графіці також можна вивести на екран монітора лінію, однак вона складатиметься з окремих точок.

Подальші пояснення базуватимуться на растровій графіці. Для того щоб лінія на екрані монітора виглядала неперерв­ ною, необхідно, щоб між її фрагментами не було «дірок». То­ му при побудові наступних алгоритмів враховуватиметься той факт, що для кожної точки растра наступною виведеною точкою має бути одна із восьми сусідніх для неї точок (мал. 172, а).

303

Мал. 172

Розглянемо алгоритм побудови відрізка. Якщо відомі ціло­ числові екранні координати його кінців, що відповідають їх за­ даним реальним координатам, то лишається визначити, які точки на екрані слід відобразити, щоб отримати реальне зглад­ жене зображення відрізка (мал. 172, б, в).

Нехай кінці М1 і М2 відрізка мають відповідно координати (JCX; ух) та (х2; у2). Тоді відрізок визначається рівнянням з кутовим

Розглянемо два випадки розміщення відрізка прямої на ек­ ранній площині. Якщо кутовий коефіцієнт k невід'ємний і не перевищує 1, тобто kKl, тоді заданий відрізок виглядає так, як показано на малюнку 172, б. У цьому випадку схема роботи ал­ горитму, що виводить зображення відрізка на екран монітора, досить проста: на кожному кроці циклу збільшуємо значення по осі Ох на 1, а по осі Оу - на значення k. Умова k < 1 необхідна для того, щоб у процесі побудови відрізка не було пропущено жодної точки.

Зауважимо, що цілочислова абсциса х поточної точки зміню­ ється на кожному кроці циклу. Щодо цілочислової ординати у, то її значення змінюватиметься лише тоді, коли у результаті накопичення приросту dy дійсна ордината точки виявиться у межах радіуса 0,5 до сусідньої точки по осі ординат. Врахував­ ши це, запишемо найпростіший варіант алгоритму в такому вигляді:

х :=х1; у :=у1; є :=0; dy:=(y2-y1)/(x2-x1); for і := 1 to n do

begin

x : = x + 1 ; e : = e + dy; {Крок по осі абсцис і обчислення відхилення.} {Якщо відхилення по осі ординат від поточного значення у перевищує 1/2,} {то необхідно збільшувати у на 1 і скоректувати відхилення є від нового значення у.}

304

if є > 0.5 then begin

|inc(y); e : = e - 1 end;

PutPixel(x, y, color) end;

Надалі необхідно буде врахувати, що у разі, коли h > 1 (мал. 172, в), обробку значень змінних х та у в алгоритмі треба поміняти ролями.

Продовжимо вдосконалення наведеного алгоритму. Неважко помітити, що в результаті його роботи отримається восьмизв'язне представлення відрізка, оскільки перехід до наступної точки відбувається на одну із восьми сусідніх клітин. Спробуємо сфор­ мулювати міркування, які дають змогу описати таке представ­ лення відрізка на площині: восьмизв'язна розгортка відрізка включає ті і тільки ті точки ґратки, бокові сторони квадрат­ них околів яких перетинаються з відрізком (мал. 172, б, в).

Якщо є < 0,5, то відрізок перети­ нається з боковою стороною квад­ ратного околу точки, що лежить справа від поточної точки, і необ­ хідно зміститися вправо на 1. Як­ що ж є > 0,5, то відрізок перети­ нається з нижньою межею квадрат­ ного околу, що лежить вище від точки, і необхідно зміститися на 1 вгору (мал. 173).

Відомо, що операції з дійсними числами виконуються повільніше, ніж із цілими, тому для

підвищення ефективності виконання алгоритму бажано відійти від виконання дійсної арифметики. З цією метою в алгоритмі, що наведений нижче, для одержання восьмизв'язної розгортки відрізка, множачи змінні dx і dy на число 2, можна позбутися дробових чисел. Змінивши «масштаб» і внісши коректування нерівності, що використовуються в операціях порівняння, от­ римаємо «цілочислову» версію алгоритму, який носить назву цілочислового алгоритму Брезенхема побудови відрізка прямої у вигляді процедури:

{Крок по осі абсцис і обчислення відхилення.} {Якщо відхилення по осі ординат від поточного значення у перевищує 1/2,}

{то необхідно збільшувати у на 1 і скоректувати відхилення є від нового значення у.}

procedure Ііпе_8(х1, х2, у1, у2: integer); var х, у, s1, s2, dx, dy, e, c: integer;

flag: boolean; begin

s1 := sign(x2 - х1); s2 := sign(y2 - у1 );{3наки відхилень по осям координат.}

Безумовно, оцінка ефективності виконання алгоритму Брезенхема для екранної побудови заданого відрізка є лінійною.

Тестування наведеного алгоритму слід провести для різних варіантів задання відрізків прямих, врахувавши такі ситуації, коли кутовий коефіцієнт менший від 1, більший від 1, дорів­ нює 1, коли координати кінців відрізка мають як цілочислові, так і дійсні значення, а також такі, що знаходяться у межах екранних координат і поза їх межами.

Алгоритм екранної побудови кола

Для побудови кола можна скористатися рівнянням кола х2 + у2 = R2, за допомогою якого обчислювати координати то­ чок, що належать цьому колу, і виводити їх на екран монітора. Але такий підхід вимагає багато обчислень, що значно змен­ шує ефективність його використання.

Розглянемо метод Брезенхема для побудови кола. Для спро­ щення розрахунків під час виконання алгоритму скористаємо­ ся тим фактом, що точки кола симетричні відносно координат­ них осей і прямих у = ±х. Згідно з цією властивістю можна по­ будувати лише 1/8 кола, а решту точок кола вивести на екран монітора, врахувавши симетрію цієї геометричної фігури: як­ що точка (х; у) належить колу, то цьому самому колу належать і точки (-х; у), (х; -у), (-х; -у), (у; х), (-у; х), (у; -х), (-у; -х).

306