Bresenham画线算法

1、以前看到Bresenham画线算法，直接拿来用，没有去推导它,近日,参考一些资料,特整理其算法推导过程如下。各位大虾如果知道其细节，赶紧闪过，不用浪费时间了。基本上Bresenham画线算法的思路如下: / 假设该线段位于第一象限内且斜率大于0小于1,设起点为(x1,y1),终点为(x2,y2)./ 根据对称性,可推导至全象限内的线段.1.画起点(x1,y1).2.准备画下个点。x坐标增1，判断如果达到终点，则完成。否则，由图中可知,下个要画的点要么为当前点的右邻接点,要么是当前点的右上邻接点.(即中点)3.画点(U或者B).4.跳回第2步.5.结束.这里需要细化的是怎么判断下个要画的点为当前

2、点的右邻接点还是当前点的右上邻接点.设线段方程：ax+by+c=0(x1<x<x2,y1<y<y2)令dx=x2-x1,dy=y2-y1则：斜率-a/b = dy/dx.从第一个点开始，我们有F(x,1,y1) = a*x1+b*y1+c=0下面求线段ax+by+c=0与x=x1+1的交点:由a*(x1+1)+b*y+c = 0, 求出交点坐标y=(-c-a(x1+1)/b所以交点与M的y坐标差值Sub1 = (-c-a(x1+1)/b - (y1+0.5) = -a/b-0.5，即Sub1的初始值为-a/b-0.5。则可得条件当 Sub1 = -a/b-0.5>

3、0时候,即下个点为U.反之,下个点为B.代入a/b,则Sub1 = dy/dx-0.5.因为是个循环中都要判断Sub,所以得求出循环下的Sub表达式,我们可以求出Sub的差值的表达式.下面求x=x1+2时的Sub，即Sub21.如果下下个点是下个点的右上邻接点，则Sub2 = (-c-a(x1+2)/b - (y1+1.5) = -2a/b - 1.5故Sub差值Dsub = Sub2 - Sub1 = -2a/b - 1.5 - (-a/b-0.5) = -a/b - 1.代入a/b得Dsub = dy/dx -1;2.如果下下个点是下个点的右邻接点，Sub2 = (-c-a(x1+2)/b

4、 - (y1+0.5) = -2a/b - 0.5故Sub差值Dsub = Sub2 - Sub1 = -2a/b - 0.5 - (-a/b-0.5) = -a/b. 代入a/b得Dsub = dy/dx;于是，我们有了Sub的初始值Sub1 = -a/b-0.5 = dy/dx-0.5,又有了Sub的差值的表达式Dsub = dy/dx -1 （当Sub1 > 0）或 dy/dx（当Sub1 < 0）.细化工作完成。于是pcode可以细化如下： / Pcode for Bresenham Line/ By SoRoManx=x1;y=y1;dx = x2-x1;dy = y2-

5、y1;Sub = dy/dx-0.5; / 赋初值，下个要画的点与中点的差值DrawPixel(x, y); / 画起点while(x<x2) x+;  if(Sub > 0) / 下个要画的点为当前点的右上邻接点   Sub += dy/dx - 1; /下下个要画的点与中点的差值  y+; / 右上邻接点y需增1  else/ 下个要画的点为当前点的右邻接点   Sub += dy/dx;   / 画下个点DrawPixel(x,y);PS:一般优化：为避免小数转整数以

6、及除法运算，由于Sub只是用来进行正负判断，所以可以令Sub = 2*dx*Sub = 2dy-dx,则相应的DSub = 2dy - 2dx或2dy.思考1:如果Sub = 0时，会产生取两个点都可以的问题。这个问题还没深入。/*/*液晶屏 点阵屏 绘制直线函数 采用BresenHam算法void draw_line(uint x1,uint y1,uint x2,uint y2,uint linecolor )int temp;int x,y;int dx,dy,e;if(x1>x2)/交换坐标 保证x1始终是起点   temp=x1;x1=x2;x2=temp;

7、   temp=y1;y1=y2;x1=temp;dx=x2-x1;dy=y2-y1;x=x1;y=y1;if(dy=0)/斜率为0   for(temp=x1;temp<x2;temp+)   draw_point(temp,y1,linecolor);if(dy>0)/斜率小于0   if(dy<dx)/斜率大于-1       e=-dx;    for (temp=0; temp<dx; temp+)&#

8、160;        draw_point (x, y, linecolor);        x+;     e=e+2*dy;     if (e>=0)            y+; e=e-2*dx;         

9、60;        else /斜率小于-1       e=-dy;    for (temp=0; temp<dy; temp+)         draw_point (x, y, linecolor);        y+;      e=e+2*dx;  

10、60;  if (e>=0)            x+; e=e-2*dy;               if(dy<0)/正斜率   dy=-dy;   if(dy<dx)/斜率小于1       e=-dx;    for (temp=0; te

11、mp<dx; temp+)         draw_point (x, y, linecolor);        x+;      e=e+2*dy;     if (e>=0)            y-; e=e-2*dx;                  else       e=-dy;    for (temp=0; temp<dy; temp+)         draw_point (x, y, linecolor);        y-;