直线的Bresenham算法

　　它也是采用递推步进的办法，令每次最大变化方向的坐标步进一个象素，同时另一个方向的坐标依据误差判别式的符号来决定是否也要步进一个象素。

　　我们首先讨论m=△y/△x，当0≤m≤1且x₁2时的Bresenham算法。从DDA直线算法可知这些条件成立时，公式(2-2)、(2-3)可写成：

　　有两种Bresenham算法思想，它们各自从不同角度介绍了Bresenham算法思想，得出的误差判别式都是一样的。

　　由于显示直线的象素点只能取整数值坐标，可以假设直线上第i个象素点坐标为(x_i，y_i)，它是直线上点(x_i，y_i)的最佳近似，并且x_i=x_i(假设m<1），如下图所示。那么，直线上下一个象素点的可能位置是(x_i+1，y_i)或(x_i+1，y_i+1)。

　　这两个距离差是

　　因此只要利用(d₁-d₂)的符号就可以决定下一个象素点的选择。为此，我们进一步定义一个新的判别式：

　　式(2-11)中的△x=(x₂-x₁)>0，因此p_i与(d₁-d₂)有相同的符号；

　　这里△y=y₂-y₁，m=△y/△x；c=2△y+△x(2b-1)。

　　下面对式(2-11)作进一步处理，以便得出误差判别递推公式并消除常数c。

　　将式(2-11)中的下标i改写成i+1，得到：

　　将式(2-12)减去(2-11)，并利用x_i+1=x_i+1，可得：

　　再假设直线的初始端点恰好是其象素点的坐标，即满足：

　　由式(2-11)和式(2-14)得到p₁的初始值：

　　这样，我们可利用误差判别变量，得到如下算法表示：

	初始 　　　 p1=2△y-△x	(2－16)
	当pi≥0时： yi+1=yi+1, 　　　　　　xi+1=xi+1， 　　　　　　pi+1=pi+2(△y-△x)
	否则：　　　yi+1=yi, 　　　　　　xi+1=xi+1， 　　　　　　pi+1=pi+2△y

　　从式(2-16)可以看出，第i+1步的判别变量p_i+1仅与第i步的判别变量p_i、直线的两个端点坐标分量差△x和△y有关，运算中只含有整数相加和乘2运算，而乘2可利用算术左移一位来完成，因此这个算法速度快并易于硬件实现。

　　条件：0≤m≤1且x₁<x₂

　　1、输入线段的两个端点坐标和画线颜色：x1，y1，x2，y2，color；
　　2、设置象素坐标初值：x=x1，y=y1；
　　3、设置初始误差判别值：p=2·Δy-Δx；
　　4、分别计算：Δx=x2-x1、Δy=y2-y1；
　　5、循环实现直线的生成：
　　　for(x=x1；x<=x2；x++)
　　　{ SetPixel(dc,x,y,color) ；
　　　　if(p>=0)
　　　　　{ y=y+1；
　　　　　　p=p+2·(Δy-Δx)；
　　　　　}
　　　　else
　　　　　{ p=p+2·Δy；
　　　　　}

　　　}

四，Bresenham算法程序实现

依然在vs2010环境下用基于MFC的对话框实现

void CBresenhamDlg::Bresham(int x1, int y1, int x2, int y2, int color)
{
	CPaintDC dc(this);
	int dx,dy,d;
	int x=x1,y=y1;
	dx = abs(x2-x1);
	dy = abs(y2-y1);
	d = 2*dy-dx;
	for (x1;x<=x2;x++)
	{
		SetPixel(dc,x,y,color);
		if (d>0)
		{
			y++;
			d=d+2*(dy-dx);
		}
		else{
			d=d+2*dy;
		}
	}
}

不过这个程序局限性太大，只有在满足条件：0≤m≤1且x₁<x_{2时才能画线，所以我们要对它做一些改进。}