在進(jìn)行圓的轉(zhuǎn)換時(shí)，只要能生成8分圓，那么圓的其它部分可通過(guò)一系列的簡(jiǎn)單反射變換得到。本小節(jié)介紹一種常用的畫圓算法：Bresenham畫圓算法。
Bresenham算法：不失一般性，考慮圓心在原點(diǎn)，半徑為R的第一個(gè)4分圓。取（0，R)為起點(diǎn)，按順時(shí)針?lè)较蛏蓤A。從這段圓弧的任意一點(diǎn)出發(fā)，按順時(shí)針?lè)较蛏蓤A時(shí)，為了最佳逼近該圓，下一象素的取法只要三種可能的選擇：正右方象素，右下方象素和正下方象素。
xi+1=xi+1
相應(yīng)的yi+1則在兩種可能中選擇：
yi+1=yi，或者yi+1=yi-1
選擇的原則是考察精確值y靠近yi還是靠近yi-1（圖1），計(jì)算式為：
y2=r2-(xi+1)2
d1=yi2-y2
=yi2-r2+(xi+1)2
d2=y2-(yi-1)2
=r2-(xi+1)2-(yi-1)2
圖1
令pi=d1-d2，并代入d1, d2，則有
pi=2(xi+1)2+yi2+(yi-1)2-2r2 (2.2.1)
pi稱為誤差。如果pi<0則yi+1=yi，否則yi+1=yi-1。pi的遞歸式為：
pi+1=pi+4xi+6+2(yi2+1-yi2)-2(yi+1-yi) (2.2.2)
pi的初值由式（2.6）代入xi=0, yi=r而得
p1=3-2r (2.2.3)
根據(jù)上面的推導(dǎo)，圓周生成算法思想為：
1、求誤差初值，p1=3-2r; i=1；畫點(diǎn)(0, r)；
2、求下一個(gè)光柵位置：
xi+1=xi+1；
if pi<0 則yi+1=yi；
否則yi+1=yi-1；
3、畫點(diǎn)（xi+1, yi+1）
4、計(jì)算下一個(gè)誤差：
if pi<0 則pi+1=pi+4xi+6；
否則 pi+1=pi+4(xi-yi)+10；
5、i=i+1; if x=y則end；否則返2。
雖然式（2.2.2）式表示pi+1的算法似乎很復(fù)雜，但因?yàn)閥i+1只能取值yi或yi-1，因此在算法中，第4步的算式變得很簡(jiǎn)單，只須作加法和4的乘法。因此圓的Bresenham算法運(yùn)行速度也是很快的，并適宜于硬件實(shí)現(xiàn)。
圓的Bresenham算法的程序?qū)崿F(xiàn)見程序2.2.1。
circle (xc, yc, radius, c)
int xc, yc, radius, c;
{
int x, y, p;
x=0;
y=radius;
p=3-2*radius;
while (x<y){
plot_circle_points(xc, yc, x, y, c);
if (p<0) p=p+4*x+6;
else{
p=p+4*(x-y)+10;
y-=1;
}
x+=1;
}
if (x= =y)
plot_circle_points(xc, yc, x, y, c);
}
plot_circle_points(xc, yc, x, y, c)
int xc, yc, x, y, c;
{
set_pixel(xc+x, yc+y, c);
set_pixel(xc+x, yc+y, c);
set_pixel(xc+x, yc-y, c);
set_pixel(xc-x, yc-y, c);
set_pixel(xc+y, yc+x, c);
set_pixel(xc-y, yc+x, c);
set_pixel(xc+y, yc-x, c);
set_pixel(xc-y, yc-x, c);
}
Bresenham的圓生成算法
設(shè)圓之半徑為r。先考慮圓心在（0,0），并從x=0, y=r開始的順時(shí)針?lè)较虻?/8圓周的生成過(guò)程。在這種情況下，x每步增加1，從x=0開始，到x=y結(jié)束。即有：
給出圓心坐標(biāo)xc, yc，和半徑r，逐點(diǎn)畫出一個(gè)圓周的公式有下列兩種：
1、直角坐標(biāo)法：
(x-xc)2+(y-yc)2=r2
由上式導(dǎo)出
y=
當(dāng)x-xc從-r到r作加1遞增時(shí)，就可以求出對(duì)應(yīng)的圓周點(diǎn)的y坐標(biāo)。但是這樣求出的圓周上的點(diǎn)是不均勻的；|x-xc|越大，對(duì)應(yīng)生成圓周點(diǎn)之間的圓周距離也就越長(zhǎng)。因此，所生成的圓不美觀。.
2、極坐標(biāo)法：
x=xc+r·cosθ
y=yc+r·sinθ
當(dāng)θ
從0 度到360 作加1遞增時(shí)，由此式便可求出圓周上均勻分布的360個(gè)點(diǎn)的x,
y坐標(biāo)。利用圓周坐標(biāo)的對(duì)稱性，此算法還可以簡(jiǎn)化：將圓周分為8個(gè)象限（圖2.2.1）。只要將第1a象限中的圓周光柵點(diǎn)求出，其余7部分圓周就可以通過(guò)
對(duì)稱法則計(jì)算出來(lái)。圖2.2.1給出了圓心在0，0點(diǎn)時(shí)的對(duì)稱變換法則。但即使作了如此簡(jiǎn)化，用上述公式每算一點(diǎn)，都要經(jīng)過(guò)三角函數(shù)計(jì)算，仍有相當(dāng)大的計(jì)算量。
圖2.2.1 圓心在0,0點(diǎn)圓周生成時(shí)的對(duì)稱變換
在計(jì)算機(jī)中上述兩個(gè)公式所示的方法生成圓周都頗費(fèi)時(shí)，下面介紹的算法則要簡(jiǎn)捷得多。
3.圓的Bresenham算法