2010年5月12日星期三

bresenham画圆算法

bresenham画圆算法

中点画圆算法在一个方向上取单位间隔,在另一个方向的取值由两种可能取值的中点离圆的远近而定。实际处理中,用决策变量的符号来确定象素点的选择,因此算法效率较高。

  Bresenham画圆和椭圆程序 - 随风倒上 - 赵志刚--Greddy的个人主页一、中点画圆算法描述

  设要显示圆的圆心在原点(0,0),半径为R,起点在(0,R)处,终点在(Bresenham画圆和椭圆程序 - 随风倒上 - 赵志刚--Greddy的个人主页Bresenham画圆和椭圆程序 - 随风倒上 - 赵志刚--Greddy的个人主页)处,顺时针生成八分之一圆,利用对称性扫描转换全部圆。

  为了应用中点画圆法,我们定义一个圆函数

F(x,y)=x2+y2-R2(2-19)

  任何点(x,y)的相对位置可由圆函数的符号来检测:

F(x,y)Bresenham画圆和椭圆程序 - 随风倒上 - 赵志刚--Greddy的个人主页<0 style="line-height: 22px; margin-top: 0px; margin-right: 0px; margin-bottom: 10px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; ">

=0 点(x,y)位于数学圆上

>0 点(x,y)位于数学圆外

(2-20)

  如下图所示,图中有两条圆弧A和B,假定当前取点为Pi(xi,yi),如果顺时针生成圆,那么下一点只能取正右方的点E(xi+1,yi)或右下方的点SE(xi+1,yi-1)两者之一。

Bresenham画圆和椭圆程序 - 随风倒上 - 赵志刚--Greddy的个人主页

中点画线算法

  假设M是E和SE的中点,即 Bresenham画圆和椭圆程序 - 随风倒上 - 赵志刚--Greddy的个人主页,则:  1、当F(M)<0时,m在圆内(圆弧a),这说明点e距离圆更近,应取点e作为下一象素点;

  2、当F(M)>0时,M在圆外(圆弧B),表明SE点离圆更近,应取SE点;

  3、当F(M)=0时,在E点与SE点之中随便取一个即可,我们约定取SE点。

  Bresenham画圆和椭圆程序 - 随风倒上 - 赵志刚--Greddy的个人主页二、中点画圆算法思想

  因此,我们用中点M的圆函数作为决策变量di,同时用增量法来迭代计算下一个中点M的决策变量di+1。

Bresenham画圆和椭圆程序 - 随风倒上 - 赵志刚--Greddy的个人主页(2-21)

  下面分两种情况来讨论在迭代计算中决策变量di+1的推导。

  1、见图(a),若di<0,则选择e点,接着下一个中点就是Bresenham画圆和椭圆程序 - 随风倒上 - 赵志刚--Greddy的个人主页,这时新的决策变量为:

Bresenham画圆和椭圆程序 - 随风倒上 - 赵志刚--Greddy的个人主页(2-22)

Bresenham画圆和椭圆程序 - 随风倒上 - 赵志刚--Greddy的个人主页

(a)(di<0)>

  式(2-22)减去(2-21)得:

di+1=di+2xi+3(2-23)

  2、见图(b),若di≥0,则选择SE点,接着下一个中点就是Bresenham画圆和椭圆程序 - 随风倒上 - 赵志刚--Greddy的个人主页 ,这时新的决策变量为:

Bresenham画圆和椭圆程序 - 随风倒上 - 赵志刚--Greddy的个人主页(2-24)

Bresenham画圆和椭圆程序 - 随风倒上 - 赵志刚--Greddy的个人主页

(b)(di≥0) 中点画线算法

  式(2-24)减去(2-21)得:

di+1=di+2(xi-yi)+5(2-25)

  我们利用递推迭代计算这八分之一圆弧上的每个点,每次迭代需要两步处理:

   (1)用前一次迭代算出的决策变量的符号来决定本次选择的点。

   (2)对本次选择的点,重新递推计算得出新的决策变量的值。

  剩下的问题是计算初始决策变量d0,如下图所示。对于初始点(0,R),顺时针生成八分之一圆,下一个中点M的坐标是Bresenham画圆和椭圆程序 - 随风倒上 - 赵志刚--Greddy的个人主页 ,所以:

Bresenham画圆和椭圆程序 - 随风倒上 - 赵志刚--Greddy的个人主页(2-26)

Bresenham画圆和椭圆程序 - 随风倒上 - 赵志刚--Greddy的个人主页

生成圆的初始条件和圆的生成方向

  Bresenham画圆和椭圆程序 - 随风倒上 - 赵志刚--Greddy的个人主页三、中点画圆算法实现

  1、输入:圆半径r、圆心(x0,y0);

  2、确定初值:x=0,y=r、d=5/4-r;

  3、While(x<=y)

   {

    ·利用八分对称性,用规定的颜色color画八个象素点(x,y);

    · 若d≥0

      {

       y=y-1; //wind:个人觉得这句应该置于下句

       d=d+2(x-y)+5);

      }

     否则

       d=d+2x+3;

    ·x=x+1;

   }

  Bresenham画圆和椭圆程序 - 随风倒上 - 赵志刚--Greddy的个人主页五、中点画圆算法完善

  在上述算法中,使用了浮点数来表示决策变量d。为了简化算法,摆脱浮点数,在算法中全部使用整数,我们使用e=d-1/4代替d。显然,初值d=5/4-r对应于e=1-r。决策变量d<0对应于e<-1/4。算法中其它与d有关的式子可把d直接换成e。又由于e的初值为整数,且在运算过程中的迭代值也是整数,故e始终是整数,所以e<-1/4等价于e<0。因此,可以写出完全用整数实现的中点画圆算法。

  要求:写出用整数实现的中点画圆算法程序,并上机调试,观看运行结果。

  Bresenham画圆和椭圆程序 - 随风倒上 - 赵志刚--Greddy的个人主页六、中点画圆算法程序

void MidpointCircle(int x0,int y0,int r,int color)

{

 int x,y;

 float d;

 x=0;

 y=r;

 d=5.0/4-r;

 while(x<=y)

 {

  putdot(x0,y0,x,y,color);

  if(d<0)

  d+=x*2.0+3;

  else

  {

   d+=2.0*(x-y)+5;

   y--;

  }

  x++;

 }

}

putdot(x0,y0,x,y,color)

{

 putpixel(x0+x,y0+y,color);

 putpixel(x0+x,y0-y,color);

 putpixel(x0-x,y0+y,color);

 putpixel(x0-x,y0-y,color);

 putpixel(x0+y,y0+x,color);

 putpixel(x0+y,y0-x,color);

 putpixel(x0-y,y0+x,color);

 putpixel(x0-y,y0-x,color);

}

没有评论: