直線算法(Bresenham)

 原理：（摘自百度百科）

     Bresenham算法是計算機圖形學領域使用最廣泛的直線掃描轉換方法。

　　其原理是：

　　過各行、各列像素中心構造一組虛拟網格線，按直線從起點到終點的

　　順序計算直線各垂直網格線的交點，然後确定該列像素中與此交點最近

　　的像素。

　　該算法的優點在于可以采用增量計算，使得對于每一列，隻要檢查一個誤差項

　　的符号，就可以确定該列所求的像素。以下為PASCAL程式實作

program b_line;

uses crt,graph;

var

  GD,GM:INTEGER;

procedure bresenham(x1,y1,x2,y2:integer);

  i,dx,dy,e:integer;

  x,y:integer;

  procedure swap(var x,y:integer);

  var

    temp:integer;

  begin

    temp :=x;

    x:=y;

    y:=temp;

  end;

begin

  setbkcolor(0);

  if abs(x1-x2)>abs(y1-y2) then

    if x1>x2 then

    begin

      swap(x1,x2);   swap(y1,y2);

    end;

    dx:=x2-x1;  dy:=y2-y1;

    e:=2*dy-dx;

    for i:=1 to dx do

      putpixel(x1,y1,white);

      if e>0 then

      begin

        inc(y1);

        e:=e-dx-dx;

      end;

      e:=e+dx+dx;

      x1:=x1+1;

  end

  else

    if y1>y2 then

      swap(y1,y2);  swap(x1,x2);

    dx :=x2-x1;

    dy:=y2-y1;

    e:=dx+dx-dy;

    for i:=1 to dy do

      putpixel(x1,y1,1);

        inc(x1);

        e:=e-dy-dy;

      e:=e+dy+dy;

      y1:=y1+1;

end;

  GD :=DETECT;

  INITGRAPH(GD,GM,'D:\TP\BGI');

  BRESENHAM(100,50,50,100);

  Repeat until Keypressed;

  closegraph;

END.

另附turbo c程式

#include <graphics.h>

/***********************Declare Grobal Valiables***************/

int gdriver,gmode;

/***********************Declare Functions**********************/

void graphic_mode_init();/*初始化圖形模式*/

void grahic_mode_close();/*退出圖形模式*/

void bresenham_line(int x1,int y1,int x2,int y2,int color);/*Bresenham算法繪制直線*/

/***********************Define*********************************/

void graphic_mode_init() /*初始化圖形模式*/

{

detectgraph(&gdriver,&gmode);

initgraph(&gdriver,&gmode,"E:\\turboc2");

setbkcolor(0);

sleep(2);

}

void grahic_mode_close()/*退出圖形模式*/

closegraph();

void bresenham_line(int x1,int y1,int x2,int y2,int color)/*Bresenham算法繪制直線*/

int xa,ya,xb,yb,i,dx,dy,pk,towdx,towdy,towdydx,t;

if(x1 > x2)

    {xa = x2;ya = y2;xb = x1;yb = y1;}

else

    {xa = x1;ya = y1;xb = x2;yb = y2;}

dx = xb - xa;

dy = yb - ya;

if(dy >= 0)

    towdy = dy * 2;

    towdx = dx * 2;

       towdydx = (dy - dx)*2;

       putpixel(xa,ya,color);

       if(abs(dx) >= abs(dy))

    {

        pk = 2 * dy - dx;

     for(i = 0;i < abs(dx);i++)

     {

      xa++;

      if(pk > 0)

       {ya++;pk += towdydx;}

      else

       {pk += towdy;}

      putpixel(xa,ya,color);

     }

    }

    else

     putpixel(xa,ya,color);

     pk = 2 * dx + 2 * dy - 1;

     for(i = 0;i < abs(dy);i++)

      ya++;

       {xa++;pk -= towdydx;}

       {pk += towdx;}

    putpixel(xa,ya,color);

    towdy = (-1)*(dy * 2);

    towdx = (-1)*(dx * 2);

    towdydx = (-1)*(dx + dy)*2;

    if(abs(dx) >= abs(dy))

     pk =    (-1)*dx;

       {ya--;pk += towdydx;}

     pk = 2*(dx + dy) + 1;

     putpixel(xb,yb,color);

      yb++;

       {xb--;pk -= towdydx;}

       {pk -= towdx;}

      putpixel(xb,yb,color);

/***********************Test***********************************/

main()

graphic_mode_init();

bresenham_line(30,300,50,15,3);

setcolor(3);

/*line(30,300,50,15,3);*/

getch();

grahic_mode_close();