图形(2)

if(f>=0){

if(interchange==1) x+=s1; else y+=s2;

pDC->SetPixel(x,y,c); f=f-2*deltax; } else{

if(interchange==1) y+=s2; else x+=s1; f=f+2*deltay; } } } 说明：

（1）以上程序已经考虑到所有象限直线的生成。 （2）Bresenham算法的优点如下： ① 不必计算直线的斜率，因此不做除法。 ② 不用浮点数，只用整数。

③ 只做整数加减运算和乘2运算，而乘2运算可以用移位操作实现。 ④ Bresenham算法的运算速度很快。 1.2 圆

给出圆心坐标(xc, yc)和半径r，逐点画出一个圆周的公式有下列两种。 1.2.1 直角坐标法 直角坐标系的圆的方程为

由上式导出：

当x–xc从–r到r做加1递增时，就可以求出对应的圆周点的y坐标。但是这样求出的圆周上的点是不均匀的，| x–xc | 越大，对应生成圆周点之间的圆周距离也就越长。因此，所生成的圆不美观。 1.2.2 中点画圆法

如图1-6所示，函数为F(x, y)=x2+y2–R2的构造圆，圆上的点为F(x, y)=0，圆外的点F(x, y)>0，圆内的点F(x, y)<0，构造判别式： d=F(M)=F(xp+1, yp–0.5)=(xp+1)2+(yp–0.5)2

若d＜0，则应取P1为下一像素，而且下一像素的判别式为 d=F(xp+2, yp–0.5)= (xp+2)2+(yp–0.5)2–R2=d+2xp+3 若d≥0，则应取P2为下一像素，而且下一像素的判别式为

d=F(xp+2, yp–1.5)= (xp+2)2+(yp–1.5)2–R2=d+2(xp– yp)+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结束，即有xi+1 = xi + 1；相应的，yi+1则在两种可能中选择：yi+1=yi或者yi+1 = yi – 1。选择的原则是考察精确值y是靠近yi还是靠近yi–1（见图1-7），计算式为 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 令pi=d1–d2，并代入d1、d2，则有

pi = 2(xi+1)2 + yi2+ (yi – 1)2 –2r2 （1.6）

pi称为误差。如果pi＜0，则yi+1=yi，否则yi+1=yi – 1。 pi的递归式为

pi+1 = pi + 4xi +6+2(yi2+1– yi2)–2(yi+1–yi) （1.7） pi的初值由式(1.6)代入xi=0，yi=r，得 p1 = 3–2r （1.8）

根据上面的推导，圆周生成算法思想如下： （1）求误差初值，p1=3–2r，i=1，画点(0, r)。

（2）求下一个光栅位置，其中xi+1=xi+1，如果pi＜0则yi+1=yi，否则yi+1=yi – 1。 （3）画点(xi+1, yi+1)。

（4）计算下一个误差，如果pi＜0则pi+1=pi+4xi+6，否则pi+1=pi+4(xi – yi)+10。 （5）i=i+1，如果x=y则结束，否则返回步骤（2）。 程序设计步骤如下。

（1）创建应用程序框架，以上面建立的单文档程序框架为基础。 （2）编辑菜单资源。

在工作区的ResourceView标签中，单击Menu项左边―+‖，然后双击其子项IDR_MAINFRAME，并根据表1-3中的定义添加编辑菜单资源。此时建好的菜单如图1-8所示。 表1-3 菜单资源表

菜单标题 菜单项标题 标示符ID 圆 中点画圆 ID_MIDPOINTCIRCLE Bresenham画圆 ID_BRESENHAMCIRCLE （3）添加消息处理函数。

利用ClassWizard（建立类向导）为应用程序添加与菜单项相关的消息处理函数，ClassName栏中选择CMyView，根据表1-4建立如下的消息映射函数，ClassWizard会自动完成有关的函数声明。

表1-4 菜单项的消息处理函数 菜单项ID 消 息 消息处理函数

ID_MIDPOINTCIRCLE CONMMAN OnMidpointcircle ID_BRESENHAMCIRCLE CONMMAN OnBresenhamcircle

（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); 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

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); 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)=b2x2+a2y2–a2b2=0

（1）对于椭圆上的点，有F(x, y)=0； （2）对于椭圆外的点，F(x, y)>0；

（3）对于椭圆内的点，F(x, y)<0。

以弧上斜率为–1的点作为分界将第一象限椭圆弧分为上下两部分（如图1-11所示）。 法向量：

而在下一个点，不等号改变方向，则说明椭圆弧从上部分转入下部分。

与中点绘制圆算法类似，一个像素确定后，在下面两个候选像素点的中点计算一个判别式的值，再根据判别式符号确定离椭圆最近的点。先看椭圆弧的上半部分，具体算法如下： 假设横坐标为xp的像素中与椭圆最近点为（xp, yp），下一对候选像素的中点应为（xp+1，yp–0.5），判别式为

，表明中点在椭圆内，应取正右方像素点，判别式变为

若 ，表明中点在椭圆外，应取右下方像素点，判别式变为

判别式 的初始条件确定。椭圆弧起点为(0, b)，第一个中点为(1,b – 0.5)，对应判别式为

在扫描转换椭圆的上半部分时，在每步迭代中需要比较法向量的两个分量来确定核实从上部分转到下半部分。在下半部分算法有些不同，要从正上方和右下方两个像素中选择下一个像素。在从上半部分转到下半部分时，还需要对下半部分的中点判别式进行初始化。即若上半部分所选择的最后一个像素点为(xp, yp)，则下半部分中点判别式应在（xp+0.5, yp–1）的点上计算。其在正下方与右下方的增量计算同上半部分。具体算法的实现请参考下面的程序设计。

程序设计步骤如下。

（1）创建应用程序框架，以上面建立的单文档程序框架为基础。 （2）编辑菜单资源。

在工作区的ResourceView标签中，单击Menu项左边―+‖，然后双击其子项IDR_MAINFRAME，并根据表1-5中的定义添加编辑菜单资源。此时建好的菜单如图1-12所示。 表1-5 菜单资源表

菜单标题 菜单项标题 标示符ID

椭圆 中点画椭圆 ID_MIDPOINTELLISPE

图1-12 程序主菜单 （3）添加消息处理函数。

利用ClassWizard（建立类向导）为应用程序添加与菜单项相关的消息处理函数，ClassName栏中选择CMyView，根据表1-6建立如下的消息映射函数，ClassWizard会自动完成有关的函数声明。

表1-6 菜单项的消息处理函数