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 , ĝi povas havi 
 funkcio de kurbo povas esti unutona funkcio kaj ne kreskanta kaj ne malkreskanta.

 Algoritmo 
eta|200px|dekstra
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 
 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;

Kategorio:Geometriaj algoritmoj
Kategorio:Komputila grafiko