第19卷第2期太原重型机械学院学报Vol.19№21998年6月JOURNALOFTAIYUANHEAVYMACHINERYINSTITUTEJun.1998圆弧插补的一种改进算法张荣国边秀雪(太原重型机械学院,太原030024(山西临汾电力工业学校,临汾041000张继福(太原重型机械学院,太原030024摘要本文提出了一种圆弧插补的改进算法,它通过构选新的偏差判别式和递推式,不仅算法简单,计算机执行速度快,且提高了圆弧插补精度,在CAD和数控加工中有一定的适用价值。关键词圆弧插补;偏差判别;算法中图分类号TH126;TP39收稿日期:1997-09-10本文第一作者:男,1964年出生,太原重型机械学院计算机系讲师,研究方向为CAD/CG和系统建模。二维图形设计中,直线、圆弧和曲线是最常用的基本图形,在CG和CAD中提供了多种生成这些图形的算法,在显示器上显示和处理这些图形时,常用扫描线算法,在绘图机和数控加工中由于画笔和刀具的特点,常用的插补算法。插补运算就是给定起点和终点插补中间数据,使画笔或刀具沿X和Y方向每次走一个步距,直到完成整个直线、圆弧或其它图形的绘制和加工。圆弧插补的算法也很多,如DDA法、直接函数法等,但最常用的仍是逐点比较法,该算法简单明了,然而在插补范围内的某些区域插补精度不是太高,为此,本文提出了一种改进算法,它不仅算法简单、计算机执行时速度快,且提高了插补精度,这对于日益求精的高新技术及产品有着一定的适用价值。1算法基本原理1.1偏差判别式对于圆弧进行插补时,我们选定坐标原点过圆心;由于圆的对称性,我们只需对第一象限内的圆弧进行插补。根据圆的方程,给定一函数F=X2+Y2-R2(1在传统算法中对于插补过程中的任一点,基F≥0,该点在圆弧的外侧,沿-X方向步进;若F<0,该点在圆弧的内侧,沿+Y方向步进。如图1中所示,A点为当前插补点,它的下个步进点可为B点也可为C点,按传统算法,下个步进点只能选到B点,很显然B点的插补偏差比C点大。为了减少这种人为规定所造成的大偏差,提高插补精度,我们引入另一函数GG=F2Δx-F2Δy=[(x-12+y2-R22-(x2+(y+12-R2]2=-4(x+y(F-x+y=1(2若G>0,说明在(x,y点沿-X方向步进产生的偏差比沿+Y方向步进后产生的偏差大,下一步应沿+Y方向进行步进,到达(x,y+1;若G<0,说明在(x,y点沿-X方向步进产生的偏差比沿+Y方向步进后产生的偏差小,下一步应沿-X方向步进,到达(x-1,y点,若G=0,沿两个方向步进后产生的偏差相同,此时插补点落在450线的圆弧上,我们取-X方向步进。由于我们是在第一象限内对圆弧进行逆向插补,(2式中x,y>0始终成图1圆弧插补立,故此,偏差判别式可简化如下:f=F-x+y+1(3若f≥0,沿-X方向步进;f<0,沿+Y方向步进。1.2递推式和终判条件的确定判别式(3中F是含有当前插补点坐标的一个二次多项式,每步进一次都需要进行偏差计算,直接用(3要花费大量的计算时间,为此,我们需要确定(3式的递推式,用尽量简单直至加减运算来取代判别式,这样可大大提高运算速度。取插补过程中的第i步,则有若fi<0,则到达新点后,下一步沿两个方向步进产生的偏差fi+1=Fi+1-xi+1+yi+1+1=x2i+1+y2i+1-R2-xi+1+yi+1+1=fi+2yi+1(4若fi≥0,则有fi+1=fi-2xi+1(5其中i=0,1,2,3,…,n;起始点处x0=R,y0=0,f0=-R+1.当终点靠近Y轴时,终点附近的圆弧趋向于平行X轴,故最后一次步进方向一定平tf于X轴,此时只有选X方向作为计数方向,才能到达终点。因此,我们选X方向作为终判的计数方向,当x=0时,到达插补圆弧的终点。2具体算法本文的圆弧插补算法用类C语言可描述如下:Mcircle(RintR;{x0=R;y0=0;f0=-R+1;f=f0;while(x0>0431太原重型机械学院学报1998年{if(f>=0{x=x0-1;y=y0;f=f0-x-x;}else{x=x0;y=y0+1;f=f0=y=y}draw((x0,y0,(x,y;x0=x;y0=y;f0=f;}/3while3/}/3mcircle3/3结束语(1选择插补点和理论圆弧的偏差作为新的偏差判别式,使每次插补时都选用偏差小的作为插补点,和简单的插补点在圆内圆外作为判别式的传统算法相比,本算法插补精度高。(2经处理后的偏差判别递推式,能保证步进方向判别需求,式中所含项为简单的加减运算,且比传统算法少一次加法运算,因此该算法插补速度高。图2所示为传统算法和本文算法对圆弧插补的结果。(a传统插补(b改进插补图2圆弧插补算法比较参考文献1孙家广,杨长贵.计算机图形学.北京:清华大学出版社,1995,165~215531第1...