圆弧的生成算法研究

《圆弧的生成算法研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、圆弧的生成算法研究本文由天空乐园大学生旅游网整理分享摘要本文研究了计算机图形学中圆弧生成的几种算法，有直角坐标算法、DDA算法、中心点法和Bresenham算法，并比较了它们的优缺点。其中前三种算法存在计算速度慢、精度差等的较大的缺点。本文着重介绍了使用广泛Bresenham算法。Bresenham画圆算法是常用的一种画圆算法,它很大程度上客服了计算速度慢、精度差的缺点，是很好的圆弧生成算法。关键字：圆弧生成；直角坐标算法；DDA算法；中心点法；Bresenham算法；一、引言计算机图形学(ComputerGraphi

2、cs，简称CG)是一种使用数学算法将二维或三维图形转化为计算机显示器的栅格形式的科学。简单地说，计算机图形学的主要研究内容就是研究如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与算法。计算机图形学的研究内容非常广泛，如图形硬件、图形标准、图形交互技术、光栅图形生成算法、曲线曲面造型、实体造型、真实感图形计算与显示算法、非真实感绘制，以及科学计算可视化、计算机动画、自然景物仿真、虚拟现实等。目前，绝大多数计算机图形系统使用的是阴极射线管显示器（CRT），显示器被分成若干大小相等的像素。通过控制

3、使像素或暗或亮，从而使屏幕得到所需要的图形。这样，在显示器上显示的图形就存在误差，比如在显示器上显示一条直线，不可能从一个像素到另一个像素之间直接画一条直线，而是通过一系列的靠近直线的像素表示。怎样快速和精确地生成所需的图形就成为计算机图形学关心的问题。二、基本理论目前，圆弧的生成算法有很多种，本文主要研究圆弧生成的直角坐标算法、DDA算法、中心点法和Bresenham算法，然后比较这几个算法的优缺点，从而说明Bresenham算法的快速，精确。2.1直角坐标系算法直角坐标法是圆弧生成算法中一种比较简单的算法。由圆的方

4、程其中以为圆心坐标，取x为自变量，可知y为：（1）１１由式（1）可得出圆弧的直角坐标法：（2）在式（2）这个直角坐标算法中，x以0到R等步长变化，当x越接近R时，圆的斜率越大，计算出来的y却不是间隔均匀的，这样画出的圆弧精度不高；在计算中，由于采用了平方、开方运算和取整运算，画圆时速度慢，算法效率不高，并且存在很大的误差。所以这个算法在实际的应用中很少采用，这里只是做一个简单说明。2.2DDA（数值微分法）算法(0,0)(R,0)图1圆心坐标原点由式（1）可知圆弧的参数方程为：（3）说明：这里只给出圆心坐标在原点情况的

5、图形（图1）。在式（3）中，为半径的旋转角度，对式（3）两边求导得到圆的极坐标方程：（4）由于：（5）由式（3）和式（4）可得到圆弧的DDA算法１１（6）在这个算法中，涉及到乘法运算和取整运算，输出的精度低；由于变化小，圆弧输出效率低。2.3中心点法2.3.1中心点法的具体内容　为了简便起见,只考虑中心在原点,半径为R的圆。对于中心不在原点的圆,可先通过平移变换,转化为中心在原点的圆。考虑到圆的对称性,在具体进行扫描转换时,只需对1/8圆实施即可。如果要显示一个整圆,只要在显示上确定一点(x,y),利用对称性原理同时显

6、示圆周上其它7个对称点,它们分别是(y,x),(y,-x),(x,-y),(-y,-x),(-y,x),(-x,y),(-x,-y)。如下图2：图2下面讨论从(0,R)到顺时针确定最佳逼近于该圆弧的像素序列。假定任一像素点为最接近理想圆弧的点并确定,那么下一像素点只能是正右方的像素点或右下方的像素点。如下图3所示。１１图3当前像素与下一个像素的候选者构造函数：。1)圆上的点；2)圆内的点；3)圆外的点。假设为的中点，如果，说明在圆内,离圆弧更近,应选为下一像素点;如果,说明在圆外,离圆弧更近,应选为下一像素点;如果,说

7、明、与圆弧等距离,选任意一点皆可,约定选取点。构造判别式若，选为下一像素点;再构造下一个判别式：如图4所示：１１图4若，选为下一个像素点；在构造下一个判别式：如图5所示图5由于起始点是,判别式的初始值为１１依据的正负,就可以选出下一个要选择的点,同理依据、的正负,可以递推出后续的选择点。在这个算法中,涉及到取整运算和乘法运算,输出的精度低。2.3.2中心点法的程序代码voidMidPointCircle(intr,intcolor){intx,y,dx=0;y=r;d=5-4r;CirclePoint(x,y,colo

8、r);while(x<=y){if(d<=0)d+=8x+12;else{d+=8(x-y)+20;y--;}x++;CirclePoint(x,y,color);}}2.3.3利用中心点法实现圆弧的绘制如下图图6使用中心点法绘制的圆弧2.4Bresenham算法2.4.1Bresenham算法的具体内容１１Bresenham画圆