实验二 圆的扫描转换算法

实验2 圆的扫描转换一、实验要求基本要求用Bresenham画圆算法实现圆的绘制。

提高要求用Bresenhamg画圆算法实现奥运会五环标志的绘制。

二、实验报告对下列内容逐项填写，适当添加空白页。

1.算法思想Bresenham画圆算法又称中点画圆算法，与Bresenham 直线算法一样，其基本的方法是利用判别变量来判断选择最近的像素点，判别变量的数值仅仅用一些加、减和移位运算就可以计算出来。

为了简便起见，考虑一个圆心在坐标原点的圆，而且只计算八分圆周上的点，其余圆周上的点利用对称性就可得到。

为什么只计算八分圆周上的点就可以了。

和直线算法类似，圆也有一个“八对称性”。

显然，我们只需要知道了圆上的一个点的坐标 (x, y) ，利用八对称性，我们马上就能得到另外七个对称点的坐标。

和直线算法类似，Bresenham画圆算法也是用一系列离散的点来近似描述一个圆。

2.程序流程图2.源程序清单和结果画圆的程序int d,x,y,x0,y0,r=100;d=3-2*r; x=0; y=r; x0=200; y0=200; //(x0,y0)圆心坐标while(y>=x){ pDC->SetPixel(x+x0,y+y0,RGB(0,0,0)); if(d<0)d=d+4*x+6;elsed=d+4*x-4*y+10,y--;x++;pDC->SetPixel(x+x0,-y+y0,RGB(0,0,0)); pDC->SetPixel(-x+x0,-y+y0,RGB(0,0,0)); pDC->SetPixel(-x+x0,y+y0,RGB(0,0,0)); pDC->SetPixel(-y+x0,x+y0,RGB(0,0,0)); pDC->SetPixel(-y+x0,-x+y0,RGB(0,0,0)); pDC->SetPixel(y+x0,x+y0,RGB(0,0,0)); pDC->SetPixel(y+x0,-x+y0,RGB(0,0,0)); }五环程序int d,x,y,x0,y0,r=53;d=3-2*r; x=0; y=r; x0=200; y0=200; //(x0,y0)圆心坐标while(y>=x){ pDC->SetPixel(x+x0,y+y0,RGB(0,0,255));if(d<0)d=d+4*x+6;elsed=d+4*x-4*y+10,y--;x++;pDC->SetPixel(x+x0,-y+y0,RGB(0,0,255));pDC->SetPixel(-x+x0,-y+y0,RGB(0,0,255));pDC->SetPixel(-x+x0,y+y0,RGB(0,0,255));pDC->SetPixel(-y+x0,x+y0,RGB(0,0,255));pDC->SetPixel(-y+x0,-x+y0,RGB(0,0,255));pDC->SetPixel(y+x0,x+y0,RGB(0,0,255));pDC->SetPixel(y+x0,-x+y0,RGB(0,0,255));}d=3-2*r; x=0; y=r; x0=320; y0=200; //(x0,y0)圆心坐标while(y>=x){ pDC->SetPixel(x+x0,y+y0,RGB(0,0,0));if(d<0)d=d+4*x+6;elsed=d+4*x-4*y+10,y--;x++;pDC->SetPixel(x+x0,-y+y0,RGB(0,0,0));pDC->SetPixel(-x+x0,-y+y0,RGB(0,0,0));pDC->SetPixel(-x+x0,y+y0,RGB(0,0,0));pDC->SetPixel(-y+x0,x+y0,RGB(0,0,0));pDC->SetPixel(-y+x0,-x+y0,RGB(0,0,0));pDC->SetPixel(y+x0,x+y0,RGB(0,0,0));pDC->SetPixel(y+x0,-x+y0,RGB(0,0,0));}d=3-2*r; x=0; y=r; x0=440; y0=200; //(x0,y0)圆心坐标while(y>=x){ pDC->SetPixel(x+x0,y+y0,RGB(255,0,0));if(d<0)d=d+4*x+6;elsed=d+4*x-4*y+10,y--;x++;pDC->SetPixel(x+x0,-y+y0,RGB(255,0,0));pDC->SetPixel(-x+x0,-y+y0,RGB(255,0,0));pDC->SetPixel(-x+x0,y+y0,RGB(255,0,0));pDC->SetPixel(-y+x0,x+y0,RGB(255,0,0));pDC->SetPixel(-y+x0,-x+y0,RGB(255,0,0));pDC->SetPixel(y+x0,x+y0,RGB(255,0,0));pDC->SetPixel(y+x0,-x+y0,RGB(255,0,0));}d=3-2*r; x=0; y=r; x0=260; y0=260; //(x0,y0)圆心坐标while(y>=x){ pDC->SetPixel(x+x0,y+y0,RGB(255,255,0));if(d<0)d=d+4*x+6;elsed=d+4*x-4*y+10,y--;x++;pDC->SetPixel(x+x0,-y+y0,RGB(255,255,0));pDC->SetPixel(-x+x0,-y+y0,RGB(255,255,0));pDC->SetPixel(-x+x0,y+y0,RGB(255,255,0));pDC->SetPixel(-y+x0,x+y0,RGB(255,255,0));pDC->SetPixel(-y+x0,-x+y0,RGB(255,255,0));pDC->SetPixel(y+x0,x+y0,RGB(255,255,0));pDC->SetPixel(y+x0,-x+y0,RGB(255,255,0));}d=3-2*r; x=0; y=r; x0=380; y0=260; //(x0,y0)圆心坐标while(y>=x){ pDC->SetPixel(x+x0,y+y0,RGB( 0,255,0));if(d<0)d=d+4*x+6;elsed=d+4*x-4*y+10,y--;x++;pDC->SetPixel(x+x0,-y+y0,RGB( 0,255,0));pDC->SetPixel(-x+x0,-y+y0,RGB( 0,255,0));pDC->SetPixel(-x+x0,y+y0,RGB( 0,255,0));pDC->SetPixel(-y+x0,x+y0,RGB( 0,255,0));pDC->SetPixel(-y+x0,-x+y0,RGB( 0,255,0));pDC->SetPixel(y+x0,x+y0,RGB( 0,255,0));pDC->SetPixel(y+x0,-x+y0,RGB( 0,255,0));}4.实验总结Bresenham确实是一种很快速的的算法。

计算机图形学——圆的扫描转换（基本光栅图形算法）与直线的⽣成类似，圆弧⽣成算法的好坏直接影响到绘图的效率。

本篇博客将讨论圆弧⽣成的3个主要算法，正负法、Bresenham 法和圆的多边形迫近法，在介绍算法时，只考虑圆⼼在原点，半径为R的情况。

⼀、正负法1、基本原理假设已选取Pi-1为第i-1个像素，则如果Pi-1在圆内，就要向圆外⽅向⾛⼀步；若已在圆外就要向圆内⾛⼀步。

总之，尽量贴近圆的轮廓线。

2、正负法的具体实现1）圆的表⽰：设圆的圆⼼为(0,0),半径为R，则圆的⽅程为：F(x,y)=x2+y2–R2=0当点(x,y)在圆内时，F(x,y)<0。

当点(x,y)在圆外时，F(x,y)>0。

2）实现步骤第1步：x0=0，y0=R第2步：求得Pi(x i,y i)后找点P i+1的原则为：当P i在圆内时(F(xi,yi)≤0)，要向右⾛⼀步得P i+1，这是向圆外⽅向⾛去。

取x i+1= x i+1, y i+1= y i当P i在圆外时(F(xi,yi)>0)，要向下⾛⼀步得P i+1，这是向圆内⽅向⾛去，取x i+1= x i, y i+1= y i-1⽤来表⽰圆弧的点均在圆弧附近且 F(xi, yi)时正时负假设已经得到点（x i, y i），则容易算出F(x i, y i)，即确定了下⼀个点（x i＋1, y i＋1），则如何计算F(x i+1, y i+1)，以确定下下个点（x i＋2, y i＋2）？分为两种情况：右⾛⼀步后：x i+1=x i+1，y i+1=y i，此时：F(x i+1, y i+1)=x i+12+y i2-R2=x i2+y i2-R2+2x i+1 = F(x i, y i)+2x i+1下⾛⼀步后：x i+1=x i，y i+1=y i-1， 此时：F(x i+1, y i+1)=x i2+（y i-1)2-R2= F(x i, y i)-2y i+1由此可得：确定了F(xi+1, yi+1)之后，即可决定下⼀个点(xi+2, yi+2)，选择道理同上。

圆形扫描曲线公式一、圆形的标准方程。

在平面直角坐标系中，圆心为(a,b)，半径为r的圆的标准方程为：(x - a)^2+(y -b)^2=r^2。

1. 圆心在原点（0,0）的情况。

当圆心在原点时，即a = 0，b=0，圆的方程为x^2+y^2=r^2。

- 例如，当r = 2时，方程为x^2+y^2=4，这个圆上的点(x,y)到原点的距离都为2。

2. 参数方程。

对于圆(x - a)^2+(y - b)^2=r^2，其参数方程为x=a + rcosθ y = b+rsinθ（其中θ为参数，θ∈[0, 2π)）。

- 以圆心在原点的圆x^2+y^2=r^2为例，其参数方程为x = rcosθ y=rsinθ。

当r = 1时，随着θ从0变化到2π，点(x,y)=(cosθ,sinθ)将沿着单位圆扫描一周。

二、圆形扫描相关的曲线公式应用。

（一）极坐标方程下的圆。

在极坐标系中，圆心在极点，半径为r的圆的极坐标方程为ρ = r。

1. 与直角坐标方程的转换。

- 由x=ρcosθ，y = ρsinθ，对于圆x^2+y^2=r^2，将x=ρcosθ，y=ρsinθ代入可得：(ρcosθ)^2+(ρsinθ)^2=r^2，化简得ρ^2(cos^2θ+sin^2θ)=r^2，因为cos^2θ+sin^2θ = 1，所以ρ = r。

（二）圆形扫描在物理学等领域中的应用。

1. 在电磁学中的环形电流磁场。

- 假设环形电流的圆心在原点，半径为R。

根据毕奥 - 萨伐尔定律，在环形电流轴线上一点的磁感应强度B的计算会涉及到圆形的相关公式。

当计算距离圆心为z的轴线上一点的磁感应强度时，需要对电流元在该点产生的磁场进行积分，而电流元的位置可以用圆的参数方程来表示，即x = Rcosθ y = Rsinθ，这有助于分析磁场的分布情况，其最终的磁感应强度公式为B=frac{μ_0IR^2}{2(R^2+z^2)^(3)/(2)}，这里圆形的相关参数方程在推导过程中起到了重要的定位电流元位置的作用。

圆的扫描转换一、算法原理本节主要讲解仅包含加减操作的顺时针绘制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 为主位移方向。

扫描转换算法——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()。