椭圆生成算法的研究样本.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。

椭圆生成算法的研究
本文由天空乐园校园二手网整理分享
摘要
作为计算机图形学中基本几何元素之一的椭圆, 其生成算法在几乎所有计算机图形学相关领域都要用到, 特别在计算机辅助设计中经常涉及。因此, 研究椭圆生成对计算机图形系统十分重要。当前, 已有大量的文献讨论了如何高效生
成误差小的椭圆。文献一中方法之一在扫描转换的同时复制椭圆宽度数个像素, 这种方法比较简单, 但造成椭圆切线斜率接近-1处显得很细。文献一中方法之二扫描转换两个同心的椭圆, 内椭圆的两个半径分别为a-w/2, b-w/2 ; 外椭圆的两个半径为 a +w/2 ,b + w/2; 然后填充它们间的间隙, 在微分几何中有一个结论: 沿着垂直椭圆弧的方向, 将此椭圆上的点移动w/2的距离所形成的曲线与原椭圆同心的椭圆, 而是由一个8次方程所描述的曲线, 因此这种算法也有较大误差, 特别是 a 的值接近于w时。然而, 对这样8次函数进行扫描转换, 计算量非常大。圆弧绘制生成宽椭圆算法与椭圆中点扫描转换算法复杂度相当, 且生成的椭圆效果较好, 视觉感受不到明显缺陷。
本文主要对计算机图形学、 椭圆的生成算法的具体实现及其应用进行综述, 并简要讨论。
关键词: 计算机图形学 椭圆生成算法 并行生成算法 宽椭圆

1 一种宽椭圆生成算法
计算机辅助设计领域常涉及宽椭圆生成, 宽椭圆生成算法的优劣直接影响
设计效果。为了生成一个圆心在原点的标准宽椭圆, 每次用单像素宽的椭圆中点扫描转换算法, 得到一个单像素宽椭圆上的一个点, 填充一个以该点为中心, 椭圆宽为直径的圆弧, 扫描转换结束后, 生成一个无明显视觉缺陷的第一象限12宽椭圆。
作为计算机图形学中基本几何元素之一的椭圆, 其生成算法在几乎所有计算机图形学相关领域都要用到, 特别在计算机辅助设计中经常涉及。因此, 研究椭圆生成对计算机图形系统十分重要。当前, 已有大量的文献讨论了如何高效生
成误差小的椭圆。椭圆的扫描转换法[1]就是其中之一, 该算法基于Da Silva 的算法[2], 运用二阶偏差分Pitteway[3], Van Aken[4]、 KAppel[5]等所用的一些技术, 该算法生成的椭圆都是单像素宽的, 而现实中更多时候要生成宽椭圆, 宽椭圆一般定义为沿着垂直两半径为a、 b 的椭圆弧的两方向, 将此椭圆上的点移动2w 的距离所形成的两条曲线中间部分, 为了生成宽椭圆, 文献一中方法之一在扫描转换的同时复制椭圆宽度数个像素, 这种方法比较简单, 但造成椭圆切线斜率接近-1 处显得很细。文献一中方法之二扫描转换两个同心的椭圆, 内椭圆的两个半径分别为2a − w , 2b − w ; 外椭圆的两个半径为2a + w , 2b + w; 然后填充它们间的间隙, 在微分何中有一个结论: 沿着垂直椭圆弧的方向, 将此椭圆上的点移动2w 的距离所形成的曲线与原椭圆同心的椭圆, 而是由一个8 次方程所描述的曲线[6], 因此这种算法也有较大误差, 特别是a 的值接近于w 时。然而, 对这样8 次函数进行扫描转换, 计算量非常大。圆弧绘制生成宽椭圆算法与椭圆中点扫描转换算法复杂度相当, 且生成的椭圆效果较好, 视觉感受不到明显缺陷。
1.1 算法基本思想
主要考虑中心在原点的标准椭圆, 宽度为w, (a>b>w, a, b, w∈z); 对于中心不在坐标原点的椭圆, 可先作相应的平移变换, 变换为中心在原点的椭圆, 把所得的像素坐标加上一个位移即可得到所求的像素坐标。另外, 只讨论椭圆在第一象限内的生成算法, 其它象限内的点利用椭圆的四分对称性即可得到。在第一象限内的四分之一椭圆分为两个区域来处理．两个区域之间以斜率为-1 的点(即法向量两个分量相等的点)作为分界。对于区域I, 以点(0, b)为始点, x 方向单位长作为步长。向右生成曲线。假设当前扫描计算得到的点为批p0( x, y) , 扫描转换的下一个点p1 可能为=( x+1, y) 或=( x+1, y-1) , 判断s1、 s2 的中间点在椭圆的内还是外, 选择下一个扫描点。
如果中点m 在内(m 点代入椭圆方程值小于1), 则下一个点p1 为( x+1, y) , 否则为( x+1, y-1) ; 当斜率变为小于-l 时, 转向区域Ⅱ, 此时以(a, 0)为始点。y 方向作为单位步长, 向左生成曲线。假设当前扫描计算得到的点为p0′(x, y), 扫描转换的下一个点可能为s1′(x, y+1)或s2′(x-1, y+1), 判断、 的中间点m( x − , y+ ) 在椭圆的内还是外, 选择下一个扫描点。如果中点在内, 则下一个点p1′为( x, y+1) 否则为( x-1, y+1) 。以上简单介绍了椭圆中点扫描生成算法, 接下来基于中点扫描算法来生成宽椭圆。宽椭圆生成算法思路: 先以中点圆算法[1]生一个圆心在原点直径为w 的圆, 填充该圆, 然后以椭圆扫描转换算法[1]求得椭圆上的点, 将填充的圆平移到扫描转换得到的各点处( 如图1) 。

图1 生成椭圆第一象限
1.2 算法实现过程
如图2, 椭圆扫描转化得到的相邻点P0(x0, y0)、 P1(x1, y1), 它们对应的圆形填充区为U1、 U0, 填充圆于造成中间大量的像素 重复绘制, 算法复杂性较高, 实际上只须绘制-, 即图中黑色的部分, 这些点全在圆边上, 为”半圆弧”, 这个半圆弧相对扫描点P1 的位置以及它的形状取决于扫描推进的方向, 也就是P1 与P0的位置关系。图1 所示, 根据椭圆扫描转换分4种来考虑它们的位置( θ为圆心角) :
( 1) 扫描第一区间(切线斜率r>-1), p1 取, =+1, y1=y0 时, 如图2 所示。- 为图中黑色右半圆弧, 绘制右半圆弧的算法:
1) 从最左的一个点开始, 取1/8 圆上的一个点q;
2) 由对称性, 计算q 对应在1/2 圆的3 个对称点q0, q1, q2;
3) 将平移() , 为p1 的坐标;
4) 判断是不是最后一个点, 不是的话, 取下一个点; 回到2) ; 是则圆弧绘完。

图2 中点扫描向右推进时相邻两次填充区的关系

( 2) 扫描第一区间( 切线斜率r>-1) , p1取s2, =+1
, , 如图3 所示。

图3 中点扫描斜下推进时相邻两次填充区的关系
为图中黑色半圆弧, 图中类似p 点的凹点要绘制, 绘制右下半圆弧的算法:
1) 从最左的一个点开始, 取1/8 圆 上的一个点q;
2) 由对称性, 计算q 对应在1/2 圆的3 个对称点;
3) 将平移() , 为p1 的坐标;
4) 判断q 边有没有凹点, 有则取凹点执行2)、 3) ;
5) 判断是不是最后一个点, 不是的话, 取q 下一个点; 回到2) ; 是则圆弧绘完。用同样的方法能够填充第二区间的椭圆。
( 3) 扫描第二区间( 切线斜率r <=-1) ,
当p1 取s1, x1=x0, y1=y0-1 时, 如图4 所示。

图4 中点扫描向下推进时相邻两次填充区的关系
为图中黑色半圆弧(−π≤θ ≤ 0), 绘制下半圆弧的算法:
1) 从最左的一个点开始, 取1/8 圆上的一个点q;
2) 由对称性, 计算q 对应在1/2 圆(−π≤θ ≤ 0)的3 个对称点;
3) 将平移() , 为p1 的坐标;
4) 判断是不是最后一个点, 不是的话, 取下一个点; 回到2); 是则圆弧绘完。
( 4) 扫描第二区间( 切线斜率r<=-1) , 当p1 取s2, x1=x0+1, y1=y0-1, 此时p0 与p1 位置与(2)同, 见图2, 必须绘制右下半圆弧, 其算法见绘制右下半圆弧的算法。
1.3 宽椭圆具体的生成过程
( 1) 生成直径为椭圆宽度w 的1/8 圆, 以数组y[n]记下1/8 圆的纵坐标值;
( 2) 填充圆心在( 0, b) 处直径为w 的圆, p0 为( 0, b) ;
( 3) 判断p0 是否为分界点, 是转(7), 不是
转入(4);
( 4) 由椭圆的扫描转换法求得p1;
( 5) 判断p1 与p0 是对角关系还是水平相邻, 如果是水平相邻, 绘制右半圆, 如果斜对角, 绘制右下半圆;
( 6) p0=p1, 转(3);
( 7) 填充圆心在( 0, b) 处直径为w 的圆, p0 为( a, 0) ;
( 8) 判断p0 是否为分界点, 不是分界点转入(9), 是则结束;
( 9) 由椭圆的扫描转换法求得p1;
( 10) 判断p1 与p0 是对角关系还是垂直相邻, 如果是垂直相邻, 绘制上半圆, 如果斜对角, 绘制左上半圆;
( 11) P0= P1, 转(8)。
2 一个椭圆的并行生成算法
随着计算机图形学的发展, 对基本几何元素生成算法的研究也不断深入, 人们从不同角度对椭圆的生成提出了许多算法. 文献[ 1] 从已知点入手, 根据递推公式逐点选择最靠近椭圆的像素点, 文献[ 2] 和[ 3] 也从已知点入手根据递推公式每次确定两个最靠近椭圆的像素点来生成椭圆, 文献[ 4] 从椭圆与其外接和内切圆之间的相互位置关系入手, 经过这两个圆来生成椭圆, 文献[ 5] 从椭圆的参数方程入手, 利用正弦和余弦的泰勒展开式以等分角度为增量生成椭圆.本文从另一角度入手, 利用多处理器( 或线程) 并行生成椭圆, 即以Bresenham 椭圆生成算法为基础引入并行特征, 并利用C # 的多线程机制模拟实现。也就是先把第一象限的椭圆分割成无关联的两段, 然后针对每一段利用一个处理器( 或线程) 并结合椭圆的四分对称性进行椭圆的Bresenham 扫描转换, 从而提高椭圆的生成效率.
2.1 椭圆弧的划分
设椭圆的方程为, 即F( x , y )=a, b 为x 轴方向和y 轴方向的两个半轴, 且a, b 均为正整数, 任意位置的椭圆可经过图形的复合变换得到。由于椭圆的四分对称性, 只需考虑第一象限1/4 椭圆的生成, 其它象限的像素点可由图形的对称变换得到。对隐函数F( x , y ) 求导可得= , 由于dy/dx 0 可知椭圆在第一象限内单调递减, 在区间[ 0, a ] 内切线的斜率从0 递减到- .为了使生成的椭圆具有封闭性, 以弧上斜率为- 1 的点作为分界, 把椭圆弧分成上下两部分. 上半部分满足| | < 1 即 , x 的变化量大于y 的变化量, 由x 从点( 0, b) 开始递增步长来确定y 的值, 下半部分满足| | 1 即, y 的变化量大于x 的变化量, 由y 从点( a, 0) 开始递增步长来确定x 的值.由于这两部分是相互独立的, 可用两个处理器( 或线程) 并行处理, 而不用考虑同步问题, 从而能最大化的提高并行效率.
2.2 两部分的算法描述
对划分后的两个独立弧段, 能够借用Bresenham 算法思想从一个已知点开始根据构造的判别递推公式逐
点生成, 这个过程可利用两个处理器( 或线程) 并行执行.对于上半部分, 假设已知点为 则下一点 在其右方 点或右下方点中选择离椭圆弧最近的点, 而| F | 为右方点到椭圆弧的距离, | F | 为右下方点到椭圆弧的距离, 经过做差:
= | F | - | F | =| F | + | F |
可判断出所要选择的点, 即: < 0 选择右方的点, 0 选择右下方的点. 根据所得到的 利用上述思想推下一点即可得到di+ 1 与di 的递推关系式: =+4 < 0且=+4, 0
该算法在VS . NET 平台下编译经过, 根据笔者的思路该算法能够利用任何并行编程环境如PVM 或MPI 在并行机或集群网络上实现.
3 一个椭圆生成算法
计算机图形学中, 关于椭圆的生成算法较多, 如中点椭圆生成算法[1], 高效的整数型椭圆生成算法[2], 基于Bresenham 算法的画椭圆算法[3], 椭圆的高质量、 快速生成算法[4]等, 这些算法的主体思想均是以递推方式每次生成椭圆上一个点的坐标, 再调用画点函数在显示器上点亮一个像素。文献[3]中介绍的是一种高效的算法, 该算法引用了虚拟空间中椭圆的内切或外接圆, 使虚拟空间中所画的圆较小, 减少了参与运算的数据位数,但该算法生成的椭圆并不精确, 当椭圆的长短轴之比较大时,靠近长轴顶端部分的图像退化严重, 呈锯齿状, 这种算法可称为”内切或外接圆算法”, 它只适合于长短轴之比小于3 的情况。文献[4]给出的算法是”等分角度的绘椭圆算法”, 它要用到浮点运算, 且无法确定不同椭圆应该多少等分方可使生成的椭圆达到最佳。
作为计算机图形学中基本几何元素之一的椭圆, 其生成算法在几乎所有计算机图形学相关领域都要用到, 特别在计算机辅助设计中经常涉及。因此, 研究椭圆生成对计算机图形系统十分重要。当前, 已有大量的文献讨论了如何高效生
成误差小的椭圆。椭圆的扫描转换法就是其中之一, 该算法基于 Dasilva的算法, 运用二阶偏差分 Pitteway, Van Aken、 KAppel等所用的一些技术, 该算法生成的椭圆都是单像素宽的, 而现实中更多时候要生成宽椭圆, 宽椭圆一般定义为沿着垂直两半径为 a、 b 的椭圆弧的两方向, 将此椭圆上的点移动w/2的距离所形成的两条曲线中间部分, 为了生成宽椭圆, 文献一中方法之一在扫描转换的同时复制椭圆宽度数个像素, 这种方法比较简单, 但造成椭圆切线斜率接近-1处显得很细。文献一中方法之二扫描转换两个同心的椭圆, 内椭圆的两个半径分别为a-w/2, b-w/2 ; 外椭圆的两个半径为 a +w/2 ,b + w/2; 然后填充它们间的间隙, 在微分几何中有一个结论: 沿着垂直椭圆弧的方向, 将此椭圆上的点移动w/2的距离所形成的曲线与原椭圆同心的椭圆, 而是由一个8次方程所描述的曲线, 因此这种算法也有较大误差, 特别是 a 的值接近于w时。然而, 对这样8次函数进行扫描转换, 计算量非常大。圆弧绘制生成宽椭圆算法与椭圆中点扫描转换算法复杂度相当, 且生成的椭圆效果较好, 视觉感受不到明显缺陷。
3.1 算法思想及算法描述
设椭圆方程为F( x, y) ==0, 其中a、 b 为x 轴方向和y 轴方向的两个半轴, 且a、 b 均为正整数, 任意位置的椭圆可经过它的平移和旋转得到。由椭圆的对称性, 可只考虑一个象限内的1 /4 椭圆弧的生成。如图1 所示, 是一个a=19, b=10 的椭圆。在第一象限内, 椭圆弧是由一组水平直线段、 斜率为- 1 的对角直线段和垂直直线段首尾相连而成的。在处理这段椭圆弧时, 依然依文献[2]中所述, 把它分为两个部分: 上半部分( 弧1) 和下半部分( 弧2) , 以弧上斜率为- 1 的点( 即法向量的两个分量相等的点) 作为分界, 如图2 所示。

图2 一象限弧分两个部分

图1 a=19, b=10的椭圆

由微分知识, 椭圆上一点P( x, y) 处切线的斜率方程为: =0, 则有y′= 。在第一象限中, y′∈[- ∞, 0]。由图可知, 在上半部分( 弧1) , y′∈[- 1, 0]; 下半部分( 弧2) , y′∈[- ∞, - 1]。即上半部分满足y′>- 1, 即, 而在下半部分则有。
2.1 上半部分( 弧1)
在上半部分, 设 是已确定的一个像素, 则下一个像素 (,) 要么是 (,) , 要么是 (,), 如图3 所示。由于x 坐标从0 开始, 每次递增1, y 坐标从b 开始, 每次不变或递减1, 因此有: ===- 1, =- 1, =- 1- 1。
图3 和的位置关系

由( 1) 、 ( 2) 、 ( 3) 能够用画点函数依次画出弧1 上的各个像素, 这实际上就是Bresenham 画椭圆的改进算法的思想, 这样做并没有充分利用到弧1 上的水平直线段和对角直线段。弧的切线反映了弧的走向, 当弧的切线斜率在- 1 /2≤y′≤0 时, x 增加2 时, y 最多减少1。如图4 所示, 这一段椭圆弧是
由水平位移至少为2 的线段组成( L1, L2, L3) 。当弧的切线斜率在- 1≤y′≤- 1 /2 时, 是长度不超过2 个像素的一组水平直线段, 当然可看成一组斜率为- 1 的对角线( L4, L5) 。在图4 中, 当x 从0 加到6 时, y 值始终为b, 这条直线段( L1) 可经过( 1) 的<0 得到; 当x 再加1, 则有( 2) 的≥0, 此时, y 应减1, 进入第二条直线段, 当x 再加1 时, 又进入了(1)的<0 状态, 此后x 继续加1 至x 加到10, 生成L2; 当x 再加1, 又有≥0, 此时, y 应减1, 如此循环直到y′<- 1 /2。在这个过程中, 能够得到长度大于等于2 个像素的一组水平直线段, 这组水平直线段可用画线函数line(, y, x, y) 画出, 其中 和y表示≥0 时所记录的水平坐标和垂直坐标, x 表示退出<0时的水平坐标。

图4 弧段由线段组成

3.2 算法的整数化
以上程序中使用了关于x、 y 的乘法运算和一些常量a、 b的乘法运算, 由于x、 y 的变化都是增量变化的, 因此可使用增量运算来避免乘法, 常量的乘法运算也能够使用中间变量使其在循环之前完成。若设incx=b*b*x, incy=a*a*y。则: 在循环开始时, x=0, y=b。因此有: incx=0, incy=a*a*b。在循环体内, 当x 增1 时, incx 增b*b, y 减1 时, incy 减a*a。此时, while( 2*b*b*x<=a*a*y) 可改写成while( ( incx<<1) <=incy) ; while( b*b*x<=a*a*y) 可改写成while( incx<=incy) 。对弧2 结束条件的处理形式: 在弧1 结束时, 使用一对变量( stopx, stopy) 记住该点, 作为弧2 的循环结束条件。这是因为弧2 的结束点就是弧1 的结束点。若设BF=b*b, AF=a*a, BF4=b*b*4, AF4=a*a*4。在循环体内部, 则有: 当d<0 时, d+=(BF4*x+2*BF) ; 当d≥0 时, d+=(BF4*x+2*BF) - AF4*y。d 的增量部分显然是x、 y 的线性函数,由于x、 y 均为增量变量, 因此, d 的增量部分完全可用增量表示式来确定。
3.3 算法的效率分析
该算法绘制一条直线段( 水平、 垂直、 对角) 的计算量与画点算法的计算量是相同的, 可是本算法的输出量只有画点算法的1 /N( 其中N 为一条线段的像素数) 。由于N≥2, 因此, 该算法的效率显然高于画点算法, 当两个半轴之比较大时, 椭圆主要由较长的水平直线段或垂直直线段组成, 即N 的平均值远远大于2, 因此绘画效率将会提高很大。弧2 的结束条件stopy的引入, 进一步减少了对角线段绘制的计算量。在天逸Y- 510笔记本电脑、 Windows- xp 操作系统下, 绘制5 000 个椭圆的进行实测统计情况如表1 所示, 能够看出, 在两个半轴之比( a /b或b /a) 小于3 时, 本算法的效率是中点算法[3]和Bresenham 改进算法[2]的2 倍以上, 是内切或外接圆算法[3]的1.5 倍左右; 本算法的效率随两个半轴之比的增大明显提高, 当两个半轴之比大于6 时, 本算法的效率是中点算法[1]和Bresenham 改进算法[2]的4 倍以上。总之该算法具有非常高的效率, 特别是当椭圆的两个半轴相差较大时, 绘图效率更加明显。
4 一种高效的整数型椭圆生成算法
对已有的椭圆生成算法进行深入的研究, 仔细分析了各种算法的优缺点; 并在此基础上, 提出一种新颖而实用的椭圆生成算法. 与同类算法相比, 该算法具有设计思想简单, 全部采用整数型运算, 而且在转折点问题的处理上有较大突破.
4.1　引　　言
计算机图形学中的基本元素包括直线, 圆, 椭圆等. 当前广大学者的注意力大都集中在直线和圆弧的生成算法上, 也因此应运而生一些著名算法, 如Br esenham 直线生成算法,DDA 直线生成算法, 正负法[ 1] 、 Bresenham 画圆算法[2] 、 多边形逼近法画圆[ 3] ; 而对于椭圆生成算法的研究却不十分活跃. 但生成椭圆的操作, 同样是一项经常性的操作, 因此对于椭圆生成算法的任何一个微小进步, 也同样是非常有意义的. 当前, 比较有影响的椭圆生成算法当属文献[ 4-10] , 总结上述算法发现存在以下缺点:
(1) 多处使用非常耗时的浮点运算和取整运算;
(2) 使用三角函数运算;
(3) 经过缩小整数范围来弥补执行速度的缓慢;
(4) 在算法推导过程中, 引入过多新概念, 使算法思想过于复杂;
(5) 以牺牲所使用空间范围的增加为代价, 来换取运行
的高效率.
4.2　算法的提出与算法思想
设椭圆的标准方程为, 其中a, b 分别为椭圆的长、 短轴, 圆心 为坐标原点. 为了不失一般性, 如果圆心不在坐标原点, 可作相应的平移变换, 生成圆心在坐标原点的椭圆. 另外, 考虑椭圆的四分对称性, 我们只讨论第一象限内的椭圆的生成即可.
椭圆与圆不同, 在第一象限内一般要分为2 个区域来处理, 2 个区域之间以斜率为- 1 的点( 即法向量的2 个分量相等的点) 作为分界. 从点( 0, b) 开始, 在第一象限内沿椭圆路径顺时针步进, 在区域1 内斜率大于- 1, 以X 方向作为单位步长来衡量Y 方向的走向; 当斜率变为小于- 1 时, 则转向区域2, 即以Y 方向作为单位步长来衡量X 方向的走向.
2. 1　区域1 中决策参数的判定
从图1 中A 点开始, 向右下方逐点寻找显示要用的点.如图2 所示, 假设为上已选定的点, 根据 的走向, 下一点应从或中选择. 显然应选图1中离 最近的点. 设和

图1 中点在原点的标准椭圆
两点的坐标分别为 和, 又设有一对足即此椭圆弧( 长轴为, 短轴为 ) 满足和点到该弧的距离相等. 则我们能够把这个椭圆弧作为一条分界线: 当在的上方时应选 点来显示; 当在 的下方时应选点来显示。

图2 当在上方时, 应当取, 否则取
本算法从区域转折点的定义入手, 即在转折点处的斜率值为- 1, 又根据椭圆方程, 可得dy / dx =.由此可得, 在区域1和区域2的交界处= 1, 即;则移出区域1的条件为:
(5)
为了进一步节省运算时间, 提高算法效率, 对于式( 5) 的判断, 我们采用增量式判断. 具体做法是: 在X 方向每走一步, 增加( 或减少) ; 在Y 方向每走一步, 增加( 或减少) , 具体实现不再详述.
另外, 在区域2 内, 我们不再把式(5) 的判断作为该区域的终止条件, 而是在进入区域2 之前, 把区域1 的最后一点的坐标记录下来, 记为和; 然后, 在区域2 内, 从( a, 0) 点开始, 逆时针显示; 以Y 方向为单位步长, 判断X 方向的变化, 从而显示区域2 内的椭圆弧. 即该区域内生成最后一点的终止条件为X = 且Y = . 在此也省略了一些运算.
4.3、 算法的复杂度分析与比较
(1) 计算量比较, 表1 所示为采用本算法与常见的中点法及正负法得到椭圆弧上的任一点的计算量比较.
表1 计算量的比较

算法 除法 乘法 加减法
正负法 0 4*n 2*n
中点法 0 2*n浮点乘 4*n
本算法 0 0 n

能够看出, 中点法使用了比较复杂又影响精度的运算,而采用本算法对于分界点问题进行处理时, 可完全不必进行如此复杂的计算.
(2) 运算时间比较本算法已在PC 机上加以验证, 取被试时间为1s, 将用本算法与用中点法生成的椭圆数进行比较, 椭圆的长、 短轴分别从( 130, 160) 增加至( n+130, n+160) , 其中n 为运用该算法得到的椭圆数. 测试结果为本算法的n= 248, 中点法的n= 180.
由此可得, 若忽视长、 短轴的变化所带来的时间变化, 本算法在1 s 内可生成248 个椭圆, 而中点法在1 s 内生成180个椭圆.
综上所述, 该算法与同类算法相比, 具有生成速度快且不具有突变和失真现象等优点.

参考文献:
[1] 孙家广.计算机图形学[M].北京: 清华大学出版社, .
[2] 唐棣, 孙岩.一种高效的整数型椭圆生成算法[J].计算机辅助设计与
图形学学报, , 14( 1) .
[3] 鲁成东.一种基于Bresenham 算法的椭圆算法[J].河南师范大学学
报, 1996, 24( 4) .
[4] 曹建忠, 孟庆波.椭圆的高质量、 快速生成算法[J].华北工学院学报,
1996, 17( 1) .
[5] HOLLAND J H.Adaptation in natural and artificial system: an introduction analysis with applications to biology, control, and artificial intelligence[M].Michigan: The University of Michigan Press, 1975.
[6] 刘洪杰, 王秀峰, 王治宝.多峰搜索的自适应遗传算法[J].控制理论
与应用, , 21( 2) : 302- 305.
[7] KENNEDY J, EBERHART R C.Particle swarm optimization[C] / /
proceeding of IEEE Int’l Conf on Neural Networks.Piscataway, NJ:
IEEE Service Center, 1995, IV: 1942- 1948.
[8] Tang Zesheng, et al. Computer Graphics' Base [ M ] . Beijing
: Tsinghua University Press, 1998. 63～72( in Chinese)
( 唐泽圣, 等. 计算机图形学基础[ M] . 北京: 清华大学出版社,
1998. 63～72)
[9] 赵京东. 一个椭圆生成算法[J]. 计算机工程与应用, , 35(6): 27-29.
[10] 陈震岳, 朱桂林. 基于几何关系的椭圆图形生成算法[J]. 计算机工程与科学, , 26(8): 56-59.
[11] 阎 双, 唐 棣. 椭圆的双步生成算法[ J] . 计算机工程与应用, , (33) : 65- 67.
[12] 刘 凯, 侯伯亨, 等. 椭圆的双步增量生成算法及其硬件实现[ J] . 计算机辅助设计与图形学学报, , 15( 4) : 393- 396.
[13]椭圆曲线 著 颜松远 大连理工大学出版社
[14]椭圆曲线算术中的高等论题 著 西尔弗曼(Joseph H.Silverman) 世界图书出版公司
[15]椭圆函数(第2版) 著 S.Lang 世界图书出版公司
计算机图形学课程设计由: 天空乐园网站郑州大学生兼职收集
由开封市同力基础工程有限公司整理出版!