Impossible is nothing  
  爱过知情重醉过知酒浓   花开花谢终是空   缘份不停留像春风来又走   女人如花花似梦
公告
日历
<2022年9月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678
统计
  • 随笔 - 8
  • 文章 - 91
  • 评论 - 16
  • 引用 - 0

导航

常用链接

留言簿(4)

随笔分类(4)

随笔档案(8)

文章分类(77)

文章档案(91)

相册

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 

在进行圆的转换时,只要能生成8分圆,那么圆的其它部分可通过一系列的简单反射变换得到。本小节介绍一种常用的画圆算法:Bresenham画圆算法。

Bresenham算法:不失一般性,考虑圆心在原点,半径为R的第一个4分圆。取(0,R)为起点,按顺时针方向生成圆。从这段圆弧的任意一点出发,按顺时针方向生成圆时,为了最佳逼近该圆,下一象素的取法只要三种可能的选择:正右方象素,右下方象素和正下方象素。

 

xi+1=xi+1

相应的yi+1则在两种可能中选择:

yi+1=yi,或者yi+1=yi-1

选择的原则是考察精确值y靠近yi还是靠近yi-1(图1),计算式为

y2=r2-(xi+1)2

d1=yi2-y2

    =yi2-r2+(xi+1)2

d2=y2-(yi-1)2

    =r2-(xi+1)2-(yi-1)2

2_2_2.gif (3311 bytes)

图1

 

令pi=d1-d2,并代入d1, d2,则有

pi=2(xi+1)2+yi2+(yi-1)2-2r2 (2.2.1)

pi称为误差。如果pi<0则yi+1=yi,否则yi+1=yi-1。pi的递归式为:

pi+1=pi+4xi+6+2(yi2+1-yi2)-2(yi+1-yi) (2.2.2)

pi的初值由式(2.6)代入xi=0, yi=r而得

          p1=3-2r (2.2.3)

根据上面的推导,圆周生成算法思想为:

1、求误差初值,p1=3-2r; i=1;画点(0, r);

 

2、求下一个光栅位置:

xi+1=xi+1;

if pi<0 则yi+1=yi;

否则yi+1=yi-1;

 

3、画点(xi+1, yi+1)

 

4、计算下一个误差:

if pi<0 则pi+1=pi+4xi+6;

否则 pi+1=pi+4(xi-yi)+10;

5、i=i+1; if x=y则end;否则返2。

 

虽然式(2.2.2)式表示pi+1的算法似乎很复杂,但因为yi+1只能取值yi或yi-1,因此在算法中,第4步的算式变得很简单,只须作加法和4的乘法。因此圆的Bresenham算法运行速度也是很快的,并适宜于硬件实现。

圆的Bresenham算法的程序实现见程序2.2.1。

circle (xc, yc, radius, c)

int xc, yc, radius, c;

{

int x, y, p;

x=0;

y=radius;

p=3-2*radius;

while (x<y){

        plot_circle_points(xc, yc, x, y, c);

        if (p<0) p=p+4*x+6;

        else{

                  p=p+4*(x-y)+10;

                  y-=1;

                }

        x+=1;

                 }

if (x= =y)

        plot_circle_points(xc, yc, x, y, c);

}

 

plot_circle_points(xc, yc, x, y, c)

int xc, yc, x, y, c;

{

set_pixel(xc+x, yc+y, c);

set_pixel(xc+x, yc+y, c);

set_pixel(xc+x, yc-y, c);

set_pixel(xc-x, yc-y, c);

set_pixel(xc+y, yc+x, c);

set_pixel(xc-y, yc+x, c);

set_pixel(xc+y, yc-x, c);

set_pixel(xc-y, yc-x, c);

} 

 

 Bresenham的圆生成算法

 设圆之半径为r。先考虑圆心在(0,0),并从x=0, y=r开始的顺时针方向的1/8圆周的生成过程。在这种情况下,x每步增加1,从x=0开始,到x=y结束。即有:

给出圆心坐标xc, yc,和半径r,逐点画出一个圆周的公式有下列两种:

 

1、直角坐标法:

(x-xc)2+(y-yc)2=r2

由上式导出

y=

x-xc从-r到r作加1递增时,就可以求出对应的圆周点的y坐标。但是这样求出的圆周上的点是不均匀的;|x-xc|越大,对应生成圆周点之间的圆周距离也就越长。因此,所生成的圆不美观。.

2、极坐标法:

x=xc+r·cosθ

y=yc+r·sinθ

θ 从0 度到360 作加1递增时,由此式便可求出圆周上均匀分布的360个点的x, y坐标。利用圆周坐标的对称性,此算法还可以简化:将圆周分为8个象限(图2.2.1)。只要将第1a象限中的圆周光栅点求出,其余7部分圆周就可以通过 对称法则计算出来。图2.2.1给出了圆心在0,0点时的对称变换法则。但即使作了如此简化,用上述公式每算一点,都要经过三角函数计算,仍有相当大的计算量。

 

  2_2_1.gif (3964 bytes)

图2.2.1 圆心在0,0点圆周生成时的对称变换

 

在计算机中上述两个公式所示的方法生成圆周都颇费时,下面介绍的算法则要简捷得多。

3.圆的Bresenham算法

posted on 2006-02-24 22:21 笑笑生 阅读(1427) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


 
Copyright © 笑笑生 Powered by: 博客园 模板提供:沪江博客