2.2.2 圆的Bresenham算法

2.2.2 圆的Bresenham算法

　电脑爱好者网1|!?!ZH u H

^{设圆之半径为r。先考虑圆心在（0,0），并从x=0, y=r开始的顺时针方向的1/8圆周的生成过程。在这种情况下，x每步增加1，从x=0开始，到x=y结束。即有：}电脑爱好者网;{lz3H3?k9u

^xi+1=xi+1

^{相应的yi+1则在两种可能中选择：}

^{yi+1=yi，或者yi+1=yi-1}

^{选择的原则是考察精确值y靠近yi还是靠近yi-1（图2.2.2），计算式为}：

y²=r²-(x_i+1)^{2电脑爱好者网3~ }'k
E2e&\H9]}

d₁=y_i²-y²

s Aqw
Bt0

    =y_i²-r²+(x_i+1)²

0Tl@'_-g(tr8z&v0

d₂=y²-(y_i-1)^{2电脑爱好者网|{'v YK4YT6zgw}

    =r²-(x_i+1)²-(y_i-1)²电脑爱好者网1rD nlv
y%B

图2.2.2 y的位置电脑爱好者网L_)eM-m5P0_m

^{令pi=d1-d2，并代入d1, d2，则有}电脑爱好者网|4bkO9@7l j1Q

^{pi=2(xi+1)2+yi2+(yi-1)2-2r2 (2.2.1)}

JQ|1]3k4sP5Ac0

^{pi称为误差。如果pi<0则yi+1=yi，否则yi+1=yi-1。pi的递归式为：}电脑爱好者网H/W4[/m,oTf

^{pi+1=pi+4xi+6+2(yi2+1-yi2)-2(yi+1-yi) (2.2.2)}电脑爱好者网#T` I;n0gCP

^{pi的初值由式（2.6）代入xi=0, yi=r而得}电脑爱好者网-_!XN'O:^
u M

          ^{p1=3-2r (2.2.3)}电脑爱好者网#gjOnOk6mY

^{根据上面的推导，圆周生成算法思想为：}

^{1、求误差初值，p1=3-2r; i=1；画点(0, r)；}电脑爱好者网KiO/H fu(Zf^

^{2、求下一个光栅位置：}

^xi+1=xi+1；

^{if pi<0 则yi+1=yi；}电脑爱好者网 d7|vPZ

^{否则yi+1=yi-1；}电脑爱好者网}h4DK
hl&|UD

^{3、画点（xi+1, yi+1）}电脑爱好者网l)~A \3Y

^{4、计算下一个误差：}

^{if pi<0 则pi+1=pi+4xi+6；}

^{否则 pi+1=pi+4(xi-yi)+10；}电脑爱好者网2~*j,H3YlI;w(mC

^{5、i=i+1; if x=y则end；否则返2。}

^{虽然式（2.2.2）式表示pi+1的算法似乎很复杂，但因为yi+1只能取值yi或yi-1，因此在算法中，第4步的算式变得很简单，只须作加法和4的乘法。因此圆的Bresenham算法运行速度也是很快的，并适宜于硬件实现。}

^{圆的Bresenham算法的程序实现见程序2.2.1。}电脑爱好者网"X fzQN)ab

circle (xc, yc, radius, c)

VpJ:f4^0

int xc, yc, radius, c;

E
?
a,xRTj
Y^0

{电脑爱好者网F5TSe|,B;RV

int x, y, p;电脑爱好者网_M,bQ{"t

x=0;

"l{E(q%rc0

y=radius;

)Z8I/Sr4?X5\"c0

p=3-2*radius;电脑爱好者网{$Of#UG\3Q"hY;u

while (x<y){电脑爱好者网H$UJ]4P0H+O^

        plot_circle_points(xc, yc, x, y, c);电脑爱好者网,D9o5h_{ij

        if (p<0) p=p+4*x+6;

Sno:fB;^3]R5C(K0

        else{

Cj&JdWf v,i)Zaz!tk0

                  p=p+4*(x-y)+10;

j%w#]M6V.e!e[0

                  y-=1;电脑爱好者网TT#wX0lP

                }电脑爱好者网(KJ5H/q6|(x$Oe

        x+=1;

?_)Tqk0

                 }电脑爱好者网Bl
YpB5Ey nG
S

if (x= =y)电脑爱好者网z2LQeY}cs

        plot_circle_points(xc, yc, x, y, c);

.m!S]uIq0

}电脑爱好者网2Jn7B|&zfOc

　

+U7t BQU l;|6R g'B0

plot_circle_points(xc, yc, x, y, c)

CB N5^O&}
uy
V0

int xc, yc, x, y, c;

;Q/G%Wo%X#HJk0

{

h kJ+yYs&||0

set_pixel(xc+x, yc+y, c);电脑爱好者网
K4|~:C1T:[-|8x

set_pixel(xc+x, yc+y, c);

|r+qU3UE0

set_pixel(xc+x, yc-y, c);电脑爱好者网R0K%N|+h"`

set_pixel(xc-x, yc-y, c);电脑爱好者网]~$o)v VP

set_pixel(xc+y, yc+x, c);电脑爱好者网4w*V)p7T7Bw9q

set_pixel(xc-y, yc+x, c);电脑爱好者网"Z-C iD8Sn

set_pixel(xc+y, yc-x, c);

Q:Kk _z]WE0

set_pixel(xc-y, yc-x, c);

|M_!W2p$Yb3N/Ld0

}

#~_;Sv/iW8^0

　

|KKUUB0

程序2.2.1 Bresenham的圆生成算

&O)U#PTG B:{ ~!Z:bN0