Алгоритм Брезенхема розкладання в растр відрізка для першого октанта
Передбачається, що кінці відрізка (x1, y1) і (x2, y2) не збігаються
Integer - функція перетворення в ціле
x, y, Dx, Dy - цілі
е - дійсне
Ініціалізація змінних
x=x1
y=y1
Dx=x2-x1
Dy=y2-y1
Ініціалізація з виправленням на половину піксела
е=Dy/Dx-1/2
початок основного циклу
for i=1 to Dx
plot (x,y)
while (e=>0)
y=y+1
e=e-1
end while
x=x+1
e=e+Dy/Dx
next i
finish
6.2. Загальний алгоритм Брезенхема.
Щоб реалізація алгоритму Брезенхема була повною, необхідно розглянути побудову відрізків у всіх октантах. Модифікацію легко зробити, враховуючи в алгоритмі номер квадранта, в якому лежить відрізок і його кутовий коефіцієнт. Коли абсолютна величина кутового коефіцієнта більше 1, у постійно змінюється на одиницю, а критерій похибки Брезенхема використовується для ухвалення рішення про зміну величини x. Вибір постійно змінюваної координати (на +1 чи -1) залежить від квадранта (рис.4.1.).
Загальний алгоритм може бути оформлений у такому вигляді:
Узагальнений цілочисельний алгоритм Брезенхема для усіх квадрантів
Передбачається, що кінці відрізка (x1, y1) і (x2, y2) не збігаються.
Усі змінні вважаються цілими.
Sign - функція, що повертає -1, 0, 1 для від’ємного, нульового і додатнього аргумента відповідно.
Ініціалізація змінних
x=x1
y=y1
Dx=abs(x2-x1)
Dy=abs(y2-y1)
s1=Sign(x2-x1)
s2=Sign(y2-y1)
обмін значень Dx і Dy в залежності від кутового коефіцієнта нахилу відрізка
if Dy<Dx then
Temp=Dx
Dx=Dy
Dy=Temp
Обмін=1
else
Обмін=0
end if
ініціалізація e з виправленням на половину піксела
e=2*Dy-Dx
основний цикл
for i=1 to Dx
Plot(x,y)
while(e=>0)
if Обмін=1 then
x=x+s1
else
y=y+s2
end if
e=e-2*Dx
end while
if Обмін=1 then
y=y+s2
else
x=x+s1
end if
e=e+2*Dy
next i
finish
Рис.6.3. Розгляд випадків для узагальненого алгоритму Брезенхема.
Для ілюстрації розглянемо відрізок із точки (0, 0) у точку (-8, -4).
Початкові установки
x=0 y=0 Dx=8 Dy=4 s1=-1 s2=-1 Обмін=0 е=0
Таблиця 6.2
Результати роботи покрокового циклу
Рис.6.4. Результат роботи узагальненого алгоритму Брезенхема в третьому квадранті
ПОРЯДОК ВИКОНАННЯ РОБОТИ
1. Побудуйте декартову двовимірну систему координат, у якій максимальне значення по осях x i y було би близько 10 і початок координат був би по центру.
2. Розграфте площину побудови відрізків у вигляді сітки, на якій будуть будуватися піксели.
3. Побудуйте псевдовідрізок, який би з’єднував початок з кінцем відрізку.
4. Приведіть результат роботи алгоритму накреслення відрізку, методом Брезенхема, у якому би підсвічувалися піксели, або ж клітинки сітки.
5. Проаналізуйте результати.
ЗМІСТ ЗВІТУ
Звіт повинен містити:
1) назву роботи;
2) мету роботи;
3) короткий теоретичний вступ;
4) завдання до лабораторної роботи;
5) тексти розроблених і відлагоджених програм;
6) малюнки з реалізацією програми;
7) висновки.
ПРИКЛАД ПРОГРАМНОЇ РЕАЛІЗАЦІЇ
unit Unit1;
interface
uses
StdCtrls, Controls, ExtCtrls, Spin, Classes,forms,graphics,SysUtils;
type
b=array[1..2,1..2] of real;
TForm1 = class(TForm)
p: TPaintBox;
Label1: TLabel;
Label2: TLabel;
SpinEdit1: TSpinEdit;
Panel1: TPanel;
Panel2: TPanel;
r1: TRadioButton;
r2: TRadioButton;
procedure pPaint(Sender: TObject);
procedure pMouseDown(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
procedure pMouseMove(Sender: TObject; Shift: TShiftState; X,
Y: Integer);
procedure pMouseUp(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
procedure SpinEdit1Change(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure Panel2Click(Sender: TObject);
procedure Panel1Click(Sender: TObject);
procedure r2Click(Sender: TObject);
end;
var
Form1: TForm1;
pos:b;
DR:boolean=false;
temp_x,temp_y:real;
dx:integer;
lab:byte=6;
implementation
{$R *.DFM}
procedure draw_7;
var x,y,di,d:integer;
begin
x:=0;
y:=round(pos[2,2]);
di:=round(2*(1-y));
while y>0 do
begin
if form1.r2.Checked then
form1.p.Canvas.Rectangle(round(x), round(y),round(x+dx),round(y+dx))
else
begin
form1.p.Canvas.Pen.Width:= form1.p.Canvas.Pen.Width+10;
form1.p.Canvas.MoveTo(round(x),round(y));
form1.p.Canvas.LineTo(round(x),round(y));
orm1.p.Canvas.Pen.Width:= form1.p.Canvas.Pen.Width-10;
end;
if di<0 then
begin //1
d:=2*di+2*y-1;
if d<=0 then
begin //2
x:=x+dx;
di:=di+2*x+1;
end //2
else
begin //3
x:=x+dx;
y:=y+dx;
di:=di+2*x-2*y+2;
end //3
end //2
else
if di>0 then
begin //1a
d:=2*di+2*x-1;
if d<=0 then
begin //2a
x:=x+dx;
di:=di+2*x+1;
end //2a
else
begin //3a
y:=y-dx;
di:=di-2*y+1;
end // 3a
end //1a
else
if di=0 then
begin //1z
x:=x+dx;
y:=y+dx;
di:=di+2*x-2*y+2;
end //1z
end;
end;
procedure draw_6;
var pos_x,pos_y,pos_xx,pos_yy:real;
i:integer;
Dy,Dxx,l:real;
delta:boolean;
begin
form1.p.Canvas.Brush.Style:=bssolid;
if abs(pos[2,1]-pos[1,1])>=abs(pos[2,2]-pos[1,2]) then
L:=abs((pos[2,1]-pos[1,1])) else L:=abs(pos[2,2]-pos[1,2]) ;
dxx:=((pos[2,1]-pos[1,1])/l)*dx;
dy:=((pos[2,2]-pos[1,2])/l)*dx;
pos_x:=((pos[1,1]*dx));
pos_y:=((pos[1,2]*dx));
i:=1; form1.p.Canvas.Brush.Color:=cllime;
if form1.r2.Checked then
form1.p.Canvas.Rectangle(round(pos_x), round(pos_y), round(pos_x+dx),round(pos_y+dx))
else
begin
form1.p.Canvas.Pen.Width:= form1.p.Canvas.Pen.Width+10;
form1.p.Canvas.MoveTo(round(pos_x), round(pos_y));
form1.p.Canvas.LineTo(round(pos_x), round(pos_y));
form1.p.Canvas.Pen.Width:= form1.p.Canvas.Pen.Width-10;
end;
form1.p.Canvas.Brush.Color:=clblack;
while i<=l do
begin
pos_xx:=0;
pos_yy:=0;
delta:=false;
pos_x:=(pos_x+dxx);
pos_y:=(pos_y+dy);
form1.p.Canvas.Brush.Style:=bssolid;
form1.p.Canvas.Brush.Color:=cllime;
begin
if (round(pos_y) mod dx) <>0 then
begin
pos_yy:=round((pos_y) / dx);
if ((pos_Y-(pos_yy*DX))> dx/2) or ((pos_Y-(pos_yy*DX))*-1> (dx/2)) then
delta:=true;
if delta then
pos_yy:=pos_yy+1;
pos_yy:=pos_yy*dx;
pos_xx:=pos_x;
delta:=false;
end else pos_yy:=pos_y;
if (round(pos_x) mod dx) <>0 then
begin
pos_xx:=round((pos_x) / dx);
if ((pos_x-(pos_xx*DX))> dx/2) or ((pos_x-(pos_xx*DX))*-1> (dx/2)) then
delta:=true;
if delta then
pos_xx:=pos_xx+1;
pos_xx:=pos_xx*dx;
pos_yy:=pos_y;
delta:=false;
end else pos_xx:=pos_x; end;
if form1.r1.Checked then
begin
form1.p.Canvas.Pen.Width:= form1.p.Canvas.Pen.Width+10;
form1.p.Canvas.MoveTo(round(pos_xx), round(pos_yy));
form1.p.Canvas.LineTo(round(pos_xx), round(pos_yy));
form1.p.Canvas.Pen.Width:= form1.p.Canvas.Pen.Width-10;
end else
form1.p.Canvas.Rectangle(round(pos_xx), round(pos_yy),
round(pos_xx+dx),round(pos_yy+dx));
form1.p.Canvas.Brush.Color:=clblack;
inc(i);
end;
end;
procedure TForm1.pPaint(Sender: TObject);
var i:integer;
begin
p.Canvas.FillRect(clientrect); i:=0;
p.Canvas.Pen.Color:=clgray;
while i<=p.Width do
begin
p.Canvas.moveto(i,0);
p.Canvas.lineto(i,p.Height);
inc(i,dx);
end; i:=0;
while i<=p.height do
begin
p.Canvas.moveto(0,i);
p.Canvas.lineto(p.width,i);
inc(i,dx);
end;
end;
procedure TForm1.pMouseDown(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
begin
ppaint(form1);
DR:=true;
pos[1,1]:=x;
pos[1,2]:=y;
temp_x:=pos[1,1];
temp_y:=pos[1,2];
end;
procedure TForm1.pMouseMove(Sender: TObject; Shift: TShiftState; X,
Y: Integer);
begin
if dr then
begin
p.Canvas.Pen.Mode:=pmxor;
p.Canvas.MoveTo(round(pos[1,1]),round(pos[1,2]));
p.Canvas.lineTo(round(temp_x),round(temp_y));
p.Canvas.Pen.Color:=clyellow;
pos[2,1]:=x;
pos[2,2]:=y;
form1.Canvas.Font.Color:=cllime;
label1.Caption:=’X = ‘+IntToStr(Round(pos[2,1]/dx))+#10+#13+’Y = ‘+IntToStr(Round(pos[2,2]/dx));
p.Canvas.MoveTo(round(pos[1,1]), round(pos[1,2]));
p.Canvas.lineTo(round(x),round(y));
temp_x:=x;
temp_y:=y;
end;
end;
procedure TForm1.pMouseUp(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
var i:byte;
begin
i:=0;
if round(pos[1,1]) mod dx <>0 then
while round(pos[1,1]-i) mod dx <>0 do
inc(i);
pos[1,1]:=pos[1,1]-i;
i:=0;
if round(pos[1,2]) mod dx <>0 then
while round(pos[1,2]-i) mod dx <>0 do
inc(i);
pos[1,2]:=pos[1,2]-i ;
i:=0;
if round(x) mod dx <>0 then
while round(x-i) mod dx <>0 do
inc(i);
pos[2,1]:=x-i;
i:=0;
if round(y) mod dx <>0 then
while round(y-i) mod dx <>0 do
inc(i);
pos[2,2]:=y-i ;
pos[2,1]:=pos[2,1] / dx;
pos[2,2]:=pos[2,2] / dx;
pos[1,1]:=pos[1,1] / dx;
pos[1,2]:=pos[1,2] / dx;
dr:=false;
if (pos[1,1]<>pos[2,1]) or(pos[2,2]<>pos[1,2]) then
case lab of
6:draw_6;
7:draw_7;
end
end;
procedure TForm1.SpinEdit1Change(Sender: TObject);
begin
if SpinEdit1.Value>0 then
dx:=SpinEdit1.Value;
ppaint(form1);
end;
procedure TForm1.FormCreate(Sender: TObject);
begin
SpinEdit1.Value:=50;
dx:=SpinEdit1.value;
end;
procedure TForm1.Panel2Click(Sender: TObject);
begin
panel2.BevelOuter:=bvLowered;
panel2.Color:=clActiveBorder;
panel1.BevelOuter:=bvRaised;
panel1.Color:=clBtnFace;
form1.Caption:=’LAB 7';
lab:=7;
end;
procedure TForm1.Panel1Click(Sender: TObject);
begin
panel1.BevelOuter:=bvLowered;
panel1.Color:=clActiveBorder;
panel2.BevelOuter:=bvRaised;
panel2.Color:=clBtnFace;
form1.Caption:=’LAB 6';
lab:=6;
end;
procedure TForm1.r2Click(Sender: TObject);
begin
case lab of
6:draw_6;
7:draw_7;
end;
end;
end.