Saltu al enhavo

Algoritmo de Bresenham

El Vikipedio, la libera enciklopedio
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

[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;