圆及圆弧生成算法.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-Ry0=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椭圆差分法,2023/7/31 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=0y=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=2x初始值=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,取正下方像素，则d2=F(Xp+0.5,Yp-2)=d2+a2(-2Yp+3)下半部分弧的终止条件为 y=0,椭圆算法步骤：,1、d1的初始条件：椭圆弧起点为(0，b)；2、第一个中点为(1,b-0.5)初始递推式：d1=F(1,b-0.5)=b*b+a*a(-b+0.25)3、进入上半部分，下一象素可能是正右方或右下方，此时递推式要初始化。d1=F(Xp+0.5,Yp-1)=b2(Xp+0.5)2+a2(Yp-1)2-a2b2 a、若d1=0,取右下方像素，则 d1=F(Xp+2,Yp-1.5)=d2+b2(2Xp+3)+a2(-2Yp+2)4、直到a2Ypb2Xp5、进入下半部分6、下半部分弧的终止条件为y=0,注意：上半部分的终止判别下半部分递推式的初值,程序：MidpointEllipe(int a,int b)int x,y;float d1,d2;x=0;y=b;d1=b*b+a*a*(-b+0.25);SetPixel(x,y);while(b*b*(x+1)0)if(d2 0)d2+=b*b*(2*x+2)+a*a*(-2*y+3);x+;y-；else d2+=a*a*(-2*y+3);y-;SetPixel(x,y);,上机：1.编制直线的Bresenham算法程序；（下次上机时完成）2.读懂并上机调试、运行圆弧的中点画圆算法程序；,手工：画圆心为(0,0),半径R=10的四分之一的圆弧用圆弧的Bresenham算法和中点画圆算法计算各个象素点的坐标值,减少取整;避免浮点运算;双向计算.,1.更好的方法,思考:,