中点画圆法的扫描转换算法

第四章、基本图形生成算法教学目的：1、知道图形生成中的基本问题；2、熟练掌握直线的扫描转换、圆与椭圆的扫描；3、掌握区域填充；4、了解线宽与线型的处理。

�在光栅显示器上显示的任何一种图形，实际上都是一些具有一种或多种颜色的象素的集合。

�生成算法即图形设备生成图形的方法，也叫光栅化或或图形的扫描转换，是确定一个象素集合及其颜色，用于显示一个图形的过程。

确定一个象素集合及其颜色，用于显示一个图形的过程，称为图形的扫描转换或光栅化。

�对图形的扫描转换分为两部分：先确定像素，再用图形的颜色或其他属性进行某种写操作。

绘图元素�构成图形的基本元素，主要有点、直线、圆和曲线等。

图形元素包含的信息：①图元的类型②图元的几何信息③图元的非几何信息；④图元的指针信息11、点22、位置33、像素44、直线55、曲线66、填充点、线图形基元包括：多边形、曲线、字符串 实心图形（或称图形填充）一级图形元素二级图形元素第一节、扫描转换算法一、坐标系1．用户坐标系�在实际世界中用来描述物体的位置、形状等。

坐标单位任意，坐标值是实数、范围不限。

2．笛卡尔坐标系（直角坐标系）�在计算机图形学中使用用来描述物体。

3．设备坐标系�在某一特定设备上用来描述物体，如显示器的屏幕坐标系，绘图仪的绘图坐标系。

坐标单位为像素、步长，即设备的分辨率。

坐标值是整数，有固定的取值范围。

4．规范坐标系�在通用图形软件包中使用的用来描述物体数据所采用的坐标系。

�目的是为了使通用图形软件包摆脱对具体物理设备的依赖性，也为了便于在不同应用和不同系统之间交换图形信息。

�坐标单位任意取，坐标取值范围是［０，１］区间。

笛卡儿坐标系与屏幕坐标系的转换�屏幕（x，y）=（x笛卡儿+x最大分辨率/2，y最大分辨率/2- y笛卡儿）二、笛卡尔坐标系和设备坐标系中相关概念的区别（1）像素点�·在几何学中，点没有准数，没有大小，只表示了在坐标系统中的一个位置。

·在图形系统中，点要由数值坐标表示。

圆的扫描转换一、算法原理本节主要讲解仅包含加减操作的顺时针绘制1/8圆的中点Bresenham 算法原理。

1、圆的特性圆心在原点、半径为R 的圆方程的隐函数表达式为：圆将平面划分成三个区域：对于圆上的点，F(x ，y)＝0；对于圆外的点，F （x ，y ）＞0；对于圆内的点，F （x ，y ）＜0。

事实上，考虑到圆在第一象限内的对称性，本算法可以进一步简化。

因为AC 段圆弧和CB 段圆弧以对称轴x ＝y 完全对称，如图3-6所示，所以可以用四条对称轴x ＝0，y ＝0， x ＝y,x ＝－y 把圆分成8等份。

只要绘制出第一象限内的1/8圆弧Ⅰ，根据对称性就可绘制出整圆，这称为八分法画圆算法。

假定第一象限内的任意点为P （x,y ），可以顺时针确定另外7个点：P （y ，x ）P （y ，－x ）,P （x,－ y ） ,P （－x ，－y ），P （－y ，－x ），P （－y ，x ），P （－x ，y ）。

),(222=-+=R y x y x F从P （xi ，yi ）开始，为了进行下一像素点的选取，需将Pu 和Pd 的中点M （x i ＋1，y i －0.5）代入隐函数，构造中点偏差判别式：当d<0时，中点M 在圆内，下一像素点应点亮Pu ，即y 方向不退步；当d>0时，中点M 在圆外，下一像素点应点亮Pd ，即y 方向退一步；当d ＝0时，中点M 在圆上， Pu 、Pd 和圆的距离相等，点亮Pu 或Pd 均可，约定取Pd 。

因此，2、递推公式1.中点偏差判别式的递推公式现在如果考虑主位移方向再走一步，应该选择哪个中点代入中点偏差判别式以决定下一步应该点亮的像素，分两种情况讨论。

222)5.0()1()5.0,1(),(R y x y x F y x F d i i i i M M --++=-+==⎩⎨⎧≥<=+)0( 1-)0( 1d y d y y i i i中点偏差判别式的递推2.中点偏差判别式的初始值圆的起点为P0（0，R ），x 为主位移方向。

扫描转换线画图元实验目的：通过上机实践，在C语言环境下实现扫描转换线画图元（直线、圆、椭圆）。

基本思想：利用计算出落在图元上或充分靠近它的一串像素，并以此像素集近似代替原连续图元在屏幕上的显示。

1、扫描转换直线段：（生成直线段的DDA算法）假设需扫描转换的直线段为P0（x0,y0）P1(x1,y1),再令∆x=x1-x0,∆y=y1-y0,斜率m=∆y/∆x,直线方程可以表示为：y=m*x+B ，求表示直线段P 0P1的像素集的最简单方法是利用直线方程直接计算。

以一个像素为单位分割区间[x0,x1],得到上的一个划分：x0,x1,…,x n,根据直线方程得到直线段上对应于横坐标xi的点的纵坐标为y i =m* x i +B，于是就得到了直线段上的点列{（x i,y i）},如图：利用公式：y i+1=mx i+1+B=m(x i+1)+B=mx i+B+m=y i+m得到直线。

2、扫描转换圆弧：该图元是利用圆的八对称性，扫描圆的八分之一弧而进行作图的。

利用函数CirclePoints（）显示圆弧上任意一点（x,y）及其七个对称点；如图所示：在作图过程中需要设置中心坐标，否则程序默认圆心（0，0），这样我们看到的将会是1/4圆弧。

关于算法课本中已经讲的很清楚了，这里就不赘述了；3、扫描转换椭圆弧： 我们知道椭圆的方程为： X 2/a+y 2/b=1椭圆弧的画法类似于圆弧的画法，即只需要讨论第一象限内椭圆弧的生成。

进一步可以将椭圆弧分为上下两部分，其分界点为切线斜率为-1的点P ，再由公式： （yy x F x y x F ∂∂∂∂),(,),(）=（2b 2x,2a 2y ） 因为（x,y ）点的切向与法向垂直，为（-2a 2y , 2b 2x ），从而切线斜率为-1的满足 2b 2x=2a 2y ⇔b 2x=a 2y 由此编程可以得到椭圆。

扫描转换直线段、圆、椭圆的程序如下：#include <stdio.h> #include<graphics.h> #include<math.h> #include<conio.h> /*----画线段----*/void LineDDA(int x0,int y0,int x1,int y1,int color) {int x;float dy ,dx,y ,m; dx=x1-x0; dy=y1-y0; m=dy/dx; y=y0;for(x=x0;x<=x1;x++){putpixel(x,(int)(y+0.5),color); y+=m; }}/*----画圆----*/void CirclePoints( int xo,int yo,int x,int y,int color){putpixel(x+xo,y+yo,color); /*在坐标x,y指定的位置上画一个点*/ putpixel(y+yo,x+xo,color);putpixel(-y+yo,x+xo,color);putpixel(-x+xo,y+yo,color);putpixel(y+yo,-x+xo,color);putpixel(x+xo,-y+yo,color);putpixel(-x+xo,-y+yo,color);putpixel(-y+yo,-x+xo,color);}void MidPointCircle(int xo,int yo,int radius,int color){int x,y,d,deltaE,deltaSE;x=0;y=radius;d=5-4*radius;deltaE=12;deltaSE=20-8*radius;CirclePoints(xo,yo,x,y,color);while(y>x){if(d<=0){d+=deltaE;deltaSE+=8;}else{d+=deltaSE;deltaSE+=16;y--;}deltaE+=8;x++;CirclePoints(xo,yo,x,y,color);}}/*----画椭圆----*/void EllipsePoints(int x_c,int y_c,int x,int y,int color){putpixel(x+x_c,y+y_c, color);putpixel(-x+x_c,y+y_c,color);putpixel(-x+x_c,-y+y_c,color);putpixel(x+x_c,-y+y_c,color);}void MidPointEllipse(int x_c,int y_c,int a,int b,int color) {long x,y,d,xP,yP,squarea,squareb;squarea=(long)a*a;squareb=(long)b*b;xP=(int)(0.5+(float)squarea/sqrt((float)(squarea+squareb))); yP=(int)(0.5+(float)squareb/sqrt((float)(squarea+squareb))); x=0;y=b;d=4*(squareb-squarea*b)+squarea; /*初始化*/ EllipsePoints(x_c,y_c,x,y,color);while(x<=xP){if(d<=0)d+=4*squareb*(2*x+3);else{d+=4*squareb*(2*x+3)-8*squarea*(y-1);y--;}x++;EllipsePoints(x_c,y_c,x,y,color);}x=a;y=0;d=4*(squarea-a*squareb)+squareb;EllipsePoints(x_c,y_c,x,y,color);while(y<=yP){if(d<=0)d+=4*squarea*(2*y+3);else{d+=4*squarea*(2*y+3)-8*squareb*(x-1);x--;}y++;EllipsePoints(x_c,y_c,x,y,color);}}void main(){int a0,b0,a1,b1,c_color;int p0,q0,r,c_color1;int m0,n0,m1,n1,c_color2;int graphdriver,graphmode;graphdriver=VGA;graphmode=VGAHI;initgraph(&graphdriver,&graphmode,"\\TC");cleardevice();printf("enter the line start:");scanf("%d,%d",&a0,&b0);printf("enter the line end:");scanf("%d,%d",&a1,&b1);printf("enter the color mumber:");scanf("%d",&c_color);cleardevice();LineDDA(a0,b0,a1,b1,c_color);getch();cleardevice();printf("enter the center :"); /*输入图圆中心*/scanf("%d,%d",&p0,&q0);printf("enter the radius:"); /*输入图圆半径*/scanf("%d",&r);printf("enter the color mumber:"); /* 输入颜色值*/scanf("%d",&c_color1);cleardevice();MidPointCircle(p0,q0,r,c_color1);getch();cleardevice();printf("enter the center :"); /*输入中心坐标*/scanf("%d,%d",&m0,&n0);printf("enter the chang duan zhou chang:"); /*输入长短轴长*/scanf("%d,%d",&m1,&n1);printf("enter the color mumber:");scanf("%d",&c_color2);cleardevice();MidPointEllipse(m0,n0,m1,n1,c_color2);getch();closegraph();}在程序运行过程中，当然也出现了不少错误，这里只举一两例加以说明（1）、程序在运行过程中，在画椭圆的时候，图象中只有四个点，而不是连续的曲线，经过查阅书籍以及请教同学发现在函数体中缺少了math.h头文件，所以加上文件包含命令#include<math.h>即可出现连续的椭圆图象。

扫描转换算法——DDA、中点画线画圆、椭圆我的理解：在光栅图形学中，由于每⼀个点的表⽰都只能是整数值，所以光栅图形学实际只是对对实际图形的近似表⽰。

数值微分法（DDA）：以下PPT截图来⾃北京化⼯⼤学李辉⽼师代码实现：import matplotlib.pyplot as pltimport matplotlib.patches as patchesfrom pylab import *def init(ax):#将主标签设置为1的倍数majorLocator = MultipleLocator(1);#设置主刻度标签的位置,标签⽂本的格式ax.xaxis.set_major_locator(majorLocator);ax.yaxis.set_major_locator(majorLocator);ax.grid(True);if__name__ == '__main__':x0, y0, x1, y1 = map(int, input("请输⼊直线的起点与终点： ").split('')) ax = subplot(title='DDA');ax.plot([x0, x1], [y0, y1], 'r');delta_x = x1-x0;delta_y = y1-y0;#画坐标轴if x1>y1:ax.axis([x0-1, x1+1, y0-1, x1+1]);init(ax);else:ax.axis([x0-1, y1+1, y0-1, y1+1]);init(ax);#计算斜率k的值if delta_x == 0:k = 999999999;else:k = delta_y / delta_x;#如果|k|<=1if k>-1 and k<1:while x0<=x1:x = round(x0);y = round(y0);ax.plot(x, y, 'b.');x0 += 1;y0 = y0+k;else:while y0<=y1:x = round(x0);y = round(y0);ax.plot(x, y, 'b.');x0 += 1/k;y0 += 1;plt.show();运⾏截图：中点画线：以下PPT截图来⾃北京化⼯⼤学李辉⽼师代码实现：wimport matplotlib.pyplot as pltimport matplotlib.patches as patchesfrom pylab import *def init(ax):#将主标签设置为1的倍数majorLocator = MultipleLocator(1);#设置主刻度标签的位置,标签⽂本的格式ax.xaxis.set_major_locator(majorLocator);ax.yaxis.set_major_locator(majorLocator);ax.grid(True);if__name__ == '__main__':x0, y0, x1, y1 = map(int, input("请输⼊直线的起点与终点： ").split('')) ax = subplot(title='Midpoint');ax.plot([x0, x1], [y0, y1], 'r');a = y0-y1;b = x1-x0;d = 2*a+b;d1 = 2*a;d2 = 2*(a+b);#画坐标轴if x1>y1:ax.axis([x0-1, x1+1, y0-1, x1+1]);init(ax);else:ax.axis([x0-1, y1+1, y0-1, y1+1]);init(ax);x = x0;y = y0;ax.plot(x, y, 'r.');while(x < x1):if d<0:x += 1;y += 1;d += d2;else:x += 1;d += d1;ax.plot(x, y, 'r.');plt.show()中点画圆法：以下PPT截图来⾃北京化⼯⼤学李辉⽼师import matplotlib.pyplot as pltimport matplotlib.patches as patchesfrom pylab import *def init(ax):#将主标签设置为1的倍数majorLocator = MultipleLocator(1);#设置主刻度标签的位置,标签⽂本的格式ax.xaxis.set_major_locator(majorLocator);ax.yaxis.set_major_locator(majorLocator);ax.grid(True);if__name__ == '__main__':r = int(input("请输⼊半径： "));plt.figure(figsize=(r*0.1, r*0.1));ax = subplot(title='MidPointCircle');d = 1-r;ax.axis([-r-1, r+1, -r-1, r+1]);init(ax);x = 0;y = r;ax.plot(x, y, 'r.');while(x <= y):if d<0:d += 2*x+3;else:d += 2*(x-y)+5;y -= 1;x += 1;ax.plot(x, y, 'r.');ax.plot(y, x, 'r.');ax.plot(x, -y, 'r.');ax.plot(-y, x, 'r.');ax.plot(-x, y, 'r.');ax.plot(y, -x, 'r.');ax.plot(-x, -y, 'r.');ax.plot(-y, -x, 'r.');plt.show()椭圆的扫描转换：以下PPT截图来⾃北京化⼯⼤学李辉⽼师代码实现：import matplotlib.pyplot as pltimport matplotlib.patches as patchesimport mpl_toolkits.axisartist as axisartistfrom pylab import *def init(ax):#设置x轴：空⼼箭头、数值在下⽅ax.axis["x"] = ax.new_floating_axis(0, 0);ax.axis["x"].set_axisline_style("->", size = 1.0);ax.axis["x"].set_axis_direction("bottom");#设置y轴：空⼼箭头、数值在右⽅ax.axis["y"] = ax.new_floating_axis(1, 0);ax.axis["y"].set_axisline_style("->", size = 1.0);ax.axis["y"].set_axis_direction("right");if__name__ == '__main__':a, b = map(int, input("请输⼊椭圆的长、短半径： ").split('')); fig = plt.figure(figsize=(5, 7))#初始化画布ax = axisartist.Subplot(fig, 111, title='MidpointElipse');#将绘图区对象添加到画布中fig.add_axes(ax)init(ax);x = 0;y = b;d1 = b*b+a*a*(-b+0.25); #增量初值ax.plot(x, y, 'r.');ax.plot(x, -y, 'r.');while(b*b*(x+1)<a*a*(y-0.5)): #法向量的x、y不⼀样⼤时if d1<0:d1 += b*b*(2*x+3);x += 1;else:d1 += b*b*(2*x+3)+a*a*(-2*y+2);x += 1;y -= 1;#画四个对称点ax.plot(x, y, 'r.');ax.plot(x, -y, 'r.');ax.plot(-x, y, 'r.');ax.plot(-x, -y, 'r.');#画到了法向量的x=y，即椭圆弧的下半部分d2 = b*b*(x+0.5)*(x+0.5)+a*a*(y-1)*(y-1)-a*a*b*b;while y>0: #终结条件y>0if d2<0:d2 += b*b*(2*x+2)+a*a*(-2*y+3);x += 1;y -= 1;else:d2 += a*a*(-2*y+3);y -= 1;ax.plot(x, y, 'r.');ax.plot(x, -y, 'r.');ax.plot(-x, y, 'r.');ax.plot(-x, -y, 'r.');plt.show()。

北京联合大学应用文理学院实验报告课程名称计算机图形学实验（实训）名称圆的扫描转换班级信息与计算科学2009级姓名学号同组者实验（实训）日期完成日期本实验（实训）所用学时统计预习实验（实训）报告总计评阅意见：成绩北京联合大学应用文理学院实验报告一、实验目的1、掌握用中点画圆法进行圆的扫描转换方法；2、掌握用Bresenham画圆法进行圆的扫描转换方法；3、理解中点画圆法与Bresenham画圆法的区别；二、算法原理介绍1、中点画圆算法假设x坐标为xp的各像素点中，与该圆弧最近者已确定，为P（xp,yp），那么，下一个与圆弧最近的像素只能是正右方的P1(xp+1,yp)，或右下方的P2（xp+1,yp-1）两者之一。

令M为P1和P2的中点，易知M的坐标为（xp+1,yp-0.5）。

显然，若M在圆内，则P1离圆弧近，应取为下一个像素；否则应取P2。

判别式d：d = F(M)=F(xp+1,yp-0.5)=(xp+1)^2+(yp-0.5)^2-R^2d的初始值为：d0 = F(1,R-0.5)=1+(R-0.5)^2-R^2=1.25-R在d≥0的情况下，取右下方像素P2，d = F(xp+2,yp-1.5)=(xp+2)^2+(yp-1.5)^2-R^2=d+2(xp-yp)+5在d<0的情况下，取正右方像素P1，d = F(xp+2,yp-0.5)=(xp+2)^2+(yp-0.5)^2-R^2=d+2xp+32、 Bresenham画圆算法假设生成圆心在坐标原点，半径为r，从x=0到x=y的1/8圆弧。

xi+1=xi +1相应的y则在两种可能中选择：y=yi，或者y=yi-1选择的原则是考察理想的y值是靠近yi还是靠近yi-1判别式：d i+1=2(xi+1)2+yi2+(yi-1)2-2r2判断式d的初始值为：d0= 3-2r。

如果d i+1>=0，则y=yi-1，di+2 =d i+1 + 4(xi- yi)+10如果d i+1<0，则y=yi，d i+2 =d i+1+ 4x i+6三、程序源代码1、中点画圆算法#include"graphics.h"#include"math.h"#include"conio.h"main(){void MidPointCircle(int,int);/*定义主函数变量，MidPointCircle中点画圆算法函数*/int gdriver,gmode; /*gdriver和gmode分别表示图形驱动器和模式*/gdriver=DETECT; /*DETECT是自动选择显示模式*/initgraph(&gdriver,&gmode,"c:\\tc3.0\\BGI");/*图形驱动文件的路径*/ MidPointCircle(200,YELLOW); /*定义圆的半径和颜色*/getch();/*getch();会等待你按下任意键，再继续执行下面的语句*/closegraph();/*关闭图形系统*/return(0); /*返回值为0*/}void MidPointCircle(int r,int color) /*定义函数变量半径和颜色*/{ int x,y;float d; /*float类型中小数位数为7位，即可精确到小数点后7位 */x=0; y=r; d=1.25-r;while(x<y) /*满足条件x<y时进入循环，不满足跳出*/{ if(d<0){d+=2*x+3; x++;}else { d+=2*(x-y)+5; x++; y--;}putpixel(x+200,y+200,color); putpixel(y+200,x+200,color);putpixel(200-x,y+200,color); putpixel(y+200,200-x,color);putpixel(200+x,200-y,color); putpixel(200-y,x+200,color);putpixel(200-x,200-y,color); putpixel(200-y,200-x,color);/* putpixel 在指定位置画一像素*/}}2、 Bresenham画圆算法#include"graphics.h"#include"math.h"#include"conio.h"main(){void Bresenham_Circle(int,int);/* Bresenham_Circle为 Bresenham画圆算法函数*/int gdriver,gmode;gdriver=DETECT;initgraph(&gdriver,&gmode,"c:\\tc3.0\\BGI");Bresenham_Circle(200,YELLOW); /*定义圆的半径和颜色*/getch();closegraph();return(0);}void Bresenham_Circle(int R,int color){ int x,y,delta,delta1,delta2,direction;x=0;y=R;delta=2*(1-R);while(y>=0) /*满足条件y>=0时进入循环，不满足跳出*/{putpixel(x+200,y+200,color); putpixel(y+200,x+200,color);putpixel(200-x,y+200,color); putpixel(y+200,200-x,color);putpixel(200+x,200-y,color); putpixel(200-y,x+200,color);putpixel(200-x,200-y,color); putpixel(200-y,200-x,color);if(delta<0){delta1=2*(delta+y)-1;if(delta1<=0)direction=1;else direction=2;}else if(delta>0){delta2=2*(delta-x)-1;if(delta2<=0) direction=2;else direction=3;}elsedirection=2;switch (direction)/*switch语句，即“切换”语句；case即“情况*/ {case 1:x++;delta+=2*x+1;break;/*执行 break 语句会退出当前循环或语句*/case 2:x++;y--;delta+=2*(x-y+1);break;case 3: y--;delta+=(-2*y+1);break;}}}四、实验结果图1中点画圆算法生成的圆半径r=200，颜色为黄色图2 Bresenham画圆算法生成的圆半径R=200，颜色为黄色五、总结与体会通过运用 C 语言环境下的图像显示设置，本次实验我学会了用中点画圆法、Bresenham 画圆法进行圆的扫描转换，更加深刻的理解了中点画圆法、Bresenham 画圆法进行圆的扫描转换的生成原理。