2.1.2 Алгоритм Брезенхема побудови вiдрiзкiв
Брезенхем
[12] розробив алгоритм креслення вiдрiзка
спочатку для цифрових графопобудувачів,
але цей алгоритм можна використовувати
і для побудови вiдрiзка на растрових
приладах з ЕПТ. Алгоритм вибирає
оптимальні растровi координати для
представлення вiдрiзка. Пiд час роботи
алгоритму на кожному його кроцi змiнюється
лише одна з координат -- або
,
або
(залежно вiд кутового коефiцiєнту) --
вiдповiдна координата змiнюється на
одиницю. Змiна iншої координати (або на
нуль, або на одиницю) залежить вiд вiдстанi
мiж дiйсним розташуванням вiдрiзка i
найближчими координатами сiтки з
пiкселiв. Цю вiдстань будемо називати
похибкою.
Алгоритм
побудовано так, що потрiбно перевiряти
лише знак цієї похибки. На рисунку
наведено вiдрiзок у першому октантi,
тобто для відрізка з кутовим коефiцiєнтом
,
що знаходиться в межах від нуля до
одиниці
(
).
З рисунка бачимо, що у випадку, коли
і
відрізок проходить
через
точку
,
то
перетин вiдрiзка з прямою
розташовано ближче до прямої
,
нiж до прямої
.
Отже, точка растра
краще
наближає xiд вiдрiзку нiж точка
.
Якщо кутовий коефiцiєнт
,
то все буде навпаки. Для кутового
коефіцієнта
алгоритм Брезенхема вибирає точку
.
Розкладання в растр вiдрiзка з першого октанта.
// Кiнець (Xf,Yf) i початок (Xs,Ys) вiдрiзка не спiвпадають!
procedure Bresenham1(Xs,Ys,Xf,Yf,Color: integer);
var x,y,Dx,Dy: integer; e: real;
begin {Bresenham1}
// iнiцiалiзацiя змiнних
x:=Xs; y:=Ys;
Dx:=Xf-Xs; Dy:=Yf-Ys;
// iнiцiалiзацiя e з поправкою на половину вiдрiзка
e:=Dy/Dx-1/2;
for i:=1 to Dx
begin {for i}
Form1.Canvas.Pixels[x,y]:=Color;
While (e>=0) do
begin
y:=y+1; e:=e-1;
end;
x:=x+1; e:=e+Dy/Dx;
end; {for i}
end; {Bresenham1}
Алгоритм Брезенхема у тому виглядi, який був описаний ранiше, використовує арифметику чисел з плаваючою крапкою i діленням (для пiдрахування кутового коефiцiєнта i знаходження похибки). Швидкодію алгоритму можна збiльшити, якщо використати тільки арифметику цiлих чисел i позбутися дiлення. Змiна e на 2*e*Dx у попередньому алгоритмi дає наступний алгоритм.
Розклад у растр вiдрiзка з першого октанта з використанням цiлих змiнних.
// Kiнець (Xf,Yf) i початок (Xs,Ys) вiдрiзка не спiвпадають!
procedure Bresenham2(Xs,Ys,Xf,Yf,Color: integer);
var x,y,Dx,Dy,e: integer;
begin {Bresenham2}
// iнiцiалiзацiя змiнних
x:=Xs; y:=Ys; Dx:=Xf-Xs; Dy:=Yf-Ys;
// iнiцiалiзацiя e з поправкою на половину вiдрiзка
e:=2*Dy-Dx;
for i:=1 to Dx
begin {for i}
Form1.Canvas.Pixels[x,y]:=Color;
while (e>=0) do begin y:=y+1; e:=e-2*Dx; end;
x:=x+1; e:=e+2*Dy;
end; {for i}
end; {Bresenham2}
Але на практицi є потреба виводити вiдрiзки у будь-якому напрямку. Тому алгоритм потрiбно узагальнити таким чином, щоб за ним можна було виводити будь-якi вiдрiзки.
Загальний метод Брезенхема побудови в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].