圆弧算法介绍PPT课件

1、只画1/8圆，其余点通过对称关系求得。),(iiyx),(iiyx ),(iiyx ),(iiyx),(iixy),(iixy ),(iixy ),(iixy圆的特征:八对称性。只要扫描转换八分之一圆弧，就可以求出整个圆弧的象素集中点画圆法第1页/共18页考虑中心在原点，半径为R的第二个8分圆， 构造判别式（圆方程）222)5 . 0() 1()5 . 0, 1()(RyxyxFMFdppppP=(xp,yp)P1P2M根据d的正负来判断是取P1还是P2。即判断中点M在圆内还是在圆外？第2页/共18页1）若 d=0, 则应取P2（ ）为下一象素，而且下一象 素的判别式为 第 一个象素是（0,R

2、），判别式d的初始值为32) 5 . 0()2() 5 . 0, 2(222pppppxdRyxyxFd5)( 2) 5 . 1() 2() 5 . 1, 2(222ppppppyxdRyxyxFd0(1,0.5)1.25dFRRP=(xp,yp)P1P2M两种情况：1,ppxy1,1ppxy第3页/共18页 为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。 使用e=d-0.25代替d e0=1-R第4页/共18页算法描述：MidPointCircle(int r int color) int x,y; float d; x=0

3、; y=r; d=1.25-r; circlepoints (x,y,color); /显示圆弧上的八个对称点 while(x=y) if(d0) d+=2*x+3; else d+=2*(x-y)+5; y-; x+; circlepoints (x,y,color); 第5页/共18页中点画圆举例：第6页/共18页象限判别通过分析，发现在进行绘制圆弧曲线时，需要考虑轨迹点所在象限的情况，因此需要进行象限的判别。对于在坐标轴上的点，需要根据绘制圆的方向来决定。ABCD第7页/共18页3.4 Bresenham算法仍然考虑圆心在原点的一个第一象限的圆弧 。对于圆弧上的点p（x, y)，其下一个

4、可选择的点如图。H(x+1，y） D(x+1,y-1)(0, ) (,)22RRRpHL0id 222( )()D PxyR222222()()()()iiihihililidD HD LxyRxyR0id 当 ，应取H点，H离圆弧近当 ，应取L点，L离圆弧近令：第8页/共18页起始点A 其中 00(,)xy000,xyR101xx第2点有111()()32dD HD LR2222221122211()()()(1)22221iiiiiiiiiidD HD LxyRxyRxyyR2222221222(1)(1)(1)242223iiiiiiiiidxyRxyRxxyyR0id 0id 当 ，应

5、取H点，此时当 ，应取L点，此时1iiyy11iiyy114246iiiiiddxdx11114464() 10iiiiiiiddxydxy第9页/共18页算法描述： procedure arc(radius :integer) var x,y,d:interger;begin x:=0;y:=radius;d:=3-2*radius;while xy dobeginplot(x,y);if dyc dobeginplot(x,y);if f0 then begin f:=f-2*(y-yc)+1; y:=y-1;end;elsebeginf:=f+2*(x-xc)+1;x:=x+1;end;

6、end; if y=yc then plot(x,y);end;第13页/共18页举例：半径为R ,圆心为（0，0），A起点（0，6） d1=3-2*6=-9xyd00 6F0=0116F1=1215F2=-10325F3=-7435F4=-2545F5=5644F6=-4754F7=5853F8=-2963F9=910 62F10=411 6 1F11=112 600 1 2 3 4 5 66543210第14页/共18页3.5 圆的多边形迫近法考虑圆心在内接正多边形的一个顶点：(,)ccxy半径为R cp的幅角为( ,)iiip x yi则有cosicixxR1cos()()cos()sinicicicicxxRxxxyy11cossinsincosiicciiccxxxxyyyy1iPiPncsiniciyyR1sin()()sin()cosicicic