转自：http://armfly.5d6d.com/thread-19-1-5.html

Bresenham算法的优点是：
1、不必计算直线之斜率，因此不做除法；
2、不用浮点数，只用整数；
3、 只做整数加减法和乘2运算，而乘2运算可以用硬件移位实现。

Bresenham算法速度很快，并适于用硬件实现。基本上 Bresenham画线算法的思路如下：
// 假设该线段位于第一象限内且斜率大于0小于1,设起点为(x1,y1),终点为(x2,y2).
// 根据对称性,可推导至全象限内的线段.
1、画起点(x1,y1).
2、准备画下个点。x坐标增1，判断如果达到终 点，则完成。否则，由图中可知,下个要画的点要么为当前点的右邻接点,要么是当前点的右上邻接点.
2.1、如果线段ax+by+c=0与x=x1+1的交点的y坐标大于M点的y坐标的话,下个点为U(x1+1,y1+1)
2.2、否则,下个点为B(x1+1,y1+1)
3、画点(U或者B).
4、跳回第2步.
5、结 束.

这里需要细化的是怎么判断下个要画的点为当前点的右邻接点还是当前点的右上邻接点。
设线段方 程：ax+by+c=0(x1令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>0时候,即下个点为U。
反之，下个点为B。
代入a/b，则Sub1 = dy/dx-0.5。
因为是个循环中都要判断Sub，所以得求出循环下的Sub表达式，我们可以求出Sub的差值的表达式。下面求 x=x1+2时的Sub，即Sub2
1、如果下下个点是下个点的右上邻接点，则
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 - (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可以细化如下：

PS：一般优化
为避免小数转整数以及除法运算，由于Sub只是用来进行正负判断，所以可以令Sub = 2*dx*Sub = 2dy-dx，则
相应的DSub = 2dy - 2dx或2dy。
思考1:如果Sub = 0时，会产生取两个点都可以的问题。这个问题还没深入。

一、实验目标：用Bresenham算法绘画直线。

二、算法描述：
设：p1=2dy-dx
综述上面的推导，第1a象限内的直线Bresenham算法思想如下：
1、画起点(x1,y1), dx=x2-x1,dy=y2-y1,计算误差初值
p1=2dy-dx; i=1；
2、求直线的下一点位置： x(i+1)=x(i+1)；
if p(i)>0 则y(i+1)=y(i+1)；否则y(i+1)= y(i)；
3、画点(x(i+1),y(i+1))；
4、求下一个误差p(i+1)；
if p(i)>0 则 p(i+1)= p(i)+2dy-2dx;
否则 p(i+1)=p(i)+2dy；
5、i=i+1; if i否则end
Bresenham算法的优点是：
1、不必计算直线之斜率，因此不做除法；
2、不用浮点数，只用整数；
3、只做整数加减法和乘2运算，而乘2运算可以用硬件移位实现。
Bresenham算法速度很快，并适于用硬件实现。

三. 程序源码：

51

}