【问题描述】
在图像处理和计算机图形学中，我们经常需要在屏幕上画直线操作。考虑给定平面上两个点A(x1,y1)以及B(x2,y2)，我们的任务是实现在屏幕上画通过AB两点的直线，并找出这条直线通过的所有中间点的坐标。值得注意的是这里每个像素的坐标均为整数。
【示例】
x1<x2 并且 y1<y2
直线的斜率在[0,1]之间，我们从左下往右上方向画线
【原始方案】
看了上述描述，首先浮现在我们脑海的是最原始简单直接的方法，如下所示：
// A naive way of drawing linevoid naiveDrawLine(x1, x2, y1, y2){m = (y2 - y1)/(x2 - x1)for (x = x1; x <= x2; x++){// Assuming that the round function finds// closest integer to a given float.y = round(mx + c);print(x, y);}}
上述方案可以正常工作，但是效率很慢。而Bresenham算法则是为了避免float类型数据的乘法和加法操作，并且避免了每次在for循环里执行对(mx+c)的取整操作。
【Bresenham算法】
考虑到图像或者屏幕上像素的特殊性，(x,y)取值均为整数数据类型。基于此性质，我们可以每次沿着ｘ轴增加１，接着我们来选择下一个y，此时我们有两种选择：要么ｙ增加１要么ｙ依旧维持不变。换句话说我们沿直线方向从点(xk,yk)移动一个像素，下一个点我们有两个选择即(xk+1,yk)或者（xk+1,yk+1)。该过程如下图所示
如上图所示，我们沿着直线方向从左下角往右上角移动，从红色点(xk,yk)移动一个像素，那么直线上下一个点的位置可能会有两个选择，如图中绿色点所示，即(xk+1,yk+1)或者(xk+1,yk)．具体选择这两个点里的哪一个，需要对比直线在xk+1处的ｙ值距离这两个整数点那个距离更小．此时的伪代码逻辑如下：
void drawLine(x1,x2,y1,y2)x = x1y = y1print(x,y)while(x<x2){x = x + 1If we should increment Yy = y + 1print(x,y)}}
接着我们的问题转化为如何设计一个准则来判断每次x增加1，y的取值是否增加1。一个直观的判断准则如下：
将x'=x+1代入直线方程，计算此时y'
比较y'和y+0.5的大小，如果y'>y+0.5，则下一个点去(x+1,y+1)；否则取(x+1,y)即可
接着我们使用间接方法来实现上述过程：
不妨假设直线方程为 ｙ=mx+b，则每次ｘ增加１，那么ｙ将增加m
记变量 fraction 含义为从上一次y增加开始到现在的斜率的累计增加量，那么如果fraction>0.5,那么我们应该增加y
此时的伪代码逻辑如下：
void drawLine(x1,x2,y1,y2)x = x1y = y1print(x,y)fraction=0m = (y2-y1)/(x2-x1)while(x<x2){x = x + 1fraction += m> 0.5)= y + 1-= 1｝print(x,y)}}
【改进除法和浮点运算操作】
上述算法还涉及浮点运算和浮点数的比较，运行的依旧较慢．实际上，我们可以进一步优化来消除浮点运算，我们注意到
此时我们可以通过在上式左右两侧同乘（x2-x1）来消除除法运算;
同时为了避免斜率增加量和0.5的比较操作，我们可以同时乘以2．
汇总后，得到如下公式：
此时伪代码优化后如下：
void drawLine(x1,x2,y1,y2)x = x1y = y1print(x,y)fraction=0m = (y2-y1)*2while(x<x2){x = x + 1fraction += m> x2-x1)= y + 1-= 2*(x2-x1)｝print(x,y)}}
【完整的python代码实现】
# Assumptions :# 1) Line is drawn from left to right.# 2) x1 < x2 and y1 < y2# 3) Slope of the line is between 0 and 1.# We draw a line from lower left to upperdef bresenham(x1, y1, x2, y2):: A({},{}), B({},{})".format(x1,y1,x2,y2))pt_list = []x = x1y = y1pt_list.append((x,y))fraction = 0m = (y2-y1) * 2diff_x = x2 - x1while x < x2:x = x + 1fraction += mif fraction > diff_x:y = y+ 1fraction = fraction - 2*diff_xy)):",pt_list)if __name__ == '__main__':=0, y1=0, x2=4, y2=4)=0, y1=0, x2=4, y2=2)
