Програма, що реал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 (інше позначення A₀₀[x_{k - 1}, y_{k - 1}]) до наступного пiксела. Цей вибiр залежить вiд вiдношення dy/dx, тобто вiд нахилу "дотичної до елiпса".

При dy/dx>-1, алгоритм здiйснює вибiр мiж двома пiкселами, що розташованi вертикально пiксел A₊₀[x_{k - 1}+1, y_{k - 1}] або пiксел A_+-[x_{k – 1} +1, y_{k – 1} - 1].

При dy/dx<-1 --- мiж двома пiкселями, що розташованi горизонтально пiксел A_0-[x_{k - 1}, y_{k - 1}-1] або пiксел A₊₀[x_{k – 1} + 1, y_{k - 1}].

При dy/dx>-1, алгоритм визначає для кожного пiкселя, що формується, яка з двох точок -- A₊₀ або A_+- -- розташована ближче до елiпса. Для цього перевiряємо, розташована середня точка B = (A₊₀ + A_+-)/2 вiдрiзка [A₊₀ A_+-] у серединi або зовнi елiпса.Легко перевiрити, що B[x_{k – 1} +1, y_{k – 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} = [b²(x_{k – 1} +1)² + a² (y_{k – 1} - 1/2)² - a² b²]

-[b²x²_{k – 1} + a²(y_{k – 1} -1/2)² - a² b²] = 2b² x_k-1+b².

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

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

Якщо [x_k ,y_k +1/2] -- середня точка мiж пікселами A₊₀ i A_+- , то [x_k-1, y_k-1 -1/2] - середня точка, що є нижчою пiкселя A_+- i

_k - _k-1 = [b²x²_k-1+a²(y_k-1-1/2)² -a²b²] - [b²x²_k-1+a²(y_k-1+1/2)² -a²b²]=-2a²y_k-1.

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

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

_k- _k-1=[b²(x_k-1+1/2)²+a²(y_k-1-1/2)²-a²b²]-[b²(x_k-1+1/2)²+a²(y_k-1-1/2)²-a²b²]=

= - 2a² y_k-1+a².

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

_k - _k-1 = [b²(x_k-1+1/2)²+a²y_k-1²-a²b²]-[b²(x_k-1-1/2)²+a²y²_k-1-a²b²]=2b²x_k-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), отримаємо

2b²x+2a²yy'=0 dy/dx=-(2b²x)/(2a²y)=-1 2b²x=2a²y.

Але у алгоритмi вже використовуються величини 2b²x i 2a²y для обчислення прирост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=[b²(x_k-1+1/2)²+a²(y_k-1-1)²-a²b²] -[b²(x_k-1+1)²+a²(y_k-1-1/2)²-a²b²]=

=3(a²-b²)/4-(b²x_k-1+a²y_k-1).

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

_k - _k-1=3(a²-b²)/4-(2b²x_k-1+2a²y_k-1)/2.

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

Реалiзацiя алгоритму.Програма, що наведена далi, є швидкою та ефективною, так як всi обчислення значень змiнних зведенi до додавання та вiднiмання. Внутрiшнi цикли не мiстять множень завдяки попередньому обчисленню значень a², b², 2a², 2b² (в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):

:=b²(1)²+a²(b-1/2)²-a²b²=b²-a²b+a²/4.

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

dx:=2b² 0=0, dy:=2a²(b)=2a²b=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пса (x_c, y₀).

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

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