Algoritmo de Bresenham
Aspekto
Algoritmo de Bresenham estas algoritmo kiu kalkulas plej bonan aproksimon de kurbo en 2D spaco.
Priskribo de algoritmo
[redakti | redakti fonton]Lemoj de algoritmo
[redakti | redakti fonton]- Angulo inter tanĝanto kaj akso OX estas malpli granda ol 45°
- Se kurbo ne havas funkcion en formo , ĝi povas havi
- funkcio de kurbo povas esti unutona funkcio kaj ne kreskanta kaj ne malkreskanta.
Algoritmo
[redakti | redakti fonton]Kurbo estas en intervalo . Unua rastrumero estas en punkto Sekve estas nur du ebloj: punkto kaj punkto . Nun oni povas kalkuli, kiu el ambaŭ punktoj estas pli proksima al la reala loko de kurbo. Mezuro por la distanco estas:
- kie:
Se punkto A estas proksima, se ne punkto B estas.
Oni kalkulas:
kaj subtraho inter kaj :
alinome:
Se oni elektas punkton B, do:
Kaj se oni elektas punkton A, do: Ĉar formulo estas rikura do restas kalkulenda :
Realigo de algoritmo
[redakti | redakti fonton] // x1 , y1 −
// x2 , y2 −
void BresenhamLine(const int x1, const int y1, const int x2, const int y2) {
//
int d, dx, dy, ai, bi, xi, yi;
int x = x1, y = y1;
//
if (x1 < x2) {
xi = 1;
dx = x2 - x1;
} else{
xi = -1;
dx = x1 - x2;
}
//
if (y1 < y2) {
yi = 1;
dy = y2 - y1;
} else {
yi = -1;
dy = y1 - y2;
}
//
glVertex2i(x, y);
//
if (dx > dy) {
ai = (dy - dx) * 2;
bi = dy * 2;
d = bi - dx;
//
while (x != x2) {
//
if (d > 0) {
x += xi;
y += yi;
d += ai;
} else {
d += bi;
x += xi;
}
glVertex2i(x, y);
}
//
} else {
ai = ( dx - dy ) * 2;
bi = dx * 2;
d = bi - dy;
//
while (y != y2) {
//
if (d > 0){
x += xi;
y += yi;
d += ai;
} else{
d += bi;
y += yi;
}
glVertex2i(x, y);
}
}
}
Procedure Linia(x1,y1,x2,y2,Kolor : integer);
var c,i : integer;
ŝ,sy,y,x : real;
begin
{ if x2<x1 then {ĉi tiu kondiĉo ne povas krei '''linio kiu aspektas kiel kreskanta funkcio'''!!!}
begin
c:=x1;
x1:=x2;
x2:=c;
end;
if y2<y1 then
begin
c:=y2;
y2:=y1;
y1:=c;
end; }
if (x2-x1)>(y2-y1) then
begin
sy:=(y2-y1)/(x2-x1);
y:=y1;
for i:=x1 to x2 do
begin
putpixel(i,round(y),Kolor);
y:=y+sy;
end;
end else
begin
sx:=(x2-x1)/(y2-y1);
x:=x1;
for i:=y1 to y2 do
begin
putpixel(round(x),i,Kolor);
x:=x+sx;
end;
end;
end;