张 博， 周丽韫， 李兴霞



中点生成椭圆的整数型算法

张 博， 周丽韫， 李兴霞

（佳木斯大学应用技术学院，黑龙江佳木斯154000）

在研究圆和椭圆生成算法基础上，通过构造递推表达式，给出中点生成椭圆的整数型算法，并对算法效率进行了分析。算法初始化时需进行两次乘法运算和一次移位运算，而生成各绘图点时只需要整数型加法运算，因此算法运算精度高、速度快，适合硬件的实现。采用VB编写程序对算法正确性进行了验证，该算法具有一定的理论和实用价值。

计算机应用；椭圆；整数算法；中点；Bresenham算法

对直线、圆和椭圆等生成算法的研究是近几年计算机图形领域的热点问题，关于圆和椭圆的生成算法较多，如Bresenham画圆算法，中点画圆法，椭圆双步增量生成算法，圆的高质量、快速生成算法等。可以看到椭圆的生成算法比圆的生成算法更加复杂，这些算法都采用构造方法，通过递推公式减少计算量，根据相应的判定条件，每次生成圆或椭圆上一个点的坐标，再调用画点函数在显示器上显示。算法的理论基础和构造技巧极为重要，以下对中点生成椭圆原理进行阐述。

1 椭圆的描述及区间划分

椭圆的方程为

其中为沿轴方向的长半轴长度，为沿轴方向短半轴长度。由于椭圆的对称性，研究椭圆的生成问题，只需研究第一象限的椭圆弧。

考虑第一象限椭圆左上部分，分量的变化小于分量；在右下部分，分量的变化大于分量。以弧上切线斜率为-1的点作为分界，把椭圆弧的划分为两个部分，假设该点坐标为(,)，该点的切线方程为