u
Pu(xi?1,yi?1)Q
M(xi?1,yi?0.5)P(xi,yi)
Pd(xi?1,yi)
假定0≤k≤1，由于x是最大位移方向，因此每次在x方向上加1，y方向上或加1，或加0.假设当前点是P(xi,yi)，则下一个点在P,yi?1)与Pd(xi?1,yi)u(xi?1中选一。以M表示P即M(xi?1,yi?0.5)。又设Q是理想直线与垂u与Pd的中点，直直线x=xi+1的交点；显然，若M在Q的下方，则P,yi?1)离直线近，u(xi?1应取为下一个像素；否则取Pd(xi?1,yi)。
如前所述，直线方程为F(x,y)=y-kx-b。欲判断Q在M上方还是下方，只要把M代入F(x,y)，并判断它的符号即可。
构造判别式如下：
di?F(xM,yM)?F(xi?1,yi?0.?5)yi?0.?k5ix?( ?b当di<0时，M在直线下方，故应取Pu。当di>0时，则应取正右方的Pd。当
di=0时，二者一样合适，可以随便取一个。我们约定取Pd，即
?y?1(di?0)y???y(di?0)当di<0时，取右上方像素Pu，欲判断再下一个像素应取哪一个，应计算
di?1?F(xi?2,yi?1.5) ?yi?1.5?kx(i?2?b)
?yi?1.5?kx(?1b)?k i? ?di?1?k
此时，di的增量为1-k。
当di≥0时，取正右方像素Pd，要判断再下一个像素应取哪一个，应计算
di?1?F(xi?2,yi?0.5) ?yi?0.5?kx(i?2?b)
?yi?0.5?kx(?1b)?k i? ?di?k
此时，di的增量为-k。
- 3 -
下面计算di的初值。显然，直线的第一个像素P0(x0,y0)在直线上，因此相应的di的初始值计算如下：
d0?F(x0?1,y0?0.5) ?y0?0.5?k(x0?2)?b ?y0?kx0?b?k?0.5
?k ?0.5由于我们使用的只是di的符号，因此可以用2di?x代替di来摆脱小数。此时算法只涉及整数运算。这样，0≤k≤1时，Bresenham算法的绘图过程如下：
① 输入直线的两端点P； （P1X1，Y1）0X，Y0）和（② 计算初始值?x，?y，d??x?2?y,x?X0,y?Y0；
③ 绘制点(x,y)。判断d的符号，若d<0，则(x,y)更新为（x+1，y+1），d更新为d+2?x-2?y；否则(x,y)更新为（x+1，y），d更新为d-2?y； ④ 当直线没有画完时，重复步骤③，否则结束。
0≤k≤1时Bresenham算法绘制直线的程序（仅包含整数运算）如下： void MidBresenhamLine(int x0,int y0,int x1,int y1,int color) {
int dx,dy,UpIncre,DownIncre,x,y; if(x0>x1)
{
x=x1;x1=x0;x0=x; y=y1;y1=y0;y0=y; }
x=x0;y=y0; dx=x1-x0;dy=y1-y0; d=dx-2*dy;
UpIncre=2*dx-2*dy; DownIncre=-2*dy; while(x<=x1) {
putpixel(x,y,color); x++;
- 4 -
if(d<0) { y++; d+= UpIncre; }
else d+=DownIncre;
} }
4.2改进Bresenham算法
虽然中点Bresenham算法是一种效率很高的算法，但也还有改进的余地。当然，其基本原理仍然是每次在最大位移方向上走一步，二另一个方向上走步是不走步取决于误差项的判别。为叙述简单，同样定0≤k≤1的直线段（k=?y/?x），其端点为P。 （）和（P，Y）0X，Y01X11 于是这样考虑该直线段的绘制：过各行、各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，交点与网格线之间的误差为di，根据di确定该列网格中与此交点最近的像素点。当di>0.5时，直线更接近于像素点P,yi?1)；当di<0.5时，更接近于像素点Pd(xi?1,yi)；u(xi?1当di=0.5时，与上述两像素点一样接近，约定取Pd(xi?1,yi)，即
xi?1?xi?1 ???yi?1(di?0.5)? ?yi?1??y(d?0.5)i?i?
?y)d?d?k(k?i其中的关键在于误差项di，它的初始值为0，每走一步有 i?1?x一旦y方向上走了一步，就把它减去1（此时可能出现负误差，这表明交点在所取网格点之下）。为方便计算，令ei?di?0.5。则当ei>0时，下一像素的y坐标增加1；否则，下一像素的y坐标不增，即有 ?xi?1?xi?1??yi?1(ei?0) ?y??i?1?y(e?0)i?i ?此时，ei的初值为-0.5，每走一步有ei?1?ei?k。当ei>0时，将ei减1.
改进的Bresenham算法还有一个缺点：在计算直线斜率与误差时，要用到小
- 5 -
数与除法，不利于硬件实现。因此改进如下：由于算法中只用到误差项的符号，于是可以用2e?x来替换e。这样就能获得整数Bresenham算法且可避免除法。其算法步骤如下：
① 输入直线的两端点P； （P1X1，Y1）0X，Y0）和（②计算初始值?x，?y，e = ??x，x?X0,y?Y0 ③绘制点(x,y)。
④e更新为e+2?y。判断e的符号，若e>0，则(x,y)更新为（x+1，y+1），同时将e更新为e-2?x；否则(x,y)更新为（x+1，y）； ⑤当直线没有画完时，重复步骤③，否则结束。
0≤k≤1时改进的Bresenham算法绘制直线的程序如下： void BresenhamLine(int x0,int y0,int x1,int y1,int color) {
int x,y,dx,dy,e; dx=x1-x0; dy=y1-y0; e=-dx;x=x0;y=y0; while(x<=x1)
{
Putpixel(x,y,color); x++; e=e+2*dy; if(e>0) { y++; e=e-2*dx; } }
}
- 6 -
5、圆的Bresenham算法原理
给定圆心在原点，半径为R的圆，其方程为x2?y2?R2。构造函数
222。对于圆上的点，有F(x,y)=0；对于圆外的点，F(x,y)>0;而F(x,y)?x?y?R2对于圆内的点，F(x,y)<0.
?0,R?x?这里只考虑如下图所示的第一象限内 ?2???(R,R )的八分八分之一圆弧。此时中点Bresenham画圆算法要从点（0，R）到点顺时针地确定最佳逼近于该圆弧的像素序列。
22对于该圆弧，由于最大位移方向为x，因此其基本原理是：每次沿x方向上走一步，而y方向上或减1，或减0。如图所示，假定当前与圆弧最近的像素点已确定为P (xi,yi)，那么，下一候选像素点只能是正右方的Pu(xi?1,yi)和右下方的P,yi?1)。到底选取哪一个候选点依旧用中点进行判别。 d(xi?1y y y=x R x 八分之一圆弧
O 中点Bresenham画圆的原理 P Pu M Pdx
假设M是P,yi?0.5)。则当F(xM,yM)<0时，Mu和Pd的中点，即有M(xi?1在圆内，此时Pu离圆弧更近，应取Pu(xi?1,yi)为下一像素点。当F(xM,yM)>0，说明Pd离圆弧更近，应取P,yi?1)。当F(xM,yM)=0时，在Pd(xi?1u和Pd之中随便选取一个即可，约定取Pd。
构造判别式
di?F(xM,yM)?F(xi?1,yi?20.?5)x(i??1)y(2i?2 0.?R5)当di<0，下一点取P,yi?1)。 u(xi?1,yi)；当di≥0时,下一点取Pd(xi?1 - 7 -