ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


Програма, що реалiзує алгоритм Брезенхема креслення частини кола у першому квадрантi.

Загрузка...

{Метод Брезенхема побудови частини кола у першому квадрантi}

unit Unit1;

interface {Unit1}

uses Windows, Messages, SysUtils, Classes, Graphics,

Controls, Forms, Dialogs, StdCtrls;

type TForm1 = class(TForm)

Label1,Label2,Label3:TLabel;Button1:TButton;

Edit1,Edit2,Edit3:TEdit;

procedure Button1Click(Sender: TObject);

private { Private declarations }

public { Public declarations }

end;

var Form1: TForm1;

implementation {Unit1}

{$R *.DFM}

var Xs,Ys,R : integer;

 

procedure RastrBresCircle(Xc,Yc,R,Color:integer);

var i,D,DL,DLP,Lim,x,y:integer;

{тут D=Dgreat,DL=DLitle,DLP=DLitlePrim}

begin {RastrBresCircle}

if R>0

then begin {R>0}

{початкове установлення змiнних}

x:=0;y:=R;

D:=2*(1-R);Lim:=0;

repeat {Початок головного циклу}

Form1.Canvas.Pixels[Xc+x,Yc+y]:=Color;

if y<=Lim then break;

if D<0

then begin {D<0}

DL:=2*D+2*y-1;

if DL<=0

then begin x:=x+1; D:=D+2*x+1; end

else begin x:=x+1;y:=y-1;D:=D+2*x-2*y+2; end;

end {D<0}

else begin {D>=0}

if D>0

then begin {D>0 }

DLP:=2*D-2*x-1;

if DLP<=0

then begin

x:=x+1;y:=y-1;

D:=D+2*x-2*y+2;

end

else begin

y:=y-1;

D:=D-2*y+1;

end;

end {D>0}

else begin {D=0}

x:=x+1;y:=y-1;D:=D-2*y+2;

end; {D=0}

end; {D>=0}

until false;

end; {R>0}

end;{RastrBresCircle}

 

procedure TForm1.Button1Click(Sender: TObject);

begin {TForm1.Button1Click}

Xs:=StrToInt(Edit1.Text);

Ys:=StrToInt(Edit2.Text);

R:=StrToInt(Edit3.Text);

RastrBresCircle(Xs,Ys,R,clGreen);

end; {TForm1.Button1Click}

end. {Unit1}

Лiтература.[22], [5]

 

2.1.4 Алгоритм Брезенхема побудови елiпса

Опис алгоритму.Побудова ітераційного алгоритму типа Брезенхема побудови еліпса є аналогічною побудові алгоритму Брезенхема для прямої. Загальний алгоритм формування еліпсів, осі яких не є паралельними осям координат див. у [14].

Наведемо далi "алгоритм середньої точки" для еліпса з центром у початку координат i напiвосями, що паралельні осям координат. Тоді рівняння еліпса має вигляд

b2 x2 + a2 y2 - a2 b2 = 0, a, b>0. (5)

Для визначення того, який з пiкселiв є найближчим до еліпсу алгоритм використовує значення рівняння еліпса у середній точці між пiкселами. Якщо це значення є від’ємним, то середня точка знаходиться у середині еліпса, додатним -- зовні еліпса.

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

Виникає питання, який з сусiднiх пiкселiв треба дослiджувати на k-му кроцi iтерацiйного алгоритму при переходi вiд пiксела A (інше позначення A00[xk - 1, yk - 1]) до наступного пiксела. Цей вибiр залежить вiд вiдношення dy/dx, тобто вiд нахилу "дотичної до елiпса".

При dy/dx>-1, алгоритм здiйснює вибiр мiж двома пiкселами, що розташованi вертикально пiксел A+0[xk - 1+1, yk - 1] або пiксел A+-[xk – 1 +1, yk – 1 - 1].

При dy/dx<-1 --- мiж двома пiкселями, що розташованi горизонтально пiксел A0-[xk - 1, yk - 1-1] або пiксел A+0[xk – 1 + 1, yk - 1].

При dy/dx>-1, алгоритм визначає для кожного пiкселя, що формується, яка з двох точок -- A+0 або A+- -- розташована ближче до елiпса. Для цього перевiряємо, розташована середня точка B = (A+0 + A+-)/2 вiдрiзка [A+0 A+-] у серединi або зовнi елiпса.Легко перевiрити, що B[xk – 1 +1, yk – 1 - 1/2]. Тому все залежить вiд знаку функцiї вiдхилення

k = k (B) = b2(xk – 1 +1)2 + a2 (yk – 1 - 1/2)2 - a2 b2. (6)

Так саме як у алгоритмi Брезенхема, значення k обчислюються iтеративним чином.

k - k 1 = [b2(xk 1 +1)2 + a2 (yk 1 - 1/2)2 - a2 b2]

-[b2x2k 1 + a2(yk 1 -1/2)2 - a2 b2] = 2b2 xk-1+b2.

Пiсля знаходження рiзницi k i k-1 (тобто k y) ще треба множити x2k на сталу. Але цього можна уникнути, обчислюючи k x (також як k y) додаючи 2b2 на кожному iтерацiйному кроцi.

Якщо пiксел A+0 є ближчим до елiпса ( k), то нове значення k, яке буде обчислено, можна використати як k-1 у наступнiй iтерацiї. Але, якщо до елiпса ближче точка A+- , то k треба скорегувати, зробивши зсув на один крок донизу.

Якщо [xk ,yk +1/2] -- середня точка мiж пікселами A+0 i A+- , то [xk-1, yk-1 -1/2] - середня точка, що є нижчою пiкселя A+- i

k - k-1 = [b2x2k-1+a2(yk-1-1/2)2 -a2b2] - [b2x2k-1+a2(yk-1+1/2)2 -a2b2]=-2a2yk-1.

Якщо dy/dx<-1, то треба вибирати мiж пiкселями A+0 i A+- , що розташованi горизонтально.

Якщо вибрано пiксел A+0, то треба скористатись точкою [xk-1+1/2, yk-1-1] i iнкремент (добавка) для дорівнює

k- k-1=[b2(xk-1+1/2)2+a2(yk-1-1/2)2-a2b2]-[b2(xk-1+1/2)2+a2(yk-1-1/2)2-a2b2]=

= - 2a2 yk-1+a2.

Якщо вибрано пiксел A0- , то треба значення k-1 скорегувати на крок у правому напрямку

k - k-1 = [b2(xk-1+1/2)2+a2yk-12-a2b2]-[b2(xk-1-1/2)2+a2y2k-1-a2b2]=2b2xk-1.

Це вказує, як формувати вiдповiднi значення iтерацiйним чином з використанням лише додавання або вiднiмання при виконаннi iтерацiйних циклiв.

Попереднiй аналiз вiдрiзняє випадки, коли dy/dx<-1 i dy/dx>-1. Залишилось розглянути випадок, коли dy/dx=-1. Розглядаючи (5) як тотожнiсть, де y=y(x), отримаємо

2b2x+2a2yy'=0 dy/dx=-(2b2x)/(2a2y)=-1 2b2x=2a2y.

Але у алгоритмi вже використовуються величини 2b2x i 2a2y для обчислення приростiв ky i kx, то останнi можна використовувати для визначення моменту, коли значення dy/dx досягне значення -1.

Наведений далi алгоритм креслить за стрiлкою годинника дугу елiпса у першiй чвертi, тобто вiд точки (0,b) до точки (a,0) (на екранi це буде третя чверть).

Спочатку вважаємо, що dy/dx>-1 i вибiр здiйснюємо мiж вертикальними пiкселями, до того, коли стане dy/dx=-1.

При виконаннi умови dy/dx=1 старi значення знаходились для вертикальних пiкселiв, а треба перейти до вибору горизонтальних пiкселiв. У цей момент треба iнкремент для k обчислити за виразом

k - k-1=[b2(xk-1+1/2)2+a2(yk-1-1)2-a2b2] -[b2(xk-1+1)2+a2(yk-1-1/2)2-a2b2]=

=3(a2-b2)/4-(b2xk-1+a2yk-1).

Оскільки алгоритм пiдраховує величини 2b2xk-1 i 2a2yk-1, то останнiй вираз можна пiдраховувати за формулою

k - k-1=3(a2-b2)/4-(2b2xk-1+2a2yk-1)/2.

При виконаннi умови dy/dx<-1 алгоритм здiйснює вибiр горизонтальних пiкселiв.

Реалiзацiя алгоритму.Програма, що наведена далi, є швидкою та ефективною, так як всi обчислення значень змiнних зведенi до додавання та вiднiмання. Внутрiшнi цикли не мiстять множень завдяки попередньому обчисленню значень a2, b2, 2a2, 2b2 (вiдповiдно, змiннi Sqr_a, Sqr_b, TwoSqr_a, TwoSqr_b). Початковi значення змiнних пiдраховуються при припущеннi, що перший пiксел виводимо у точцi (0,b).

Таким чином, початкове значення обчислюється для середньої точки мiж пiкселями з координатами (1,b) i (1,b-1), тобто у точцi (1,b-1/2):

:=b2(1)2+a2(b-1/2)2-a2b2=b2-a2b+a2/4.

Початковi значення для dy i dx (їм вiдповiдають змiннi k i x опису алгоритму):

dx:=2b2 0=0, dy:=2a2(b)=2a2b=TwoSqr_a*b.

Процедура BresenhamEllipse є точною реалiзацiєю наведеного алгоритму.

Спочатку вона формує всi пік селі мiж (0,b) i точкою, де похiдна dy/dx стає рiвною -1.

Потiм процедура корегує значення d ( k при dy/dx=-1).

Далi iтеративний вибiр пiкселiв продовжується до досягнення осi OX.

Процедура викликає процедуру Set4Pixels для малювання кожного з чотирьох пiкселiв, що вiдповiдають поточному сформованому пiкселю у чотирьох квадрантах вiдносно фактичного центру елiпса (xc, y0).

Вiдсiкання точок, яки не є видимими у клiєнтської частинi форми, при цьому не робиться (це здiйснюється системними засобами).

Вiдповiднi процедури.

Загрузка...

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти