圆和椭圆的生成算法.doc

贵州大学实验报告
学院:计算机科学与信息学院专业:软件工程班级:102
姓名
学号
实验组
实验时间
指导教师
成绩
实验项目名称
实验二:圆和椭圆的生成算法
实验目的
掌握圆和椭圆的中点算法及二次差分法,了解并掌握在光栅显示系统中圆和椭圆的生成和显示算法,并在自己熟悉的平台上实现相应的测试代码。
实验要求
掌握圆的基本特性(八对称性)
掌握椭圆的基本特性(四对称性)
掌握中点算法和二次差分法的思想
熟练的编写出测试代码
实验原理
中点算法画圆和椭圆的实验原理
画圆
因为圆具有八对称性,可以先画出第二个八分圆,利用八对称性画出其它八分圆。已知圆弧的隐函数的形式为:F(x,y)=x2+y2-R2=0。所以可知:
F(x,y)>0
F(x,y)<0
F(x,y)=0
F(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-)
如F(M)<0,则M在园内,下一点取正右方T点;
如F(M)>0,则M在园外,下一点取右下方B点;
如F(M)=0,则M在园上,下一点取T点或B点均可。
构造判别式:d=F(M)=F(xi+1,yi-)=(xi+1)2+(yi-)2-R2
(1)d<0,中点在圆内,选正右方的T点,再下一个象素的判别式为:
dnew=F(xi+2,yi-) =(xi+2)2+(yi-)2-R2=d+(2xi+3)
则d的增量为:ΔT = 2xi+3
(2) d>=0,中点在圆外,选右下方的B点,再下一个象素的判别式为:
dnew=F(xi+2,yi-) =(xi+2)2+(yi-)2-R2=d+(2xi+3)+(- yi+2)
=d+2(xi-yi)+5
则d的增量为:ΔB = 2(xi-yi)+5
d初始值为:d0=F(1,R-) =1+(R-)2-R2 =-R
因为在d的运算中包含了浮点数的运算,使复杂度提高,为了消除d中的浮点数运算,可以令d = 1-r.
画椭圆
为方便说明,可以选取中心在原点的椭圆,方程为:x2/a2+y2/b2 = 1。则隐函数的形式为:F(x,y)= b2 x2+ a2y2-(ab)2=,可只考虑第一象限的椭圆,其他的椭圆弧可以通过对称求得。
椭圆上的法向量可以将椭圆弧分为上下两个部分,在上半部分,x的增量大于y的增量,在下半部分,y的增量大于x的增量。可以得到这样的一个不等式来判别椭圆弧是否已从上半部分过度到下半部分:b2 (Xp+1) < a2 (Yp-)(椭圆弧进入下半部分时,不等式会改变方向)。
椭圆的正负划分性:
F(X,Y) = 0:(X,Y) 在椭圆上
F(X,Y) < 0:(X,Y) 在椭圆内
F(X,Y) > 0:(X,Y) 在椭圆外
(1)对于椭圆弧的上半部分:
假设Pi(xi,yi)已确定,则下一对待选像素的中点是:M(xi+1,yi-)
d = F(M) = F(xi+1,yi-)=b2(xi+1)2+a2(yi-)2-a2b2
初始点为(0,b),则M为(1,b-),d的初值为:d0=F(1,b-)=b2+a2/(-b+1/4)
(a)当d<0(取T点)时,下一点(i+1)点的坐标为(xi+1,Yi),为确定i+2点取的下一个中点M的坐标为:(xi+2,yi-).则d1=F(xi+2,yi-),故增量为:b2(2xi+3)
(b)当d>=0(取B点)时,下一点(i+1)点的坐标为(xi+1,Yi-1),为确定i+2点取的下一个中点M的坐标为:(xi+2,Yi -) .则d2=F(xi+2,yi-),故增量为:b2(2xi+3)+a2(-2yi+2).
(2)对于椭圆弧的下半部分

在每一次迭代中都要判断椭圆是否已从上半部进入了下半部,如果b2x>=a2y,则椭圆进入下半部份,此时令△y=1,且:d0=b2(x+)2+a2(y-1)2-a2b2
(a)若d<0,则M在椭圆内部,取右下方像素R,则d=F(xp+,yp-2),增量为2(b2xi+1-a2yi+1)+a2
(b)若d>=0,M在椭圆的外部,取正下方像素L,则d=F(xp+,yp-2),增量为:a2(-2yi+1+1)
下半部分的终止条件为y=0
二次差分法画圆和椭圆的实验原理
(一)画圆
二次差分法的基本思想就是在现选像素点的