圆及圆弧生成算法市公开课金奖市赛课一等奖课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,3.2 圆弧扫描转换,对称性,x,y,0,（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）,P,1,=(x,y)P,5,=(-x,-y),P,2,=(y,x)P,6,=(-y,-x),P,3,=(-y,x)P,7,=(y,-x),P,4,=(-x,y)P,8,=(x,-y),第1页,第1页,3.2.1,圆弧扫描法,已知圆圆心坐标为（x,c,y,c,），半径为R,圆直角坐标方程表示为 (x-x,c,),2,+(y-y,c,),2,=R,2,x,0,=x,c,-R,y,0,=,y,c,x,i+1,=x,i,+1,y,i+1,(x,i,+1,Round,(y,i+1,),缺点,:,(1)运算速度慢,(2)显示质量不好,(x,c,y,c,),(x,c,-R,y,c,),角度DDA算法,圆弧扫描法,正负法、圆弧Bresenham算法、中点画圆法等,3.2圆生成算法,第2页,第2页,由圆参数方程,推导出圆弧增量算法表示式:,缺点：所产生圆是不封闭，且该圆半径有不断增大趋势。,取微分,令,x,0,=R,y,0,=0,起点(x,0,y,0,),=02,为所画圆弧圆心角,单位为弧度,d 2,-m,角度增量，m 为整数。,已知圆圆心坐标为（0,0），半径为R,(0,0),(R,0),3.2.2角度DDA算法(近似法),第3页,第3页,P,i,P,i+1,原因：,P,i+1,是在P,i,上加一个小矢量而得到，这个矢量垂直于位置矢量P,i。,因此新半径经常比前一个半径大，从而得到曲线是一条螺线。,将第二式中,x,i,用,x,i+1,代替,则有:,y,i+1,=y,i,+x,i+1,d,=,y,i,+(x,i,-y,i,d,),d,=,d,x,i,+(1-d,2,),y,i,x,i+1,=x,i,-y,i,d,为椭圆,d2,-m,，当m=4时，此椭圆与准确圆之间误差E1.6,3.2.3椭圆差分法,第4页,第4页,10/10/hjy-5,d,P,i+1,P,i,O,X,Y,1 pixel=R,sin d,d,=arc sin,-1,1/R,令：,3.2.4旋转法(正多边形迫近),第5页,第5页,3.2.4旋转法(正多边形迫近),设圆圆心为,c,(0,0),半径为,R,。,假设圆弧起始角和终止角分,别为,0,和,1,，,把圆弧分割为,n,份，则两个顶点之间夹角为,=（,1,-,0,）/n,。,设内接正多边形一个顶点为,P,i,(,x,i,y,i,),，,cP,i,幅角为,i,，,则,x,i,=,R,cos,i,y,i,=,R,sin,i,顶点,P,i,+1,坐标为,x,i,+1,=,R,cos(,i,+,),=,x,i,cos,-,y,i,sin,y,i,+1,=,R,sin(,i,+,),=,x,i,sin,+,y,i,cos,用正多边形迫近圆弧法,由此决定了,一系列顶点，两个定点拟定一条直线，n条直线迫近了个整个圆。,第6页,第6页,表示为矩阵形式，则内接正多边形递推公式,计算一个点（,x,i,+1,y,i,+1,）只要作四次乘法。,x,i,+1,=,R,cos(,i,+,),=,x,i,cos,-,y,i,sin,y,i,+1,=,R,sin(,i,+,),=,x,i,sin,+,y,i,cos,第7页,第7页,x,y,(x,c,y,c,),方程,若F(x,y),0,点(x,y)在圆,外,若F(x,y),=,0,点(x,y)在圆,上,2.F(x,y)=0 是二阶光滑,F,F,F,F,1.F(x,y)=0 划分平面域为3个点集,函数特点：,F,F,圆方程为：,3.每一个点曲率半径步长 (1 pixel),3.2.5正负法（隐函数曲线),第8页,第8页,(0,R),若点P,i,在圆内或圆上，,即 F(x,i,y,i,)0,若点P,i,在圆外，,即,F(x,i,y,i,),0,以第一个1/4圆弧为例，取圆弧最上方点为起始点(x,0,y,0,)，,x,0,=0 y,0,=R,点P,i+1,取R点，即x,i+1,=x,i,+1,y,i+1,=y,i,点P,i+1,取,B点，即,x,i+1,=x,i,y,i+1,=y,i,-1,由当前点,P,i,(x,i,y,i,),选择下一点,P,i+1,(x,i+1,y,i+1,),规则是：,x,y,o,第9页,第9页,则,当x,i+1,=x,i,+1,y,i+1,=y,i,时,，,当x,i+1,=x,i,y,i+1,=y,i,-1时,，,第10页,第10页,结论第一个1/4圆弧正负法算法：,若F(x,i,y,i,)0（点在内侧，下一点选外侧）,若F(x,i,y,i,)0（点在外侧，下一点选内侧）,x,i+1,=x,i,+1,y,i+1,=y,i,x,i+1,=x,i,y,i+1,=y,i,-1,已知圆心坐标为（x,c,y,c,），半径为R，,起始点(x,0,y,0,)x,0,=x,c,y,0,=y,c,+R,第11页,第11页,存在问题：,考虑过极限点转向，即换向规则。,x,y,o,极限点,极限点,当,时，有x向极值。,当,时，有y向极值。,第12页,第12页,以坐标原点为圆心第一象限1/4圆为例,X,Y,O,V(x,i,y,i,-1),P(x,i,y,i,),H(x,i,+1,y,i,),D(x,i,+1,y,i,-1),(0,R),(R,0),起点为(0,R)，按顺时针方向生成圆,则y为x单调递减函数,设P(x,i,y,i,)点为当前点圆上亮点,下一个该显示象素有三种也许:,右方象素H、,右下方D、,下方象素V,决定一象素使其与真正圆距离平方最小,2,2,2,),1,(,R,y,x,m,i,i,V,-,-,+,=,2,2,2,),1,(,),1,(,R,y,x,m,i,i,D,-,-,+,+,=,2,2,2,),1,(,R,y,x,m,i,i,H,-,+,+,=,圆在与点P(x,i,y,i,)附近光栅网格相交关系只有5种,1,2,3,4,5,1.基本思想,3.2.6圆弧Bresenham算法,第13页,第13页,五种情况分解图：,H,D,V全在圆内,H在圆外，D,V在圆内,D在圆上，H在圆外，V在圆内,D,H在圆外，V在圆内,D,V,H 全在圆外,3,H,D,V,5,H,D,V,4,H,D,V,2,D,V,H,V(x,i,y,i,-1),P(x,i,y,i,),H(x,i,+1,y,i,),D(x,i,+1,y,i,-1),1,2,3,4,5,1,H,D,V,取D点,取H点或D点,取D点或V点,取H点,取V点,第14页,第14页,首先计算圆心到右下角象素D距离平方与圆心到圆弧上点距离平方之差,假如,i,0,阐明D点在圆内,只能是1,2情况，可选D点或H点,设,为圆到象素H距离平方与圆到象素D距离平方之差。,|(x,i,+1),2,+(y,i,),2,-R,2,|-|(x,i,+1),2,+(y,i,-1),2,-R,2,|,Mh Md,假如,0,应选D(x,i+1,y,i,-1),假如,=0,要求选D(x,i+1,y,i,-1),V(x,i,y,i,-1),P(x,i,y,i,),H(x,i,+1,y,i,),D(x,i,+1,y,i,-1),1,2,3,第15页,第15页,对于情况2，左下角D总是位于圆内，而H点总是位于圆外,(x,i,+1),2,+(y,i,-1),2,-R,2,0,=2(,i,+,y,i,)-1,对于情况1,由于y为一单调递减函数，只能选取H点,由于：,(x,i,+1),2,+(y,i,),2,-R,2,0,(x,i,+1),2,+(y,i,-1),2,-R,2,0,=,(y,i,-1),2,-(y,i,),2,=0,V(x,i,y,i,-1),P(x,i,y,i,),H(x,i,+1,y,i,),D(x,i,+1,y,i,-1),1,2,3,|(x,i,+1),2,+(y,i,),2,-R,2,|-|(x,i,+1),2,+(y,i,-1),2,-R,2,|,第16页,第16页,假如,i,0,阐明D点在圆外,只能是4,5情况，可选V点或D点,设,为圆到象素D距离平方与圆到象素V距离平方之差。,|(x,i,+1),2,+(y,i,-1),2,-R,2,|-|(x,i,),2,+(y,i,-1),2,-R,2,|,假如,0,假如,=0,要求选D(x,i+1,y,i,-1),阐明圆到D点距离大,应选V(x,i,y,i,-1),情况4:,由于D在圆外，而V在圆内:,(x,i,+1),2,+(y,i,-1),2,-R,2,=0,(x,i,),2,+(y,i,-1),2,-R,2,0,结论与情况4是一致,对于情况3,应选D点,V(x,i,y,i,-1),P(x,i,y,i,),H(x,i,+1,y,i,),D(x,i,+1,y,i,-1),4,5,第17页,第17页,归纳总结：,当,i,0时，,0,取D,(x,i,+1,y,i,-1)点,当,i,0时，,0,取V,(x,i,y,i,-1)点,当,i,=0时，,取D,(x,i,+1,y,i,-1)点,由上面分析,增量算法递推公式:,水平移动到,H,(x,i,+1,y,i,)点,X,i+1,=,x,i,+1,y,i+1,=,y,i,i+1,=,(x,i+1,+1),2,+(y,i+1,-1),2,-R,2,(x,i,+1),2,+(y,i,-1),2,-R,2,i,+2x,i+1,+1,对角移动到,D,点,X,i+1,=,x,i,+1,y,i+1,=,y,i,-1,i+1,=,i,+2x,i+1,-2y,i+1,+2,V(x,i,y,i,-1),P(x,i,y,i,),H(x,i,+1,y,i,),D(x,i,+1,y,i,-1),第18页,第18页,移动到,V,点,X,i+1,=,x,i,y,i+1,=,y,i,-1,i+1,=,i,-2y,i+1,+1,V(x,i,y,i,-1),P(x,i,y,i,),H(x,i,+1,y,i,),D(x,i,+1,y,i,-1),圆弧Bresenham算法长处:,起点和终点准确，分布均匀，计算简朴。,正负法绘制圆,Bresenham法绘制圆,第19页,第19页,举例:,画圆心为(0,0),半径R=8四分之一圆弧,初始条件,:x,1,=0;y,1,=8;R=8,1,=(x,1,+1),2,+(y,1,-1),2,-R,2,=1+49-64=-140;,HD,=2(,1,+y,1,)-1=2(-14+8)-1=-130,取H点,2,=,1,+2x,2,+1=-14+2*1+1=-110,HD,=2(,2,+y,2,)-1,=2(-11+8)-1=-70,取D点,取H点,点亮点(0,8),也许点亮H或D点,x,2,=1,y,2,=8,3,=,2,+2x,3,+1=-11+2*2+1=-60,x,3,=2,y,3,=8,x,4,=3,y,4,=7,4,=,3,+2x,4,-2y,4,+2=-6+2*3-2*7+2=-120,HD,=2(,3,+y,4,)-1,=,2(-12+7)-1=-110,取H点,x,4,=4,y,4,=7,5,=,4,+2x,5,+1=-12+2*4+1=-30,取D点,x,5,=5,y,5,=6,6,=,5,+2x,5,-2y,5,+2=-3+2*5-2*6+2=-30,取D点,x,6,=6,y,6,=5,V(x,i,y,i,-1),P(x,i,y,i,),H(x,i,+1,y,i,),D(x,i,+1,y,i,-1),第20页,第20页,7,=,6,+2x,6,-2y,6,+2=-3+2*6-2*5+2=10,取D点,x,7,=7,y,7,=4,DV,=2(,6,-x,6,)-1=2(1-6)-1=-110,DV,=2(,7,-x,7,)-1=2(9-7)-