![]() |
Програма, що реал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восями, що паралельні осям координат. Тоді рівняння еліпса має вигляд
Для визначення того, який з п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дхилення
Так саме як у алгоритмi Брезенхема, значення
-[b2x2k – 1 + a2(yk – 1 -1/2)2 - a2 b2] = 2b2 xk-1+b2. Пiсля знаходження рiзницi Якщо пiксел A+0 є ближчим до елiпса ( Якщо [xk ,yk +1/2] -- середня точка мiж пікселами A+0 i A+- , то [xk-1, yk-1 -1/2] - середня точка, що є нижчою пiкселя A+- i
Якщо dy/dx<-1, то треба вибирати мiж пiкселями A+0 i A+- , що розташованi горизонтально. Якщо вибрано пiксел A+0, то треба скористатись точкою [xk-1+1/2, yk-1-1] i iнкремент (добавка) для
= - 2a2 yk-1+a2. Якщо вибрано пiксел A0- , то треба значення
Це вказує, як формувати в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 Але у алгоритмi вже використовуються величини 2b2x i 2a2y для обчислення приростiв Наведений дал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нкремент для
=3(a2-b2)/4-(b2xk-1+a2yk-1). Оскільки алгоритм пiдраховує величини 2b2xk-1 i 2a2yk-1, то останнiй вираз можна пiдраховувати за формулою
При виконанн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 значення для dy i dx (їм вiдповiдають змiннi 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 ( Дал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 процедури. |
|||||
|