lesson04圆与椭圆的生成算法市公开课特等奖市赛课微课一等奖课件

lessonfour2.2

圆与椭圆扫描转换算法1第二章第二节第1页1、园特征依据圆方程：(x2+y2)=R2用扫描线方式生成圆时，会出现x方向增量取1，则y=±(R2-x2)1/2,这种方法，既增加了运算复杂性，又会产生点集疏密不均现象：当x=0时，圆周上切线斜率为零；当x靠近R时，圆周上切线斜率趋向无穷大，所以出现靠近y轴处点集较密集、平坦，但靠近x轴处间隔较大、陡直。为了克服这一现象，能够使x值改变范围从0到R/21/2，即处为止，同时对于每一组(x,y)值，利用对称求出其它7个点坐标。yx2第二章第二节第2页圆八对称性圆被定义为到给定中心位置(xc,yc)距离为r点集。圆心位于原点圆有四条对称轴x=0,y=0,x=y和x=-y。若已知圆弧上一点(x,y),能够得到其关于四条对称轴其它7个点，这种性质称为圆八对称性。所以，只要扫描转换八分之一圆弧，就能够求出整个圆弧象素集。voidCirclePoints(intx,inty,intcolor){drawpixel(x,y,color);drawpixel(y,x,color);drawpixel(-x,y,color);drawpixel(y,-x,color);drawpixel(x,-y,color);drawpixel(-y,x,color);drawpixel(-x,-y,color);drawpixel(-y,-x,color);}3第二章第二节第3页中点画圆法

假如我们结构函数

F(x,y)=x2+y2-R2，则对于圆上点有F(x,y)=0，对于圆外点有F(x,y)>0，对于圆内点F(x,y)<0。与中点画线法一样，结构判别式：d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2若

d<0，则应取P1为下一象素，而且再下一象素判别式为：d=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2=d+2xp+3若d≥0，则应取P2为下一象素，而且下一象素判别式为d=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2=d+2(xp-yp)+5我们这里讨论第一个象素是（0,R），判别式d初始值为：d0=F(1,R-0.5)=1.25-R4第二章第二节第4页中点画圆算法MidPointCircle(intr，intcolor){intx,y;floatd;x=0;y=r;d=1.25-r;circlepoints(x,y,color);while(x<=y){if(d<0)d+=2*x+3;else{d+=2*(x-y)+5;y--;}x++;circlepoints(x,y,color);}}5第二章第二节第5页Bresenham圆算法Bresenham圆算法基本思想是寻找最靠近于实际圆周上点。现仅讨论八分之一圆周，

即x从0到R/21/2范围，

所以F，G情况无须列入在内。

对于Pi-1下一点Pi只有两种可能，

即Si(xi-1+1,yi-1)和Ti(xi-1+1,yi-1-1)

误差公式：D(Si)=(xi-1+1)2+(yi-1)2-R2

D(Ti)=(xi-1+1)2+(yi-1-1)2-R2

当|D(Si)|≥|D(Ti)|，则Ti更靠近于圆周，选择Ti

当|D(Si)|＜|D(Ti)|，则Si更靠近于圆周，选择Si

令di=|D(Si)|-|D(Ti)|

则

di≥0，取Ti

di＜0，取SiPi-1ABDEFGSiTi6第二章第二节第6页圆生成算法原理情况C：因为Si在圆外，所以D(Si)＞0，因为Ti在圆内，所以D(Ti)＜0所以di=D(Si)+D(Ti)情况A,B：①从圆上看，Si更靠近于圆周，选择Si(应属于di＜0情况）②因为Si,Ti都在圆内或圆上，即D(Si)≤0，D(Ti)＜0，所以用式di=D(Si)+D(Ti)(di＜0,取Si)判别即可。情况D,E：①从圆上看，Ti更靠近于圆周，选择Ti(应属于di>0情况）②因为Si，Ti都在圆外或圆上，即D(Si)＞0，D(Ti)≥0，所以用式di=D(Si)+D(Ti)(di＞0,取Ti)判别即可。总而言之，得出，只要计算下式di=D(Si)+D(Ti)符号，便可选定Si或Ti作为下一点。Pi-1ABCDEFGSiTi7第二章第二节第7页圆生成算法改进

设x0=0，y0=R，

则S1为(1,R)，T1为(1,R-1)，

d1=(12+R2-R2)+[(12+(R-1)2-R2]=3-2R

设Pi-1为(xi-1,yi-1)，则取下一点

Si

(xi-1+1,yi-1)，Ti

(xi-1+1,yi-1-1)，

则：di=[(xi-1+1)2+yi-12-R2]+[(xi-1+1)2+(yi-1-1)2-R2]

假设di＜0，则取Si作为下一点，

即Pi(xi-1+1,yi-1)且Si+1为(xi-1+2,yi-1)，Ti+1为(xi-1+2,yi-1-1)， 则：di+1=[(xi-1+2)2+(yi-1)2-R2]+[(xi-1+2)2+(yi-1-1)2-R2]

di+1-di=4xi-1+6

di+1=di+4xi-1+68第二章第二节第8页圆生成算法改进假设di≥0，则取Ti作为下一点，

即Pi(xi-1+1,yi-1-1)则第i+1次两个可能点为

Si+1

(xi-1+2,yi-1-1)，Ti+1

(xi-1+2,yi-1-2)

di+1=[(xi-1+2)2+(yi-1-1)2-R2]+[(xi-1+2)2+(yi-1-2)2-R2]

di+1-di=4(xi-1-yi-1)+10

di+1=di+4(xi-1-yi-1)+10

即得di递归式:

d1=3-2R

(x0=0,y0=R)

di+1=di+4xi-1+6

当di＜0时，取Si(xi-1+1,yi)

di+1=di+4(xi-1-yi-1)+10 当di≥0时，取Ti(xi-1+1,yi-1)9第二章第二节第9页圆生成算法描述置第一点坐标：x=0，y=R置初始误差：d=3-2Rwhilex＜ydo

begin

输出点(x,y)以及其它7点(y,x),(-x,y),

(-y,x),(-y,-x),(-x,-y),(x,-y),(y,-x)

ifd＜0thend=d+4·x+6

elsed=d+4·(x-y)+10，y=y-1

x=x+1

endif

x=ythen输出点(x,y)以及(-x,y),(-x,-y),(x,-y)endofalgorithm10第二章第二节第10页2、椭圆特征椭圆被定义为到两个定点(焦点)距离之和等于常数点集合。椭圆上任意点p(x,y)到两个焦点距离记为d1和d2，那么，椭圆方程可表示为：d1+d2=常数设两个焦点坐标F1=(x1,y1)和F2=(x2,y2)来表示椭圆方程： [(x-x1)2+(y-y1)2]1/2+[(x-x2)2+(y-y2)2]1/2=常数改写椭圆方程，则通用椭圆方程： Ax2+By2+Cxy+Dx+Ey+F=011第二章第二节第11页标准位置椭圆：长轴和短轴与X和Y轴平行，椭圆中心可在(xc,yc)。标准位置椭圆方程： [(x-xc)/rx]2+[(y-yc)/ry]2=1 其中：rx和ry分别为长半轴和短半轴。极坐标表示： x=xc+rxcosθ,y=yc+rysinθ标准位置椭圆其在四分象限是对称，所以我们只需要计算一个四分象限椭圆曲线位置，然后依据对称性得到其余部分。12第二章第二节第12页3.5.2中点椭圆算法首先计算椭圆中心在(0,0)标准位置椭圆曲线第一分象限曲线部分位置像素(x,y)，然后将点变换到椭圆中心在(xc,yc)。依据前面DDA算法讨论，当|m|≤1时，取x方向单位步长(1或-1)，相反，取y方向单位步长(1或-1)。所以，对于第一分象限椭圆曲线分成两部分：一部分曲线斜率绝对值小于1和斜率绝对值大于1。并分别对两段曲线分别取x方向步长和y方向取步长.13第二章第二节第13页这里可选择(0,ry)或(rx,0)作为起点开始算法。以从(0,ry)开始从左到右进行。椭圆函数作为决议参数： fellipse(x,y)=ry2x2+rx2y2-rx2ry2

该函数含有以下特征： <0(x,y)位于椭圆边界内fellipse(x,y)=0(x,y)位于椭圆边界上 >0(x,y)位于椭圆边界外椭圆函数fellipse(x,y)作为中点椭圆算法决议参数。在每个取样位置，按照椭圆函数在沿椭圆轨迹两个候选像素点中点求值符号选择下一个像素

14第二章第二节第14页从(0,ry)开始，在x方向取单位步长1直到斜率变为≥-1。椭圆斜率： dy/dx=-ry2x/rx2y两段曲线采取不一样算法分界点： 2ry2x=2rx2y对于第1段曲线设用该算法计算出点(xk,yk)，下一个点(xk+1,yk+1)为A(xk+1,yk)或B(xk+1,yk-1)，即右边点或右下点。依据以下决议参数符号判断：15第二章第二节第15页 p1k=fellipse(xk+1,yk-0.5)=ry2(xk+1)2+rx2(yk-0.5)2-rx2ry2

下一点判断：当p1k<0，取A(xk+1,yk)，yk+1=yk当p1k≥0，取B(xk+1,yk-1)，yk+1=yk-1其中xk+1=xk+1递归表示式：p1k+1=p1k+2ry2(xk+1)+ry2+rx2[(yk+1-0.5)2-(yk-0.5)2]16第二章第二节第16页初始决议参数：将(x0,y0)=(0,ry)带入:p10=fellipse(1,ry-0.5)=ry2-rx2ry+rx2/4该椭圆第一分象限第一部分椭圆曲线中点算法表示：p10=ry2-rx2ry+rx2/4xk+1=xk+1yk+1=yk，p1k+1=p1k+2ry2xk+1+ry2当p1k<0yk+1=yk-1，p1k+1=p1k+2ry2xk+1+ry2-2rx2yk+1当p1k≥017第二章第二节第17页决议参数增量=2ry2xk+1+ry2当p1k<02ry2xk+1+ry2-2rx2yk+1当p1k≥0对于2ry2xk+1和2rx2yk+1本身又是一个增量表示式，2ry2xk+1增量一直为2ry2，而2rx2yk+1增量为0(当p1k<0)或-2rx2(当p1k≥0)，在起始位置(x0,y0)=(0,ry)，2ry2xk+1和2rx2yk+1初始值分别为0和2rx2ry。18第二章第二节第18页然而对于第一分象限第2段曲线，取y方向单位步长。在每一步，计算决议参数时取两个候选水平像素中点。设前一步取(xk,yk)，下一个点(xk+1,yk+1)选择：B(xk,yk-1)或A(xk+1,yk-1)，即下边点或右下点。M(xk+0/5,yk-1)为AB中点。依据以下决议参数符号判断：p2k=fellipse(xk+0.5,yk-1)=ry2(xk+0.5)2+rx2(yk-1)2-rx2ry2

19第二章第二节第19页取点判断：p2k≤0，取(xk+1,yk-1),(xk+1,yk+1)=(xk+1,yk-1),即右下点Ap2k>0，取(xk,yk-1),(xk+1,yk+1)=(xk,yk-1),即下边点B递归表示式： p2k+1=p2k-2rx2(yk-1)+rx2+ry2[(xk+1+0.5)2-(xk+0.5)2]20第二章第二节第20页当从第一分象限椭圆第1段曲线进入第2段曲线时，采取p2k作为决议参数，此时，p2k初始点为第段曲线最终计算点，设为(x0,y0)。则第二部分曲线初始决议参数:p20=fellipse(x0+0.5,y0-1)=ry2(x0+0.5)2+rx2(y0-1)2-rx2ry2

21第二章第二节第21页该椭圆第一分象限第2段椭圆曲线中点算法表示： p20=ry2(x0+0.5)2+rx2(y0-1)2-rx2ry2yk+1=yk-1xk+1=xk，p2k+1=p2k-2rx2yk+1+rx2,当p2k>0xk+1=xk+1，p2k+1=p2k-rx2yk+1+rx2+2ry2xk+1当p2k≤022第二章第二节第22页决议参数增量=-2rx2yk+1+rx2当p2k>0-2rx2yk+1+rx2+2ry2xk+1当p2k≤0对于2rx2yk+1和2ry2xk+1本身又是一个增量表示式，2rx2yk+1增量一直为-2rx2，而2ry2xk+1增量为0(当p2k>0)或2ry2(当p2k≤0)，在起始位置(x0,y0)，2rx2yk+1和2ry2xk+1初始值分别为2rx2y0和2ry2x0。23第二章第二节第23页中点椭圆算法步骤：1.输入rx,ry和椭圆中心(xc,yc)，并得到中心在原点椭圆上第一个点。2.计算第一分象限第1段椭圆曲线决议参数初值：p10=ry2-rx2ry+rx2/43.在第1段曲线每个xk处，从k=0开始，完成以下测试：假如当p1k<0，则下一个点为(xk+1,yk+1)=(xk+1,yk)，且：p1k+1=p1k+2ry2(xk+1)+ry2，不然，下一个点为(xk+1,yk+1)=(xk+1,yk-1)，且：p1k+1=p1k+2ry2(xk+1)+ry2-2rx2(yk-1)。且循环至2ry2x≥2rx2y，循环结束得到最终点(x0,y0)。24第二章第二节第24页4.使用第1段曲线计算最终得到点(x0,y0)，来计算第2段曲线初始决议参数： p20=ry2(x0+0.5)2+rx2(y0-1)2-rx2ry25.在第2段曲线每个yk处，从k=0开始，完成以下检测：假如p2k>0，则下一个点为(xk+1,yk+1)=(xk,yk-1)，且p2k+1=p2k-2rx2(yk-1)+rx2，不然下一个点为(xk+1,yk+1)=(xk+1,yk-1)，且p2k+1=p2k-2rx2(yk-1)+rx2+2ry2(xk+1)，且循环至2rx2y=0即y=0。6.确定其它三个分象限中对称点。7.将每个计算出像素位置(x,y)移到中心在(xc,yc)椭圆轨迹上，并按坐标画点：x=x+xc，y=y+yc。25第二章第二节第25页中点椭圆算法C实现#defineROUND(