Графика и обработка изображений. Фракталы.

Рисование линий по алгоритму Брезенхейма.

В 1965 году Брезенхеймом был предложен простой целочисленный алгоритм для растрового построения отрезка.

При построении растрового изображения отрезка всегда выбирается ближайший по вертикали пиксел. При этом из двух точек A и B (см. рис.) выбирается та, которая ближе к исходной прямой (в данном случае выбирается точка А, так как а < b). Для этого вводится число d, равное (x2-x1)*(b-a). В случае если d > 0 значение y от предыдущей точки увеличивается на 1, а d на 2*(delta_y - delta_x). В противном случае значение y не изменяется, а значение d заменяется на 2*delta_y.

Пример на языке С (общий случай):

void Line(int x1, int y1, int x2, int y2, int color)
{
    int dx = abs(x2-x1);
    int dy = abs(y2-y1);
    int sx = x2>=x1?1:-1;
    int sy = y2>=y1?1:-1;

    if(dy <= dx)
    {
        int d=(dy<<1)-dx;
        int d1=dy<<1;
        int d2=(dy-dx)<<1;

        putpixel(x1, y1, color);

        for(int x=x1+sx, y=y1, i=1; i<=dx; i++, x+=sx)
        {
            if(d>0)
            {
                d+=d2;
                y+=sy;
            }
            else d+=d1;
            putpixel(x, y, color);
        }
    }
    else
    {
        int d=(dx<<1)-dy;
        int d1=dx<<1;
        int d2=(dx-dy)<<1;

        putpixel(x1, y1, color);

        for(int x=x1,y=y1+sy,i=1;i<=dy;i++,y+=sy)
        {
            if(d>0)
            {
                d+=d2;
                x+=sx;
            }
            else d+=d1;
            putpixel(x, y, color);
        }
    }
}

Пример на Паскале

Procedure Line(SX,SY,EX,EY:Integer);
Var t,dist,Xerr,Yerr,DX,DY,INCX,INCY:Integer;
Begin
 Xerr:=0; Yerr:=0;
 DX:=EX-SX;  DY:=EY-SY;
 INCX:=1; INCY:=1;
 if DX=0 then INCX:=0;
 if DX<0then INCX:=-1;
 if DY=0 then INCY:=0;
 if DY<0then INCY:=-1;
 DX:=ABS(DX); DY:=ABS(DY);
 if DX>DYThen Dist:=DX;
 else Dist:=DY;
 Xerr:=DX; Yerr:=DY;
 for t:=0 to dist do
  begin
   PutPixel(Sx,Sy,Color);
   Xerr:=Xerr+DX; Yerr:=Yerr+DY;
   if Xerr>Distthen
    begin
     Xerr:=Xerr-dist;
     Sx:=Sx+INCX;
    end;
   if Yerr>Distthen
    begin
     Yerr:=Yerr-dist;
     Sy:=Sy+INCY;
    end;
  end;
End;
	
	

Вверх по странице, к оглавлению и навигации.