若d≥0，则应取P2为下一像素，而且下一像素的判别式为
d=F(x p+2, y p–1.5)= (x p+2)2+(y p–1.5)2–R2=d+2(x p–y p)+5
我们讨论按顺时针方向生成第二个八分圆，则第一个像素是（0, R），判别式d的初始值为
d0=F(1, R–0.5)=1.25–R
1.2.3 圆的Bresenham算法
设圆的半径为r，先考虑圆心在(0, 0)，从x=0、y=r开始的顺时针方向的1/8圆周的生成过程。在这种情况下，x每步增加1，从x=0开始，到x=y结束，即有x i+1 = x i + 1；相应的，y i+1则在两种可能中选择：y i+1=y i或者y i+1= y i–1。选择的原则是考察精确值y是靠近y i还是靠近y i–1（见图1-7），计算式为
y2= r2–(x i+1)2
d1 = y i2–y2 = y i2–r2+(x i+1)2
d2 = y2– (y i–1)2 = r2–(x i+1)2–(y i–1)2
令p i=d1–d2，并代入d1、d2，则有
p i = 2(x i+1)2 + y i2+ (y i–1)2–2r2（1.6）
p i称为误差。如果p i＜0，则y i+1=y i，否则y i+1=y i–1。
p i的递归式为
p i+1 = p i + 4x i +6+2(y i2+1–y i2)–2(y i+1–y i) （1.7）
p i的初值由式(1.6)代入x i=0，y i=r，得
p1 = 3–2r（1.8）
根据上面的推导，圆周生成算法思想如下：
（1）求误差初值，p1=3–2r，i=1，画点(0, r)。
（2）求下一个光栅位置，其中x i+1=x i+1，如果p i＜0则y i+1=y i，否则y i+1=y i–1。
（3）画点(x i+1, y i+1)。
（4）计算下一个误差，如果p i＜0则p i+1=p i+4x i+6，否则p i+1=p i+4(x i–y i)+10。
（5）i=i+1，如果x=y则结束，否则返回步骤（2）。
程序设计步骤如下。
（1）创建应用程序框架，以上面建立的单文档程序框架为基础。
（2）编辑菜单资源。
在工作区的ResourceView标签中，单击Menu项左边“+”，然后双击其子项IDR_MAINFRAME，并根据表1-3中的定义添加编辑菜单资源。此时建好的菜单如图1-8
所示。
表1-3 菜单资源表
（3）添加消息处理函数。
利用ClassWizard （建立类向导）为应用程序添加与菜单项相关的消息处理函数，ClassName 栏中选择CMyView ，根据表1-4建立如下的消息映射函数，ClassWizard 会自动完成有关的函数声明。
表1-4 菜单项的消息处理函数
（4）程序结构代码，在CMyView.cpp 文件中的相应位置添加如下代码。
void CMyView::OnMidpointcircle() //中点算法绘制圆，如图1-9所示
{
// TODO: Add your command handler code here
CDC* pDC=GetDC();
int xc=300, yc=300, r=50, c=0;
int x,y;
float d;
x=0; y=r; d=1.25-r;
pDC->SetPixel ((xc+x),(yc+y),c);
pDC->SetPixel ((xc-x),(yc+y),c);
pDC->SetPixel ((xc+x),(yc-y),c);
pDC->SetPixel ((xc-x),(yc-y),c);
pDC->SetPixel ((xc+y),(yc+x),c);
pDC->SetPixel ((xc-y),(yc+x),c);
pDC->SetPixel ((xc+y),(yc-x),c);
pDC->SetPixel ((xc-y),(yc-x),c);
while(x<=y)
{ if(d<0) d+=2*x+3;
else { d+=2*(x-y)+5; y--;}
x++;
pDC->SetPixel ((xc+x),(yc+y),c);
pDC->SetPixel ((xc-x),(yc+y),c); 图1-9 中点算法绘制圆
图1-8 程序主菜单
pDC->SetPixel ((xc+x),(yc-y),c);
pDC->SetPixel ((xc-x),(yc-y),c);
pDC->SetPixel ((xc+y),(yc+x),c);
pDC->SetPixel ((xc-y),(yc+x),c);
pDC->SetPixel ((xc+y),(yc-x),c);
pDC->SetPixel ((xc-y),(yc-x),c);
}
}
void CMyView::OnBresenhamcircle() //// Bresenham算法绘制圆，如图1-10所示{
CDC* pDC=GetDC();
int xc=100, yc=100, radius=50, c=0;
int x=0,y=radius,p=3-2*radius;
while(x<y)
{
pDC->SetPixel(xc+x, yc+y, c);
图1-10 Bresenham算法绘制圆pDC->SetPixel(xc-x, yc+y, c);
pDC->SetPixel(xc+x, yc-y, c);
pDC->SetPixel(xc-x, yc-y, c);
pDC->SetPixel(xc+y, yc+x, c);
pDC->SetPixel(xc-y, yc+x, c);
pDC->SetPixel(xc+y, yc-x, c);
pDC->SetPixel(xc-y, yc-x, c);
if (p<0)
p=p+4*x+6;
else
{
p=p+4*(x-y)+10;
y-=1;
}
x+=1;
}
if(x==y)
pDC->SetPixel(xc+x, yc+y, c);
pDC->SetPixel(xc-x, yc+y, c);
pDC->SetPixel(xc+x, yc-y, c);
pDC->SetPixel(xc-x, yc-y, c);
pDC->SetPixel(xc+y, yc+x, c);
pDC->SetPixel(xc-y, yc+x, c);
pDC->SetPixel(xc+y, yc-x, c);
pDC->SetPixel(xc-y, yc-x, c);
}
1.3 椭圆扫描转换中点算法
下面讨论椭圆的扫描转换中点算法，设椭圆为中心在坐标原点的标准椭圆，其方 程为 F (x , y )=b 2x 2+a 2y 2–a 2b 2=0
（1）对于椭圆上的点，有F (x , y )=0；
（2）对于椭圆外的点，F (x , y )>0；
（3）对于椭圆内的点，F (x , y )<0。
以弧上斜率为–1的点作为分界将第一象限椭圆弧分为上下两部分（如图1-11所示）。 法向量：
22(,)i j 2i 2j F F N x y b x a y x y ??=+=+??
22(1)(0.5)i i b x a y +<- 而在下一个点，不等号改变方向，则说明椭圆弧从上部分转入下部分。 与中点绘制圆算法类似，一个像素确定后，在下面两个候选像素点的中点计算一个判别式的值，再根
据判别式符号确定离椭圆最近的点。先看椭圆弧的上半部分，具体算法如下： 假设横坐标为x p 的像素中与椭圆最近点为（x p , y p ），下一对候选像素的中点应为（x p +1，y p –0.5），判别式为
222222
1(1,0.5)(1)(0.5)p p p p d F x y b x a y a b =+-=++--
10d <，表明中点在椭圆内，应取正右方像素点，判别式变为
222222211(2,0.5)(2)(0.5)(23)p p p p p d F x y b x a y a b d b x '=+-=++--=++
若10d ≥，表明中点在椭圆外，应取右下方像素点，判别式变为