Algoritmo de Bresenham

El Vikipedio

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

Enhavo

1 Priskribo de algoritmo
- 1.1 Lemoj de algoritmo
- 1.2 Algoritmo
2 Realigo de algoritmo

[redakti] Priskribo de algoritmo

[redakti] 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)\leq1$

funkcio de kurbo povas esti unutona funkcio kaj ne kreskanta kaj ne malkaresanta.

[redakti] Algoritmo

Kurbo estas en intervalo $[x i, x k]$ . Unua rastrumero estas en punkto $P (x i; y i)$ Sekve oni estas nur du eblecoj: punkto $A (x i + 1; y i)$ kaj punkto $B (x i + 1; y i + 1)$ . Nun oni povas kalkuli kiu el punktoj estas pli proksime de reala loko de kurbo. Mezuro de ĝi estas:

$d i = d x ( | A C | - | C B | ) = 2 d y (x i - x o) - 2 d x (y i - y o) + 2 d y - d x$

kie:

d x = x k - x i

d y = y k - y i

C = (x 0, y 0)

Se $d i > 0$ punkto A estas proksime se ne punkto B estas.

Oni kalkulas:

$d i + 1 = 2 d y (x i + 1 - x 0) - 2 d x (y i + 1 - y 0) + 2 d y - d x$

kaj subtraho inter $d i + 1$ kaj $d i$ :

d i + 1 - d i = 2 d y (x i + 1 - x i) - 2 d x (h i + 1 - y i)

alinome:

d i + 1 = d i + 2 d y - 2 d x (y i + 1 - y i)

Se $d i > = 0$ oni selektas punkto B, do:

d i + 1 = d i + 2(d y - d x)

Kaj se $d i < 0$ oni selektas punkto A, do: $d i + 1 = d i + 2 d y$ Ĉar formulo estas rikura do oni restas kalkuli $d 0$ :

d 0 = 2 d y - d x

[redakti] Realigo de algoritmo

[redakti] Java

[redakti] 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);
         }
     }
 }

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

Kategorioj: Komputilo | Komputila grafiko

See also ebooksgratis.com: no banners, no cookies, totally FREE.