等分圆周生成圆和椭圆快速算法

摘 要： 在等分圆周角的前提下，以泰勒公式为基础，构造出圆和椭圆的生成算法，并对算法的误差进行了详细分析，给出了算法的适用范围。算法生成的点分布均匀，可应用于对图形输出有较高要求的场合。预处理后，计算每个点对只需要11次加法运算，避免了大量的三角函数运算，运算速度快、运算精度高。该快速算法的构造方法新颖，具有较强的理论和实用价值。

关键词： 等分圆周； 圆； 椭圆； 泰勒公式； 算法

中图分类号：TP391 文献标志码：A 文章编号：1006-8228（2014）08-37-03

A quick algorithm generating circle and ellipse about equal division circumference

Zhang Bo

（College of Bussiness， Jiamusi University， Jiamusi， Heilongjiang 154000， China）

Abstract： Based on equal division circumference angle and Taylor formula， algorithm of circle and ellipse is introduced. The errors of algorithm are analyzed and application scope of the algorithm is given. The algorithm generates uniform distribution dots and can be applied in the cases where graph output is of high quality. After preprocessing， every graphic dots are calculated by 11 times addition， avoiding much trigonometric function calculating. The algorithm is fast and precise， which is of practical value. A new and original construction method is proposed. It has great theoretical and practical value.

Key words： equal division circumference； circle； ellipse； Taylor Formula； algorithm

0 引言

圆和椭圆的生成算法较多，比较有名的有Bresenham画圆算法，圆和椭圆的中点生成法[1]。但以上算法生成的绘图点分布不均匀，视觉效果不好。等分圆生成的点之间距离相等，显示效果最佳。以等分圆周生成的椭圆效果也比普通方法有很显著的改善。

根据参数方程x=acos（θ），y=bsin（θ），采用直接计算的方法可生成对应的绘图点。由于有三角函数运算和乘法运算，逐点计算运算量较大。文献[4]给出了通过构造递推公式减少计算量的算法，算法执行的速度快，但该算法的精度還不够高，当圆的半径或长短轴长较大时，坐标点的误差大于1，理论上圆的半径a不应超过3067，很显然该精度已经不能满足目前的需求。

对于圆只需生成1/8圆周，其他部分由对称性获得；而对于椭圆就需要生成1/4椭圆弧。如果直接把文献[4]生成圆的方法应用到生成椭圆，椭圆弧对应的最大角度变为π/2，递推公式计算出的值误差也加大（文中论述原因）。针对以上问题，通过递推公式的重新构造，给出了一个精度更高的圆的生成算法，并提出采用八分之一圆周非对称方式生成椭圆，实现了生成椭圆和生成圆的精度一样高。

1 圆的递推公式的构造

1.1 圆方程的泰勒展开

假设圆心在原点，圆的方程为：

因其对称性，这里只考虑图形的生成。假设把以上区间分成n份，每份的角度为： 。当θ=kt时（k=0，1，…，n），分别计算出x和y的值。把上面参数方程用泰勒公式展开，取前几项得到：

1.2 构造表达式

对于y构造六个表达式：

以上各式有如下性质：

只要把y对应的泰勒展开式构造成以上六个表达式的形式，f5（k）的值就对应θ=kt时的y值。重复以上过程，可计算出f5（k+2），f5（k+3），f5（k+4）等。也就可计算出θ=（k+1）t，θ=（k+2）t，θ=（k+3）t时对应的y值。

1.3 系数的确定

设y=f5（k），令k=0，1，2，3，4，5得到如下各式：

解得：

采用同样的方法可对x泰勒展开式进行构造：

仿造上面方法还要构造g5（k）、g4（k）…g0（k）等六个式子。设x=g6（k），令k=0，1，2，3，4，5，6，计算出a0、a1、a2、a3、a4、a5、a6的值（相应求解省略，在下面算法中直接给出）。

2 圆的生成算法

在区间分成n份，每份的角度为。算法生成第一象限的圆弧。

数组元素a（6）、a（5）、a（4）、a（3）、a（2）、a（1）、a（0）分别存放表达式x 对应的构造表达式的值。初始时k=0，把k带入构造表达式并对数组元素进行初始化，a（6）、a（5）、a（4）、a（3）、a（2）、a（1）、a（0）的值分别为a6、a5、a4、a3、a2、a1、a0。

数组元素b（5）、b（4）、b（3）、b（2）、b（1）、b（0）分别存放表达式f5（k）、f4（k）、f3（k）、f2（k）、f1（k）、f0（k）的值。初始时k=0，代入构造表达式对数组元素进行初始化，b（5）、b（4）、b（3）、b（2）、b（1）和b（0）的值分别为b5、b4、b3、b2、b1、b0。

⑴ 预处理

⑵ for {k=0； k<=n； k++}

{

drawpixel（a（6），b（5），color）；

/*在（a（6），b（5））画点，color为点的颜色*/

drawpixel（b（5），a（6），color）； /*在对称点（b（5），a（6））处画点*/

for （i=6； i>=1； i--）

{

a（i）=a（i）+a（i-1）；

}

for（j=5； j>=1； j--）

{

b（j）=b（j）+b（j-1）；

}

}

3 生成圆的算法分析

3.1 理论分析

当kt=时，rcos（θ）泰勒展开的余项为（ξ在0和之间，（8）为八阶导数，因此误差不超过。令<1，解得r<278454.54（π=3.141593）。

rsin（θ）泰勒展开的余项为 （ξ在0和之间，（7）为七阶导数），因此误差不超过，令<1，解得r<27340.16（π=3.141593）。

由此可知，当r≤27340时，生成圆的算法计算的x，y值与真实值误差小于1。预处理后，生成每个点对需要11次加法运算。

3.2 生成圆算法直接应用于椭圆产生的误差分析

如果直接把以上算法应用于椭圆的生成，需要把r分别用椭圆的长半轴和短半轴代替，而椭圆相对于直线x=y是非对称的，因此还需要算法扩大区间生成第一象限的椭圆弧。

采用以上分析方法，当kt=π/2时，令<1，解得r<213.59。r的取值范围太小了，该算法由于误差原因不能直接应用于椭圆生成（后面给出一种方法解决此问题）。

3.3 生成圆算法的实验分析

见图1、图2和图3，把生成圆算法与直接计算进行对比，用VB进行编程实现。直接计算角度θ从0到π，变化的步长也取t，直接用参数方程x=rcos（θ），y=rsin（θ）计算。生成圆算法误差最大的地方在圆的π/4处（由于该位置迭代次数最多），把显示分辨率设置成1024×768。由于半径的值太大，把坐标偏移量设为（cx，cy）。

Form1.Scale（0，768）-（1024，0）

cx=-Sin（3.1416/4）*r

cy=-Cos（3.1416/4）*r+500

m是圆弧的取点数，当r值大时m的值也要大些，这样可保证显示足够的点做对比。实验中观察，改变m值对精度影响不大，精度主要取决于r 的大小。为显示清晰，在画点的位置绘制半径为3的圆。生成圆算法在第一和第三列位置绘制两次（实心圆），直接计算方法在第二和第三列绘制两次（空心圆）。第一和第二列圆心的偏移量不同，第三列圆心的偏移量相同。由于r的值太大，显示在屏幕上的点看上去象是在一条直线上。

r=35000时，第三列融合的很好，误差很小。r=100000时，第三列圆有一半相交。r=200000时，第三列圆相切。在图2和图3中，下面位置显示两个点距离很近，这是因为正好选在圆的π/4处，绘图时对称显示的结果。

为准确分析算法的误差情况，采用编程计算的方法，对于不同的半径r，整个圆周取2*π*r个点。对于所有的k（kt从0变化到π/4 ），计算a（6）-a*cos（kt）的值，并把绝对值最大者作为x的最大差；对于所有的k，计算b（5）-a*sin（kt）的值，并把绝对值最大者作为y轴方向的最大差。

从图4数据可看出，当r=27579时，算法计算坐标值与直接计算法之差小于1，与理论分析吻合。另外，从输出的结果可看出，计算的y比x误差大，这是由于y的泰勒展开式没有x的展开式阶数高。当r=200000时，y值的误差较大。

4 椭圆的生成算法

在图5中，圆的方程为：x2+y2=a2，椭圆的方程为：，其中，a为圆的半径，又为椭圆的长半轴，b为椭圆的短半轴。

设圆上B点坐标为（acos（α），asin（α））（α在0和π/4之间），过B点作x轴的垂线交椭圆于A点，该点的坐标为（acos（α），bsin（α））。B点相对于直线x=y的对称点为圆上的点D，D点的坐标为（asin（α），acos（α））。过D作x轴的垂线，交椭圆于C点，解得C点的坐标为（asin（α），bcos（α））。A点和C点为要绘图的点，按生成圆的算法只要同步构造出半径分别为a和b的两个圆，就可获得A点和C点的坐标值。具体算法与生成圆的算法类似。

5 椭圆算法的算法分析

每次循环生成两个点，进行22次加法运算，平均每个点需要11次加法运算。由于椭圆需要生成1/4椭圆，而圆只需要生成1/8圆，其他部分由对称获得。因此，生成椭圆的计算量相當于圆的两倍。采用以上方法构造的椭圆生成算法，其运算的精度与生成圆的算法是一样的。

6 结束语

本文在等分圆周角的前提下，以泰勒公式为基础，构造出圆和椭圆的生成算法，所给出的圆和椭圆的算法已经通过实验验证。当圆的半径、椭圆的长半轴或短半轴t≤27579时，该算法是非常精确的。当t≤100000时，相对误差也不大，算法也是可用的（对一般的应用已经是足够了）。通过对y构造更高阶的泰勒展开式，可使算法的运算精度进一步提高。

该算法生成的点分布均匀、美观，生成的点数可控，可应用于对图形输出有较高要求的场合。预处理后，计算每个点对只需要11次加法运算，避免了大量的三角函数运算，因此，运算速度快、运算精度高。本文给出的构造方法新颖，所提出的算法具有较强的理论和实用价值。

参考文献：

[1] 孙家广等.计算机图形学[M].清华大学出版社，1998.

[2] 邓四清，王平，谢进.有理四次插值样条曲线的区域控制[J].计算机工

程与设计，2008.12：3243-3246

[3] 郑豪.切割线法圆弧插补新算法的设计与实现[J].计算机工程与设

计，2008.11：2984-2986

[4] 张博.圆的高质量、快速生成算法[J].计算机应用与软件，1994.2：51-55

[5] 杨一山，顾耀林.基于样条模型插值在科学可视化上的应用[J].计算

机应用，2006.5：1045-1047

[6] 屠晓明，刘雄伟.直线Bresenham生成算法的三维推广[J].计算机辅

助设计与图形学学报，2001.9：13-16

[7] 王栋.Visual Basic程序设计[M].清华大学出版社，2002.

[8] 严伟敏，吴伟民.数据结构[M].清华大学出版社，1997.