圆及圆弧生成算法.ppt
《圆及圆弧生成算法.ppt》由会员分享,可在线阅读,更多相关《圆及圆弧生成算法.ppt(47页珍藏版)》请在三一文库上搜索。
1、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)显示质量不
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时,
3、此椭圆与精确圆之间的误差E1.6,3.2.3 椭圆差分法,2019/8/7 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+) = xis
4、in+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圆弧为例,取圆弧的最上方点为起始点
5、(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,
6、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,
7、说明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-
8、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)
9、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)
10、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
11、*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,
12、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,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 圆弧 生成 算法
链接地址:https://www.31doc.com/p-3276546.html