直线的Bresenham算法

2.1.2 直线的Bresenham算法

^{本算法由Bresenham在1965年提出。设直线从起点（x1, y1）到终点（x2, y2）。直线可表示为方程y=mx+b。其中}

^{b = y1 - m * x1,} 电脑爱好者网 ]p'I.u-es'V

^{m =}

^{我们的讨论先将直线方向限于1a象限（图2.1.1）在这种情况下，当直线光栅化时，x每次都增加1个单元，即}

^xi+1=xi+1

^{而y的相应增加应当小于1。为了光栅化，yi+1只可能选择如下两种位置之一（图2.1.2）。}电脑爱好者网z,F(o/rEz:y-i Ph*^ X

电脑爱好者网lE#I+yE.V*@5p#e

图2.1.2

^{图2.1.2 yi+1的位置选择yi-1=yi 或者 yi+1=yi+1}电脑爱好者网$cm(xPL

^{选择的原则是看精确值y与yi及yi+1的距离d1及d2的大小而定。计算式为：}电脑爱好者网l Vd)UI!j z2S(O

^{y=m(xi+1)+b (2.1.1)}电脑爱好者网J2Ac0O0Z6B.VKs

^{d1=y-yi (2.1.2)}

T3Ed5`;a&KDq+n0

^{d2=yi+1-y (2.1.3)}电脑爱好者网YOn0Yw"Z%oZ

^{如果d1-d2>0，则yi+1=yi+1，否则yi+1=yi。因此算法的关键在于简便地求出d1-d2的符号。将式（2.1.1）、（2.1.2）、（2.1.3）代入d1-d2，得}电脑爱好者网s*~F,Tp UL6[5Y.Dk

^{d1-d2=2y-2yi-1=2(xi+1)-2yi+2b-1}电脑爱好者网1]x0}^9zL0f

^{用dx乘等式两边，并以Pi=dx(d1-d2)代入上述等式，得}电脑爱好者网J w;Ba$J

^{Pi=2xidy-2yidx+2dy+dx(2b-1) (2.1.4)}电脑爱好者网sZ6}0I1lfgo.u^

^{d1-d2是我们用以判断符号的误差。由于在1a象限，dx总大于0，所以Pi仍旧可以用作判断符号的误差。Pi-1为：}

^{Pi+1=Pi+2dy-2dx(yi+1-yi) (2.1.5)}

^{误差的初值P1，可将x1, y1，和b代入式（2.1.4）中的xi, yi而得到：}电脑爱好者网0S;}-PtS)}E cw

^P1=2dy-dx

^{综述上面的推导，第1a象限内的直线Bresenham算法思想如下：}电脑爱好者网(@E}~(Z+xd-N3I jB

^{1、画点(x1, y2); dx=x2-x1; dy=y2-y1；}

itC]}y5c1~0

^{计算误差初值P1=2dy-dx; i=1；}电脑爱好者网r u$\/Bi*T#\

^{2、求直线的下一点位置：}电脑爱好者网Qz7h|7sEW'[

^xi+1=xi+1；电脑爱好者网+W
R1L$^]q_l

^{if Pi>0 则yi+1=yi+1；}

6I-\e3H2M7_6Y0

^{否则yi+1=yi；}电脑爱好者网+dz? p?

^{3、画点（xi+1, yi-1）；}电脑爱好者网5GzA#\aB3E5I:j(c

^{4、求下一个误差Pi+1；}电脑爱好者网fv?C%s"z:W'[

^{if Pi>0 则Pi+1=Pi+2dy-2dx;}电脑爱好者网)N0R'yeq8q&_4Y8pH

^{否则Pi+1=Pi+2dy；}

q#A(E0t.g2a#J0U@L0

^{5、i=i+1; if i<dx+1则转2；否则end。}

lwnG_i6{(sD0

^{Bresenham算法的优点是：}电脑爱好者网U#n+K,Yk6w4p

^{1、不必计算直线之斜率，因此不做除法；}电脑爱好者网4Sd7DQKC

^{2、不用浮点数，只用整数；}电脑爱好者网1U3\C6G@F {T`&P

^{3、只做整数加减法和乘2运算，而乘2运算可以用硬件移位实现。}

^{Bresenham算法速度很快，并适于用硬件实现。}电脑爱好者网6p:zl `1aE

　电脑爱好者网1yA(I9[]1L!k

    ^{由上述算法思想编制的程序如程序2.1.2。这个程序适用于所有8个方向的直线（图2.1.1）的生成。程序用色彩C画出一条端点为（x1, y1）和（x2, y2）的直线。其中变量的含义是：P是误差；const1和const2，是误差的逐点变化量；inc是y的单位递变量，值为1或-1；tmp是用作象限变换时的临时变量。程序以判断|dx|>|dy|为分支，并分别将2a, 3a象限的直线和3b, 4b象限的直线变换到1a, 4a和2b, 1b方向去，以求得程序处理的简洁。}电脑爱好者网hLZ!j&iQo-bR^

void line (x1, y1, x2, y2, c)电脑爱好者网Ln#Ah9{B.F*Fc#G/~y

int x1, y1, x2, y2, c;

w)fXQ/V C j0

{电脑爱好者网(R#DeT)ov&O$E

int dx;电脑爱好者网{X VsKfO,C

int dy;

Ed%JBf,v#Wq$D;\ _0

int x;电脑爱好者网(Egi^Gw|E~2~&Rv

int y;

%K uxde3b6U0

int p;

!DG-Cz q8wD0

int const1;电脑爱好者网P~%[;N5{;@3K,lh

int const2;电脑爱好者网@n un"Y7W}&Jd

int inc;电脑爱好者网/ps#\&mr~

int tmp;

i sz3R9R$\Wa#u*V0

dx=x2-x1;

w
Y)[ L'?xK\0

dy=y2-y1;电脑爱好者网N U L/pPv

if (dx*dy>=0) /*准备x或y的单位递变值。*/

$Q1w)?4?Q+tC0

          inc=1;

.h0f.I v(Z'H
x*T]0

else电脑爱好者网0BfF&T&D
Y2I

inc=-1;电脑爱好者网DX8Lla8R N

if (abs(dx)>abs(dy)){

c Hm6O3tXQU9v0

      if(dx<0){电脑爱好者网j3i`E2D+U {!l(yt

               tmp=x1; /*将2a, 3a象限方向*/电脑爱好者网s4l*q!J8N'\)NwGHV7H

               x1=x2; /*的直线变换到1a, 4a*/电脑爱好者网jhG9X$x9S({x

               x2=tmp;电脑爱好者网K'h5E9C:? I^H

               tmp=y1; /*象限方向去*/

#nX8A ^jYO0

               y1=y2;

m$d"Ig4in*`"l0

               dx=-dy;

_O0z)}9w8Wt)s0

               dy=-dy;

.dhrlH(o*C0

           }

1kT.H8y&`Pvd G0

      p=2*dy-dx;

TL A ^(acZV6{G0

      const1=2*dy; /*注意此时误差的*/

@.M0\kv2w'c0

      const2=2*(dy-dy); /*变化参数取值. */

g5G5q(V'u^+g0

      x=x1;

yZ(M J2d!J0

      y=y1;

3Cql*b~7T2|0

      set_pixel(x, y, c);电脑爱好者网a@8`Oqh3Fl

      while (x<x2){电脑爱好者网 F!]d8^a7?Bs

          x++;电脑爱好者网 tF^.B,f.x#l

          if (p<0)电脑爱好者网/Iw+LZz/rq

                       p+=const1;电脑爱好者网Q}*k8Wn

             else{

JY:Jy#j0

                       y+=inc;电脑爱好者网b&O~bkZ4g+@Z6n

                       p+=const2;

%uW;h2mDaz0

                    }

{!}
FQA6Q6m r&mE0

             set_piexl(x, y, c);电脑爱好者网$B;o%{%U%`Q.Te}

         }电脑爱好者网0S-xZ2{F y~6f

}电脑爱好者网A'[Q#d9CqE b

else {电脑爱好者网:y}v7g-A2Zq`

       if (dy<0){

;`)A5Oz"j;C0

                    tmp=x1; /*将3b, 4b象限方向的*/电脑爱好者网b)N%cY~ ]

                    x1=x2; /*直线变换到2b, 1b */电脑爱好者网]:CZv1B8];x&V#c

                    x2=tmp; /*象限方向去. */

+YF}IQz$[}0

                    tmp=y1;电脑爱好者网b_c i.LW$z
H

y1=y2;

Wd9[:l"S;V$[!h?0

dx=-dy;电脑爱好者网!cT:XRSrm3@4J(r9Z

dy=-dy;

+n'[T X1g0

}电脑爱好者网t#vl}tO

p=2*dx-dy; /*注意此时误差的*/电脑爱好者网 w]i Q;s.U#i#c

const1=2*dx; /*变化参数取值. */

L7D![X? P%dc'v0

const2=2*(dx-dy);电脑爱好者网 \6u/ND'ly)c!}

x=x1;

KRcK3F0

y=y1;电脑爱好者网3Id;@N.Qm

set_pixel (x, y, c);电脑爱好者网 W M9E}0Y l9oL

      while (y<y2){

\n r [U$k'U'a x0

             y++;

J4b(Fb$k0

             if(p<0)电脑爱好者网sr4MTq9sWw5` F

                    p+=const1;

2zQy/G:rD#g0

             else{

&UsV*k:Bs0

x+=inc;

:Pb j!~0Bl0

p+=const2;电脑爱好者网@,rD `3R

set_pixel (x, y, c);电脑爱好者网p4j"y5}gU.aLFg&nc

}电脑爱好者网)@y Rn8[ i4q.SJ5n.P E

              }电脑爱好者网A6h"LbE[s

}

Z I V(^/~[0

　

zk{y+x!xQB e0

程序2.1.2适用于直线所有八个方向的Bresenham直线生成算法电脑爱好者网 {HJT.z