2.2.2 圆的Bresenham算法

2.2.2 圆的Bresenham算法

　电脑爱好者网iv ZcQUE$?U*t9i

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

^xi+1=xi+1

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

^{yi+1=yi，或者yi+1=yi-1}电脑爱好者网` Y&C+d^-n cIat

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

y²=r²-(x_i+1)^{2电脑爱好者网4gP4Tq3o%Y@.^F k}

d₁=y_i²-y^{2电脑爱好者网]4O"B!M*l r2sJi}

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

;TSq`ErmQ_0

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

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

4}w|R.D;|0

图2.2.2 y的位置电脑爱好者网4`eC8bV|7m,Sv

^{令pi=d1-d2，并代入d1, d2，则有}电脑爱好者网+~(t FEX7I4i

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

5YU4\-F1p J$Z0

^{pi称为误差。如果pi<0则yi+1=yi，否则yi+1=yi-1。pi的递归式为：}电脑爱好者网8I8X @?*Pe6CXd

^{pi+1=pi+4xi+6+2(yi2+1-yi2)-2(yi+1-yi) (2.2.2)}

_9v Lt;iBJ0

^{pi的初值由式（2.6）代入xi=0, yi=r而得}

          ^{p1=3-2r (2.2.3)}电脑爱好者网:c4t6e ~v2T#{

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

^{1、求误差初值，p1=3-2r; i=1；画点(0, r)；}电脑爱好者网 ~%D~+d4b!Dw

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

^xi+1=xi+1；

^{if pi<0 则yi+1=yi；}电脑爱好者网2Ebv9g C3gf

^{否则yi+1=yi-1；}电脑爱好者网8um3zj*?V

^{3、画点（xi+1, yi+1）}

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

^{if pi<0 则pi+1=pi+4xi+6；}电脑爱好者网}3}XQ,l["m~

^{否则 pi+1=pi+4(xi-yi)+10；}电脑爱好者网n:B~9{:a XZE@*X

^{5、i=i+1; if x=y则end；否则返2。}电脑爱好者网@0I{ _9l6]:u

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

^{圆的Bresenham算法的程序实现见程序2.2.1。}电脑爱好者网[n7No2W/oJg1vB

circle (xc, yc, radius, c)

,Yi'V C2\)~0

int xc, yc, radius, c;电脑爱好者网%pw kp!K*d

{

&LfO3dg c4j"i0

int x, y, p;电脑爱好者网*h|5`(syBp$[m

x=0;电脑爱好者网 AMM;F0?$F2Y

y=radius;电脑爱好者网8d-N)I5\#d;l?@X
E,{

p=3-2*radius;

5Jo*B ^5J+v&c0

while (x<y){

f
[2~ z{V0

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

C0R:whRN b0

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

&w+Z Ao+i d!b0

        else{电脑爱好者网 nu0y&k7m

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

o xirrzZ&w7F0

                  y-=1;电脑爱好者网!?dsU)q1a7B

                }

[@dCu)MB1O0[0

        x+=1;

h^a ~
J |!kQ0

                 }

`]Qv6Zc!@t;y0

if (x= =y)

Q R5K0~oa0

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

0E/fz4Ab*x#\0

}

5c.S*VL\6ye-{0

　电脑爱好者网)}1v mjA&ay

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

9t$e&U.Zg0

int xc, yc, x, y, c;电脑爱好者网7p}P z[.\5l`

{电脑爱好者网Ny;U&D SWJ}R

set_pixel(xc+x, yc+y, c);电脑爱好者网#^T5p%BHE|ev

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

Q)n!G&w-cc]0

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

.TVtk"z1a+G9L:y0

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

c`
CVBo0

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

3O)b9Ry;L w2L hA0

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

-gtT[7E ]'_5i*I0

set_pixel(xc+y, yc-x, c);电脑爱好者网:^._l'Ov,ui2[

set_pixel(xc-y, yc-x, c);电脑爱好者网ovd1x0Mm!|

}

gC,c$r3rcB#id0

　

FWf:pVo/J/NU0

程序2.2.1 Bresenham的圆生成算

cfG2K9o!@x'f0