圆及圆弧生成算法.ppt

3.2 圆弧的扫描转换,对称性,（8，2） （x，y）,（8，2） （x，y）,（8，2） （x，y）,（8，2） （x，y）,（2，8） （y，x）,（2，8） （y，x）,（2，8） （y，x）,（2，8） （y，x）,P1 =(x,y) P5 =(-x,-y),P2 =(y,x) P6 =(-y,-x),P3 =(-y,x) P7 =(y,-x),P4=(-x,y) P8=(x,-y),3.2.1 圆弧的扫描法,已知圆的圆心坐标为（xc,yc），半径为R,圆的直角坐标方程表示为 (x-xc)2+(y-yc)2=R2,x0=xc-R y0= yc,缺点: (1)运算速度慢 (2)显示质量不好,角度DDA算法,圆弧的扫描法,正负法、圆弧的Bresenham算法、中点画圆法等,3.2 圆的生成算法,由圆的参数方程,推导出圆弧的增量算法的表达式:,缺点：所产生的圆是不封闭的，且该圆的半径有不断增大的趋势。,取微分,令,=02,为所画圆弧的圆心角单位为弧度,d 2-m 角度增量，m 为整数。,已知圆的圆心坐标为（0,0），半径为R,3.2.2 角度DDA算法(近似法),原因：,Pi+1是在Pi上加一个小的矢量而得到，这个矢量垂直于位置矢量Pi 。,因此新的半径经常比前一个半径大，从而得到的曲线是一条螺线。,将第二式中的 xi 用 xi+1 代替,则有:,为椭圆,d2-m ，当m=4时，此椭圆与精确圆之间的误差E1.6,3.2.3 椭圆差分法,2019/7/19 hjy- 5,1 pixel=R sin d,d=arc sin-11/R,令：,3.2.4 旋转法(正多边形逼近),3.2.4 旋转法(正多边形逼近),设圆的圆心为c(0,0),半径为R。假设圆弧的起始角和终止角分 别为0和1，把圆弧分割为n份，则两个顶点之间的夹角为 =（ 1 - 0 ）/n 。,设内接正多边形的一个顶点为 Pi(xi,yi)，cPi的幅角为i，则 xi=Rcosi yi=Rsini 顶点Pi+1的坐标为 xi+1=Rcos(i+) = xicos-yisin yi+1=Rsin(i+) = xisin+yicos,用正多边形迫近圆弧法,由此决定了一系列顶点，两个定点确定一条直线，n条直线逼近了个整个圆。,表示为矩阵形式，则内接正多边形的递推公式,计算一个点（xi+1,yi+1）只要作四次乘法。,xi+1=Rcos(i+) = xicos-yisin yi+1=Rsin(i+) = xisin+yicos,方程,2. F( x, y)=0 是二阶光滑,圆的方程为：,3. 每一个点的曲率半径步长 (1 pixel),3.2.5 正负法（隐函数曲线),若点Pi在圆内或圆上， 即 F(xi,yi) 0,若点Pi在圆外， 即 F(xi,yi) 0,以第一个1/4圆弧为例，取圆弧的最上方点为起始点(x0,y0)， x0=0 y0=R,由当前点Pi(xi,yi)选择下一点Pi+1(xi+1,yi+1)的规则是：,则,当xi+1= xi+1, yi+1= yi时，,当xi+1= xi, yi+1= yi-1时，,结论第一个1/4圆弧的正负法算法：,若F(xi,yi) 0 （点在内侧，下一点选外侧）,若F(xi,yi) 0 （点在外侧，下一点选内侧）,已知圆心坐标为（xc,yc），半径为R，,起始点(x0,y0) x0=xc y0=yc+R,存在的问题：,考虑过极限点的转向，即换向的规则。,当 时，有x向极值。,当 时，有y向极值。,以坐标原点为圆心的第一象限1/4圆为例,(0,R),(R,0),起点为(0,R)，按顺时针方向生成圆,则y为x的单调递减函数,设P(xi,yi)点为当前点圆上的亮点,下一个该显示的象素有三种可能:,右方象素H、,右下方D、,下方象素V,决定一象素使其与真正圆的距离的平方最小,圆在与点P(xi,yi)附近光栅网格的相交关系只有5种,1.基本思想,3.2.6 圆弧的Bresenham算法,五种情况分解图：,H,D,V全在圆内,H在圆外，D,V在圆内,D在圆上，H在圆外，V在圆内,D,H在圆外，V在圆内,D,V,H 全在圆外,取D点,取H点或D点,取D点或V点,取H点,取V点,首先计算圆心到右下角象素D的距离平方与圆心到圆弧上的点的距离平方之差,如果i0,说明D点在圆内,只能是1,2情况，可选D点或H点,设为圆到象素H的距离平方与圆到象素D的距离平方之差。,|(xi+1)2+(yi)2-R2|-|(xi+1)2+(yi-1)2-R2| Mh Md,如果0,说明圆到D点的距离大于圆到H点的距离，,应选H (xi+1,yi),如果0,应选D(xi+1,yi-1),如果=0,规定选D(xi+1,yi-1),对于情况2，左下角D总是位于圆内，而H点总是位于圆外,(xi+1)2+(yi-1)2-R20, = 2(i+ yi)-1,对于情况1,由于y为一单调递减函数，只能选取H点,因为： (xi+1)2+(yi)2-R20,(xi+1)2+(yi-1)2-R20, = (yi-1)2 -(yi)20,结论与情况2是一致的,所以有： (xi+1)2+(yi)2-R2=0,|(xi+1)2+(yi)2-R2|-|(xi+1)2+(yi-1)2-R2|,如果i0,说明D点在圆外,只能是4,5情况，可选V点或D点,设为圆到象素D的距离平方与圆到象素V的距离平方之差。,|(xi+1)2+(yi -1)2-R2|-|(xi)2+(yi-1)2-R2|,如果0,说明圆到V点的距离大,应选D(xi+1,yi-1),如果0,如果=0,规定选D(xi+1,yi-1),说明圆到D点的距离大,应选V(xi,yi-1),情况4: 由于D在圆外，而V在圆内:,(xi+1)2+(yi -1)2-R2=0,(xi)2+(yi-1)2-R20, = 2(ixi)-1,对于情况5,由于y为一单调递减函数，只能选取V点, = (xi+1)2 -(xi)20,结论与情况4是一致的,对于情况3,应选D点,归纳总结：,当i0时，,=0, 取H(xi+1,yi)点,0, 取D(xi+1,yi-1)点,当i0时，,=0, 取D(xi+1,yi-1)点,0, 取V(xi,yi-1)点,当i=0时，,取D(xi+1,yi-1)点,由上面的分析,增量算法的递推公式:,水平移动到H(xi+1,yi)点,Xi+1=xi+1,yi+1=yi,i+1 = (xi+1+1)2+(yi+1 -1)2-R2,(xi+1)2+(yi -1)2-R2, i+2xi+1+1,对角移动到D点,Xi+1=xi+1,yi+1=yi-1,i+1 = i+2xi+1 -2yi+1 +2,移动到V点,Xi+1=xi,yi+1=yi-1,i+1 = i-2yi+1 +1,圆弧的Bresenham算法的优点:起点和终点准确，分布均匀，计算简单。,举例:,画圆心为(0,0),半径R=8的四分之一的圆弧,初始条件:x1=0; y1=8; R=8,1=(x1+1)2+(y1-1)2 -R2 =1+49-64=-140;,HD=2(1+y1)-1=2(-14+8)-1=-130,取H点,2=1+2x2+1=-14+2*1+1=-110,HD =2(2+y2)-1 =2(-11+8)-1=-70,HD =2(3+y3)-1 =2(-6+8)-1=30,取D点,取H点,点亮点(0,8),可能点亮H或D点,x2 =1,y2 =8,3=2+2x3+1=-11+2*2+1=-60,x3 =2,y3 =8,x4 =3,y4 =7,4 = 3+2x4 -2y4 +2=-6+2*3-2*7+2=-120,HD =2(3+y4)-1 =2(-12+7)-1=-110,取H点,x4 =4,y4 =7,5 = 4+2x5 +1=-12+2*4+1=-30,HD=2(4+y4)-1=2(-3+7)-1=90,取D点,x5 =5,y5 =6,6 = 5+2x5 -2y5 +2=-3+2*5-2*6+2=-30,HD=2(6+y6)-1=2(-3+6)-1=50,取D点,x6 =6,y6 =5,7 = 6+2x6 -2y6 +2=-3+2*6-2*5+2=10,取D点,x7 =7,y7 =4,DV=2(6-x6)-1=2(1-6)-1=-110,8 = 7+2x7 -2y7 +2=1+2*7-2*4+2=90,DV=2(7-x7)-1=2(9-7)-1=30,取V点,x8 =7,y8 =3,9 = 8 -2y8 +1=9-2*3+1=40,DV=2(9-x8)-1=2(4-7)-1=-70,取D点,x9=8,y9 =2,10 = 9+2x9 -2y9+2=4+2*8-2*2+2=180,DV=2(10-x9)-1=2(18-8)-1=190,取V点,x10=8,y10 =1,11 = 10 -2y10 +1=19-2*2+1=160,DV=2(11-x10)-1=2(16-8)-1=150,取V点,x11 =8,y11 =0,y=0,结束,起点x=0 y=R,D0,D0,1/4圆程序流程图,只须讨论1/8圆，一般采用第二个8分圆 P为当前点亮象素，那么，下一个选择的象素可能是P1（Xp+1，Yp）或P2（Xp+1，Yp1)。,3.2.7 中点画圆算法（利用圆的对称性）,构造函数：F（X，Y）=X2 + Y2 - R2 ；则 F（X，Y）= 0 （X，Y）在圆上； F（X，Y） 0 （X，Y）在圆外。 设M为P1、P2间的中点，M=(Xp+1,Yp-0.5),M,P1,P2,3.2.7 中点画圆算法（利用圆的对称性）,有如下结论： F（M）= 0 ，在圆外，则取P2 为此，可采用如下判别式： d = F(M) = F(xp + 1, yp - 0.5) =(xp + 1)2 + (yp - 0.5) 2 - R2,M,P1,P2,d = F(M) = F(xp + 1, yp - 0.5) =(xp + 1)2 + (yp - 0.5) 2 - R2 若d0, 则P1 为下一个象素，那么再下一个象素的判别式为： d1 = F(xp + 2, yp - 0.5) = (xp + 2)2 + (yp - 0.5) 2 - R2 = d + 2xp +3 即d 的增量为 2xp +3.,M,P1,P2,若d=0, 则P2 为下一个象素，那么再下一个象素的判别式为： d1 = F(xp + 2, yp - 1.5) = (xp + 2)2 + (yp - 1.5) 2 - R2 = d + （2xp + 3）+（-2 yp + 2） 即d 的增量为 2 (xp - yp) +5. d的初值: d0 = F(1, R-0.5) = 1 + (R-0.5)2 - R2 = 1.25 - R,M,P1,P2,算法步骤： 1.输入圆的半径R。 2.计算初始值d=1.25-R、x=0、y=R。 3.绘制点(x,y)及其在八分圆中的另外七个对称点。 4.判断d的符号。若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。 5.当xy时，重复步骤3和4。否则结束。,MidpointCircle(int r) int x,y; float d; x=0; y=r; d=1.25-r; while(xy) Setpixel(x,y); if(d0) d+ = 2*x+3; x+; elsed+ = 2*(x-y) + 5; x+;y-; ,初始值d=1.25-R 若d=0,d 的增量为: 2(xp-yp)+5. 若d0, d 的增量为: 2xp+3.,第i个象素 d Pi(x,y) 1 d0=1.25-10=-8.750 P1(3,9) 5 d4=6.25-7=-0.750 P1(5,8) 7 d6=10.25-1=9.250 P1(6,7) 8 d7=9.25+3=12.250 P1(7,6),例子：设圆半径R=10,为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。 使用e=d-0.25代替d，(d = 1.25 R) 则 e0=1-R,void MidpointCircle1(int R) int x,y,d; x=0;y=R;d=1-R; SetPixel(x,y); while(xy) if(d0) d+=2*x+3;x+; else d+=2*(x-y)+5;x+;y-; SetPixel(x,y); ,上述算法能否再改进呢？ 注意到d的增量是x,y的线性函数， 每当x递增1，则d的增量递增x=2 每当y递减1，则d的增量递增y=2 x初始值=3；y初始值=-2r+2,void MidpointCircle2(int R) int x,y,deltax,deltay,d; x=0;y=R;d=1-R; deltax=3; deltay=2-R-R; SetPixel(x,y); while(xy) if(d0) d+=deltax;deltax+=2;x+; else d+=(deltax+deltay); deltax+=2;deltay+=2; x+;y-; SetPixel(x,y); ,3.3 椭圆的扫描转换 椭圆的特征 长半轴为a，短半轴为b的标准椭圆,F(x,y)=b2x2+a2y2-a2b2=0 对于椭圆上的点，有F(x,y)=0； 对于椭圆外的点，F(x,y)0； 对于椭圆内的点，F(x,y)0。 解决问题：沿x轴或y轴取单位距离均有斜率的绝对值大于1或小于1的曲线，怎么办？,在上半部分,法向量的y分量大 在下半部分,法向量的x分量大,上半部分,下半部分,法向量 两分量相等,M1,M2,在当前中点处，法向量（2b2(Xp+1)，2a2(Yp-0.5)的y分量比x分量大, 即：b2(Xp+1)a2(Yp-0.5),而在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分。,法向量斜率绝对值小于1 在y轴取单位步长,法向量斜率绝对值大于1 在x轴取单位步长,F(x,y)=b2x2+a2y2-a2b2=0 椭圆上一点处的法向量,中点椭圆算法,与圆的中点算法类似：确定一个象素后，接着在两个候选象素的中点计算一个判别式的值，由判别式的符号确定更近的点 先讨论椭圆弧的上部分 设(Xp，Yp)已确定，则下一待选像素的中点是(Xp+1,Yp-0.5) d1=F(Xp+1,Yp-0.5)= b2(Xp+1)2+a2(Yp-0.5)2-a2b2,根据d1的符号来决定下一像素是取正右方的那个，还是右下方的那个。 若d10，中点在椭圆内，取正右方象素，判别式更新为： d1=F(Xp+2,Yp-0.5)=d1+b2(2Xp+3) d1的增量为b2(2Xp+3),根据d1的符号来决定下一像素是取正右方的那个，还是右下方的那个。 当d10，中点在椭圆外，取右下方象素，更新判别式： d1=F(Xp+2,Yp-1.5)=d1+b2(2Xp+3)+a2(-2Yp+2) d1的增量为b2(2Xp+3)+a2(-2Yp+2),d1的初始条件：椭圆弧起点为(0，b)； 第一个中点为(1,b-0.5) 初始判别式： d1=F(1,b-0.5)=b*b+a*a(-b+0.25),转入下一部分，下一象素可能是正下方或右下方，此时判别式要初始化。 d2 = F(Xp+0.5,Yp-1) = b2(Xp+0.5)2+a2(Yp-1)2-a2b2 若d20,取右下方像素，则d2 = F(Xp+1.5,Yp-2) = d2 + b2(2Xp+2)+a2(-2Yp+3),对于下半部分： d2 = F(Xp+0.5,Yp-1) = b2(Xp+0.5)2+a2(Yp-1)2-a2b2 若d2=0,