贵州大学--实验二：圆和椭圆的生成算法

《贵州大学--实验二：圆和椭圆的生成算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、贵州大学实验报告学院：计算机科学与信息学院专业：软件工程班级：102姓名学号实验组实验时间指导教师成绩实验项目名称实验二：圆和椭圆的生成算法实验目的掌握圆和椭圆的中点算法及二次差分法，了解并掌握在光栅显示系统中圆和椭圆的生成和显示算法,并在自己熟悉的平台上实现相应的测试代码。实验要求1，掌握圆的基本特性（八对称性）2，掌握椭圆的基本特性（四对称性）3，掌握中点算法和二次差分法的思想4，熟练的编写出测试代码实验原理一、中点算法画圆和椭圆的实验原理（一）画圆因为圆具有八对称性，可以先画出第二个八分圆，利用八对称性画出其它八分圆。已知圆弧的隐函数的形式为：F(x,y)=x2+y2-R

2、2=0。所以可知：F(x,y)>0F(x,y)<0F(x,y)=0F(x,y)>0，(x,y)在园外；F(x,y)<0，(x,y)在园内，F(x,y)=0，(x,y)在园上。假设(xi,yi)为已确定的象素坐标，则下一个象素只能是正右方的T点或右下方的B点。设M是T和B的中点，则M的坐标为(xi+1,yi-0.5)如F(M)<0，则M在园内，下一点取正右方T点；如F(M)>0，则M在园外，下一点取右下方B点；如F(M)=0，则M在园上，下一点取T点或B点均可。构造判别式：d=F(M)=F(xi+1,yi-0.5)=(xi+1)2+(yi-0.5)2-R2（1）d<0，中点在圆内

3、,选正右方的T点,再下一个象素的判别式为：dnew=F(xi+2,yi-0.5)=(xi+2)2+(yi-0.5)2-R2=d+(2xi+3)则d的增量为：ΔT=2xi+3(2)d>=0,中点在圆外,选右下方的B点,再下一个象素的判别式为：dnew=F(xi+2,yi-1.5)=(xi+2)2+(yi-1.5)2-R2=d+(2xi+3)+(-yi+2)=d+2(xi-yi)+5则d的增量为：ΔB=2（xi-yi）+5d初始值为：d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-R因为在d的运算中包含了浮点数的运算，使复杂度提高，为了消除d中的浮点数运算，可以令

4、d=1-r.（一）画椭圆为方便说明，可以选取中心在原点的椭圆，方程为：x2/a2+y2/b2=1。则隐函数的形式为：F（x,y）=b2x2+a2y2-(ab)2=0.因为椭圆具有四对称性，可只考虑第一象限的椭圆，其他的椭圆弧可以通过对称求得。椭圆上的法向量可以将椭圆弧分为上下两个部分，在上半部分，x的增量大于y的增量，在下半部分，y的增量大于x的增量。可以得到这样的一个不等式来判别椭圆弧是否已从上半部分过度到下半部分：b2(Xp+1)

5、(X,Y)在椭圆内F(X,Y)>0：(X,Y)在椭圆外(1)对于椭圆弧的上半部分：假设Pi(xi，yi)已确定，则下一对待选像素的中点是：M(xi+1,yi-0.5)d=F(M)=F(xi+1,yi-0.5)=b2(xi+1)2+a2(yi-0.5)2-a2b2初始点为（0，b）,则M为（1，b-0.5）,d的初值为：d0=F(1,b-0.5)=b2+a2/(-b+1/4)(a)当d<0(取T点)时，下一点(i+1)点的坐标为(xi+1，Yi)，为确定i+2点取的下一个中点M的坐标为：(xi+2，yi-0.5).则d1=F(xi+2,yi-0.5)，故增量为：b2(2xi+3)

6、(b)当d>=0(取B点)时，下一点(i+1)点的坐标为(xi+1，Yi-1)，为确定i+2点取的下一个中点M的坐标为：(xi+2，Yi-1.5).则d2=F(xi+2,yi-1.5),故增量为：b2(2xi+3)+a2(-2yi+2).(2)对于椭圆弧的下半部分在每一次迭代中都要判断椭圆是否已从上半部进入了下半部，如果b2x>=a2y，则椭圆进入下半部份，此时令△y=1，且：d0=b2(x+0.5)2+a2(y-1)2-a2b2(a)若d<0,则M在椭圆内部，取右下方像素R，则d=F(xp+1.5,yp-2),增量为2(b2xi+1-a2yi+1)+a2(b)若d>=0,M在

7、椭圆的外部，取正下方像素L，则d=F(xp+0.5,yp-2)，增量为：a2(-2yi+1+1)下半部分的终止条件为y=0一、二次差分法画圆和椭圆的实验原理(一)画圆二次差分法的基本思想就是在现选像素点的基础上进行二次选择，计算增量，从而达到消除中点算法中的乘法运算，降低增量阶数的目的。假设现有点为P(xp,yp)，在中心法画圆中已求得正右方的增量为ΔT=2xi+3，右下方的增量为ΔB=2（xi-yi）+5若现已选择P(xp,yp)点正右方的T点，下一个点可以选T点正右方的点和T点右下方的点