Algoritmo de Bresenham

Ilustraĵo pri la algoritmo de Bresenham

Algoritmo de Bresenham estas algoritmo kiu kalkulas plej bonan aproksimon de kurbo en 2D spaco.

Priskribo de algoritmo

Lemoj de algoritmo

• Angulo inter tanĝanto kaj akso OX estas malpli granda ol 45°
  • Se kurbo ne havas funkcion en formo $y=f(x)$, ĝi povas havi $0<f'(x)\leq 1$
• funkcio de kurbo povas esti unutona funkcio kaj ne kreskanta kaj ne malkreskanta.

Algoritmo

Kurbo estas en intervalo $[x_{i},x_{k}]$. Unua rastrumero estas en punkto $P(x_{i};y_{i})$ Sekve estas nur du ebloj: punkto $A(x_{i}+1;y_{i})$ kaj punkto $B(x_{i}+1;y_{i}+1)$. Nun oni povas kalkuli, kiu el ambaŭ punktoj estas pli proksima al la reala loko de kurbo. Mezuro por la distanco estas:

$d_{i}=dx(|AC|-|CB|)=2dy(x_{i}-x_{o})-2dx(y_{i}-y_{o})+2dy-dx$

kie:

$dx=x_{k}-x_{i}$

$dy=y_{k}-y_{i}$

$C=(x_{0},y_{0})$

Se $d_{i}>0$ punkto A estas proksima, se ne punkto B estas.

Oni kalkulas:

$d_{i+1}=2dy(x_{i+1}-x_{0})-2dx(y_{i+1}-y_{0})+2dy-dx$

kaj subtraho inter $d_{i+1}$ kaj $d_{i}$:

$d_{i+1}-d_{i}=2dy(x_{i+1}-x_{i})-2dx(h_{i+1}-y_{i})$

alinome:

$d_{i+1}=di+2dy-2dx(y_{i+1}-y_{i})$

Se $d_{i}>=0$ oni elektas punkton B, do:

$d_{i+1}=d_{i}+2(dy-dx)$

Kaj se $d_{i}<0$ oni elektas punkton A, do: $d_{i+1}=d_{i}+2dy$ Ĉar formulo estas rikura do restas kalkulenda $d_{0}$:

$d_{0}=2dy-dx$

Realigo de algoritmo

C/C++

 // 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);
         }
     }
 }

Pascal

 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;