实验二 笛卡尔法，极坐标法，Bresenham 算法画圆 一、 实验原理 Bresenham 算法画圆 Bresenham 画圆算法是最有效的算法之一，考虑以圆心的第一个四分之一圆。如 果以点 x=0、y=R 为起点顺时针方向生成圆时，则在第一像限内 y 是 x 的单调减函数。 从圆的任意一点出发，按顺时针方向生成圆时，最佳逼近像素的取法只的三种可能性， 即右方像素、右下方像素和下方像素。根据这种思想将其分成以下 5 种可能情况（如 图 1）。 笛卡尔法，极坐标法 主要是利用数学公式的思想来画圆 二、 算法推导： Bresenham 算法推导： 推导第一象限 y＝0 到 y＝x 圆弧段的扫描转换算法，坐标的选择不选择共有以下 5 种情 况 1 2 3 p 5 4 图 1 y 坐标 圆心角 α 误差项 d 理想点 Q 取下一个点 d 更新 y=0 y=x y=x y=1 0°<=α<=45° 45°<=α<=90° <0 在中点右 取右点 d+2y+3 >=0 在中点左 <0 在中点上 >=0 在中点下 取左点 取上点 取下点 d-2(y-x)+5 d+2x+3 d-2(x-y)+5 在 x=y 到 y=0 的圆弧中，（R,0）点此在圆弧上，最大位移方向为 y，由（R,0）点开始， y 渐增，x 渐减，每次 y 方向加 1，x 方向减 1 或减 0。 设 P 点坐标（xi,yi）,下一个候选点为右点 Pr（xi,yi+1）和左点 Pl（xi-1,yi+1）， 取 Pl 和 Pr 的中点 M（xi-0.5,yi+1），设理想圆与 y=yi+1 的交点 Q， 构造判别式：d=f(xM,yM)=(x-0.5)2+(yi+1)2+R2 当 d<0 时，M 在 Q 点左方（Q 在 M 右），取右点 Pr（xi,yi+1） 当 d>0 时，M 在 Q 点右方（Q 在 M 左），取左点 Pl（xi-1,yi+1） 当 d=0 时，M 与 Q 点重合，约定取左点 Pl（xi-1,yi+1） 

所以有：y 1i =y i +1 x 1i =x i -1 或 x i 推导判别式： d>=0 时，取左点 Pl（xi-1,yi+1），下一点为（xi-1,yi+2）和（xi-2,yi+2） d<0 时，取右点 Pr（xi,yi+1），下一点为（xi,yi+2）和（xi-1,yi+2） 极坐标算法： 极坐标算法主要是利用数学公式 x1=R*cos(x);y1=R*sin(x)来画圆 迪卡尔算法： 迪卡尔算法主要是利用数学公式 R 2 =X 2 +Y 2 来画 三、 详细算法： BresenHam 算法： void CMy200915303View::OnBRESENHAMcircle(int x1, int y1, int x2, int y2) { CDC*pDC; COLORREF Color=RGB(255,0,0); pDC=GetDC(); x1=point1.x; y1=point1.y; x2=point2.x; y2=point2.y; double r; r=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); double delta,delta1,delta2; int x,y,direction; x=0; y=int(r+0.5); delta=2*(1-r); while (y>=0) //在 Y>0 的前提下绘制二分之一圆 

{ pDC->SetPixel(x1+x,y1+y,color); pDC->SetPixel(x1+x,y1-y,color); pDC->SetPixel(x1-x,y1+y,color); pDC->SetPixel(x1-x,y1-y,color); if (delta<0) { delta1=2*(delta+y)-1; if (delta1<=0) direction=1; else direction=2; } if (delta>0) { delta2=2*(delta-x)-1; if (delta2<=0) direction=2; else direction=3; } if (delta==0) { direction=2; } switch(direction) { case 1: x++; delta+=2*x+1; break; case 2: x++; y--; delta+=2*(x-y+1); break; case 3: y--; delta+=(-2*y+1); break; } } } 

极坐标画圆算法 void CMy200915303View::onjizuobiao(float R) { x=0; float float x1=0,y1=0; while(x>=0&&x<=180/4) { circlepoint(x1,y1) ; x=x+0.1; x1=R*cos(x); y1=R*sin(x); } } 迪卡尔画圆算法 void CMy200915303View::dcart(float R) { float x=-R,y; CDC *p=GetDC(); y=sqrt(R *R-x*x); while(x<=R) { p->SetPixel(x+100,y+100,RGB(0,255,255)); p->SetPixel(x+100,-y+100,RGB(0,0,0)); x++; y=sqrt(R*R-x*x); } } 三、 试验结果： 

五、小结