Загальний метод Брезенхема побудови вiдрiзка.

var Xs,Ys,Xf,Yf : integer;

function Sign(X:integer):integer;

begin {Sign}

if X>0 then Sign:=1;

if X=0 then Sign:=0;

if X<0 then Sign:=-1;

end; {Sign}

procedure RastrBresLine(Xs,Ys,Xf,Yf,Color:integer);

var i,Dx,Dy,De,s1,s2,x,y,Temp,Change: integer;

begin {RastrBresLine}

// початковi установки

x:=Xs; y:=Ys;

Dx:=abs(Xf-Xs); Dy:=abs(Yf-Ys);

s1:=Sign(Xf-Xs); s2:=Sign(Yf-Ys);

// обмiн Dx и Dy у залежностi вiд коеф. нахилу вiдрiзка

if Dy > Dx

then begin

Temp:=Dx;Dx:=Dy;Dy:=Temp;Change:=1;

end

else Change:=0;

// уставлення нев'язки De з поправкою на пiвпiкселя

De:=2*Dy-Dx;

for i:=1 to Dx do

begin {for i}

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

while De>=0 do

begin

if Change=1 then x:=x+s1 else y:=y+s2; De:=De-2*Dx;

end;

if Change=1 then y:=y+s2 else x:=x+s1; De:=De+2*Dy;

end; {for i}

end; {RastrBresLine}

procedure TForm1.Button1Click(Sender: TObject);

begin {TForm1.Button1Click}

Xs:=StrToInt(Edit1.Text); Ys:=StrToInt(Edit2.Text);

Xf:=StrToInt(Edit3.Text); Yf:=StrToInt(Edit4.Text);

RastrBresLine(Xs,Ys,Xf,Yf,clGreen);

end; {TForm1.Button1Click}

Зауваження 1Наведенi алгоритми Брезенхема породжують лiнiю вiдрiзка границi, яка є чотирьохзв'язною (див. Пiдроздiл 2.2.5). Тому алгоритми Брезенхема зручно використовувати для виведення вiдрiзкiв границi областi, внутрішню (або зовнiшню) частину якої потрiбно заповнити якимось кольором.

Зауваження 2Для виведення вiдрiзкiв у вікно форми мовою Object Pascal використовуються процедури Form1.Canvas.MoveTo(Xa,Ya) i Form1.Canvas.LineTo(Xb,Yb) (див.[9]). Для виведення окремих пiкселiв використовується процедура Form1.Canvas.Pixels[X,Y]. Вiдповiднi засоби у мовi програмування C++ див.[10, стор.64-65].

Реалiзацiю алгоритму Брезенхема мовою програмування C див. [4, стор.128-129] i [11, стор. 121-126], на асемблерi - [11, стор. 126-129].

Лiтература. [12], [4, Гл.6], [8, стор.100-101], [11, Часть III], [13, Разд. 0.2.3], [13, 0.13, Прил. 2].

2.1.3 Алгоритм Брезенхема креслення кола

У растр потрiбно розкладати не тiльки лiнiйнi, а й iншi, складнiші функцiї. Розкладання у растр конiчних перерiзiв, тобто кола, елiпса, параболи, гiперболи, розглядалося у значної кiлькостi робiт ([14], [15], [16], [17]). Найбiльшу увагу приділяли колу ([18], [19], [20], [21]).Найбiльш ефективний i нескладний алгоритм був запропонований Брезенхемом [22]. Для початку зауважимо, що можна генерувати тiльки одну восьму частину кола (наприклад, перший октант з кутом вiд 0 до 45 градусiв). Інші частини одержуємо послiдовними симетрiями (вiдносно прямої y=x , потім вiдносно прямої x=0 i нарештi вiдносно прямої y=0).Для побудови алгоритму розглянемо першу чверть (квадрант) кола з центром в початку координат. Зауважимо, що при початку роботи алгоритму з точки (0,R) i генерацiї точок кола за годинниковою стрiлкою у першому квадрантi y-координати згенерованих точок, є монотонно спадною функцією вiд аргументу x. Будемо вважати, що центр кола знаходиться у точцi (0,0) i радiус R>0 є величина цiла.

Для будь-якої точки кола при генеруваннi за напрямом стрiлки годинника iснує лише три можливостi обрати наступний пiксел, що наближатиме коло найлiпшим чином:

Рис.1. Вибiр пiкселiв у першому квадрантi

На рис.1. цi напрямки позначенi вiдповiдно m_H, m_D, і m_V. Алгоритм вибирає той пiксел, для якого є найменшим квадрат вiдстанi мiж одним з цих пiкселiв i колом, тобто вибирає мiнiмум з наступних чисел

У околi точки (x_i,y_i) можливi лише п'ять типiв перетину кола з сіткою растра:

Випадок 1. Коло пройде мiж точками (x_i+1,y_i) i (x_i+1,y_i-1).

Випадок 2. Коло пройде мiж точками (x_i+1,y_i) i (x_i+1,y_i+1).

Випадок 3. Коло пройде мiж точками (x_i,y_i-1) i (x_i+1,y_i-1).

Випадок 4. Коло пройде мiж точками (x_i-1,y_i-1) i (x_i, y_i-1).

Випадок 5. Коло пройде через точку (x_i+1,y_i-1).

Позначимо через рiзницю мiж квадратами вiдстаней вiд центра кола до пiксела (x_i+1,y_i-1) i вiд центра кола до точки на колi, тобто .

Як у алгоритмi Брезенхема для вiдрiзка, бажано при обраннi нового пiксела використовувати лише знак похибки . Розглянемо алгоритм пiд цим кутом зору.

1. Випадок, коли <0.При <0 дiагональна точка (x_i+1,y_i-1) знаходиться всерединi кола, тобто маємо випадки 1 або 2. Звiсно, що потрiбно вибрати або пiксел (x_i+1,y_i), тобто m_H, або пiксел (x_i+1,y_i-1), тобто m_D.

Розглянемо спочатку випадок 1. Знайдемо рiзницю квадратiв вiдстаней від кола до пiкселiв у горизонтальному m_H i дiагональному m_D напрямках:

При <0 вiдстань вiд кола до дiагонального пiксела (величина m_D) бiльшa нiж до горизонтального (величина m_H). Тому

при 0 вибираємо mH (у точку (xi+1, yi)), інакше вибираємо mD ( у точку (xi+1, yi-1))

(3)

Зауважимо, що у випадку 1: (x_i+1)² +y_i²-R² 0, (x_i+1)² +(y_i-1)²-R² 0 тому що дiагональний пiксел (x_i+1,y_i-1) завжди лежить всерединi кола, а горизонтальний пiксел (x_i+1,y_i) - зовнi. Тому можна рахувати за формулою

= (x _i +1)² + y _i ² – R ² + (x _i +1) ²+(y _i - 1)²-R ²

=2(x _i +1) ² + 2 y_i ²-1²-2 R ²-2 y _i -1=2 ( + y_i)-1

У випадку 2 потрiбно вибрати горизонтальний пiксел (x_i+1,y_i) тому, що y є монотонно спадна функцiя вiд x. При цьому горизонтальний (x_i+1,y_i) i дiагональний (x_i+1,y_i-1) пiкселi лежать у серединi кола.

Тодi (x_i + 1) ²+ y _i ² – R ² <0, (x _i + 1) ² + (y _i - 1) ² – R ²<0 i

= - (x _i + 1) ² – y _i ² + R ² + (x _i + 1) ² + (y _i - 1) ² - R ²= - 2y_i +1<0.

Тому дiє правило (3).

2. Випадок, коли >0. При >0 дiагональна точка (x_i+1,y_i-1) знаходиться зовнi кола, тобто одержуємо випадки 3 i 4 (потрiбно вибрати або пiксел (x_i+1,y_i-1), тобто m_D, або пiксел (x_i,y_i-1), тобто m_V). Знайдемо рiзницю квадратiв вiдстаней вiд кола до пiкселiв у дiагональному m_D i вертикальному m_V напрямках:

При '<0 вiдстань вiд кола до вертикального пiксела (x_i, y_i-1) бiльше нiж вiдстань до дiагонального (x_i+1, y_i-1) пiксела. Тому формулюємо наступне правило вибору

при ’ 0 вибираємо mD ( у точку (x i+ 1, yi - 1)) інакше вибираємо mV (у точку (xi, yi-1))

(4)

Перевiрка компонент ' для випадку 3 дає (x_i + 1) ² + ( y_i - 1) ² – R ² 0,

x _i ² + (y _i + 1) ² – R ² < 0 тому, що у цьому випадку дiагональний пiксел

(x _i + 1 , y _i - 1) лежить зовнi кола, а вертикальний пiксел (x _i , y_i - 1) -- у серединi кола. Звідси

’= (x _i +1)² + (y _i - 1) ² – R ² + x _i ²+(y _i - 1)²-R ²

=2(x _i +1) ² + 2( y_i - 1)² - 2 R ²+ (y _i -1)² – 2 x_i - 1=2 ( + x_i)-1

У випадку 4 потрiбно вибирати вертикальний пiксел (x_i, y_i-1) тому, що y є монотонно спадна функція вiд x. При цьому (x_i + 1)²(y_i -1)² - R²>0,

x_i² + (y_i - 1)² - R²>0 тому, що обидва пiкселя знаходяться зовнi кола. Звiдси '>0, тобто дiє правило (4)

3. Випадок, коли =0. При =0 маємо випадок 5, тобто коли дiагональний пiксел (x_i+1,y_i-1) належить до кола. Перевiрка компонент виразу дає (x_i+1)²+y_i²-R²>0, (x_i+1)²+(y_i-1)²-R²=0.

Тому =(x_i+1)²+y_i²-R²>0 i вибираємо дiагональний пiксел (x_i+1)+(y_i-1)²-R², що збiгається з правилом (3). Перевірка компонент виразу ' дає (x_i+1)²+(y_i-1)²-R²=0, x_i²+(y_i-1)²-R²=0, x_i²+(y_i-1)²-R² 0.

Тому '=(x_i+1)²+(y_i-1)²-R²>0 i вибираємо дiагональний пiксел (x_i+1,y_i-1), що збiгається з правилом (4).

Таким чином, випадок, коли =0 можна обробляти як за випадком, коли <0, так i за випадком, коли >0.

Знайдемо рекурентнi спiввiдношення для реалiзацiї крокiв алгоритму. Розглянемо рiзнi випадки.

Горизонтальний крок m_H до пiкселя (x_i+1,y_i): x_i+1=x_i+1, y_i+1=y_i,

_i+1=(x_i+1 + 1) ² + (y_i+1 - 1) ²- R ²=x_i+1 ² + 2x_i+1 + 1 + (y_i-1) ² – R ²=

= (x_i+1) ² + (y _i-1)² – R ² + 2x_i+1 + 1= _i + 2x_i+1 + 1.

Дiагональний крок m_D до пiкселя (x_i+1,y_i-1):x_i+1=x_i+1, y_i+1=y_i-1,

_i+1=(x_i+1 + 1) ² + (y_i+1 - 1) ² – R ² = x_i+1 ² + 2x_i+1 + 1 + y_i+1² - 2y_i+1 + 1 – R ² =

= (x_i + 1)² + (y_i - 1)² – R ² + 2x_i+1 - 2y_i+1 + 2 = _i + 2x_i+1 - 2y_i+1 + 2.

Вертикальний крок m_V до пiкселя (x_i, y_i-1): x_i+1 = x_i, y_i+1 = y_i-1,

_i+1 = (x_i+1 + 1)² + (y_i+1 - 1)² – R ² = (x_i + 1)² + y²_i+1 - 2y_i+1 + 1 -R²=

= (x_i + 1)² + (y_i - 1)² – R ² - 2y_i+1 + 1 = _i - 2y_i+1 + 1.

Тепер ми можемо розглянути алгоритм Брезенхема побудови частини кола у першому квадрантi.