3.2 圆与椭圆图形

3.2.1 简单方程产生圆弧

用圆的参数方程，直接计算离散点值。圆的参数方程为

x=x0+rcosθ y=y0+rsinθ

式中，x0和y0为圆的圆心坐标，r为圆的半径。

对以上方程进行离散化：

xi=x0+rcosθi

yi=y0+rsinθi

这里关键的问题是θi+1与θi的关系，即θi+1=θi+d中的d如何确定。如果使用画点生成圆，则d与圆的半径r相关，r越大，圆的周长就长，圆周上的像素点就多，对于固定范围内的θ，d就越小。根据圆周长公式，取d=1/（2πr）。因此离散化后圆的参数取值如下：

θ0=0,θi+1=θi+1/(2πr)i=0, 1, 2,…，直到θi=2π时结束，直到θi=2π时结束

其VC主要程序代码为：

CDC∗pDC=GetDC（）;
d=0.5/r/3.14;
for（t=0;t＜6.283;t=t+d）
{    x=x0+r∗cos（t）;
     y=y0+r∗sin（t）;
     pDC-＞SetPixel （x，y，RGB（0，0，0））;
}

此方法算法简单，但算法效率不高，有小数及函数运算，不易硬件实现。

3.2.2 中点画圆算法

1.八分法画圆

为了方便，我们只考虑中心在原点、半径为整数R的八分圆，圆的其他部分可通过一系列的简单反射变换得到，如图3-12所示。设已知一个圆心在原点的圆上一点（x，y），根据对称性可得另外7个八分圆上的对应点（y，x），（y，-x），（x，-y），（-x，-y），（-y，-x），（-y，x），（-x，y）。

对于中心不在原点的圆，可先对中心在原点的圆进行扫描转换，最后把所得的像素坐标加上圆的中心坐标即得所求像素坐标。

2.中点画圆算法基本原理

考虑如图3-13所示的八分圆的生成。讨论从（0，R）到（）顺时针圆弧的像素序列生成。假定与圆弧最近的P（x，y）像素已确定，那么下一个像素只能是正右方的P1（x+1，y）或右下方的P2（x+1，y-1）两者之一，如图3-14所示。

3.中点画圆算法的基本判别式

构造一个误差判别函数：F(x,y)=x2+y2-R2

对于圆上的点，F（x，y）=0；对于圆外的点，F（x，y）＞0；对于圆内的点，F（x，y）＜0。

设M是PlP2的中点，M=(xi+1,yi-0.5)。当F（M）＜0时，M在圆内，P1离圆弧更近，应取P1作为下一像素。当F（M）＞0时，P2离圆弧更近，应取P2。当F（M）=0时，在Pl与P2之中随便取一个即可，约定取P2。

与中点画线算法一样，构造判别式为

di=F(M)=F(xi+1,yi-0.5)=(xi+1)2+(yi-0.5)2-R2

4.中点画圆算法的递推公式

若di＜0，应取P1为下一像素，而且下一个像素的判别式为

di+1=F(xi+2,yi-0.5)=(xi+2)2+(yi-0.5)2-R2=di+2xi+3

若di≥0，则P2是下一像素，而且下一像素的判别式为

di+1=F(xi+2,yi-1.5)=(xi+2)2+(yi-1.5)2-R2=di+2xi+2yi+5

由于第1个像素是（0，R），判别式di的初始值为：

d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-R

根据上述分析，可写出中点画圆算法的递推公式如下：

d0=1.25-R,x0=0，y0=R

di＜0：di+1=di+2xi+3，xi+1=xi+1

di≥0：di+1=di+2xi-2yi+5，xi+1=xi+1，yi+1=yi-1(i=0,1,2,…，直到x＞y为止)

5.消除小数运算

在上述算法中，d使用了浮点数表示。为了摆脱浮点数，在算法中全部使用整数，使用e0=d0-0.25代替d0。

初始化运算d0=1.25-R对应于e0=1-R。

判别式di＜0对应于ei＜-0.25，又由于e的初值为整数，且在运算过程中的增量也是整数，故e始终是整数，所以ei＜-0.25等价于ei＜0。

其他与d有关的式子可把d直接换成e。因此，可以写出完全用整数实现的中点画圆算法。算法中e仍用d来表示。

d0=1-R,x0=0，y0=R

di＜0：di+1=di+2xi+3，xi+1=xi+1

di≥0：di+1=di+2xi-2yi+5，xi+1=xi+1，yi+1=yi-1(i=0,1,2,…，直到x＞y为止)

6.程序设计

中点画圆算法画圆弧的VC主要程序代码如下：

CDC.pDC=GetDC();
d=1-r; x=0; y=r; // r为圆的半径
while(y>=x)
{ pDC->SetPixel (x+x0,y+y0,RGB(0,0,0)); //（x0,y0）为圆心坐标
    pDC->SetPixel (-x+x0,y+y0,RGB(0,0,0));
    pDC->SetPixel (-x+x0,-y+y0,RGB(0,0,0));
    pDC->SetPixel (x+x0,-y+y0,RGB(0,0,0));
    pDC->SetPixel (y+x0,x+y0,RGB(0,0,0));
    pDC->SetPixel (-y+x0,x+y0,RGB(0,0,0));
    pDC->SetPixel (-y+x0,-x+y0,RGB(0,0,0));
    pDC->SetPixel (y+x0,-x+y0,RGB(0,0,0));
    x=x+1;
    if(d<0)
    d=d+2.x+3;
    else
      d=d+2.(x-y)+5, y--;
}

当x0=100，y0=100，r=80，该程序的运行效果如图3-15所示。

3.2.3 Bresenham画圆算法

Bresenham画圆算法的基本思想是寻找最接近于实际圆周上的点。与中点画圆算法相似，考虑圆心在原点，半径为R的八分圆，取（0，R）为起点，按顺时针方向生成圆。如图3-16所示，对于Pi的下一点Pi+1只有两种可能，即S（xi+1，yi）和T（xi+1，yi-1）。

1.基本判别式

根据圆的公式：x2+y2=R2

误差公式：

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

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

当|D（S）|≥|D（T）|，则T更接近于圆周，选择T。

当|D（S）|＜|D（T）|，则S更接近于圆周，选择S。

令di=|D(S)|-|D(T)|，则di≥0，取T；di＜0，取S。

由于判别式的di计算较复杂，因此要进行简化。

2.简化判别式

在S、T像素中，与理想圆弧最近者为所求像素。理想圆弧与这两个候选点之间的关系有以下几种情况：

情况C：S在圆外，所以D（S）＞0；T在圆内，所以D（T）＜0。因此判别式可简化为di=D(S)+D(T)。

下面分析一下其他情况是否可用此判别式。

情况A、B：S、T都在圆内或圆上，即D（S） ≤ 0，D（T）＜0，所以判别式di=D(S)+D(T)＜0，取S。从图3-16中可以看出S更接近圆周，选择S是对的。

情况D、E：S、T都在圆外或圆上，即D（S）＞0，D（T）≥0，所以判别式di=D（S）+D（T）＞0，取T。从图3-16中可以看出T更接近圆周，选择T是对的。

综上所述，只要计算出di=D(S)+D(T)的符号，便可确定是选S还是选T作为下一点。

3.判别式的递推公式

设x0=0，y0=R

d0=D(S)+D(T)=(12+R2-R2)+[12+(R-1)2-R2]=3-2R

设Pi为（xi，yi），则

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

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

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

di+1=di+4xi+6

设di≥0，则取T作为下一点，则

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

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

即Bresenham画圆算法的递归式为

d0=3-2R(x0=0，y0=R)

当di＜0时，

di+1=di+4(xi-yi)+6，xi+1=xi+1

当di≥0时，di+1=di+4(xi-yi)+10，xi+1=xi+1，yi+1=yi-1 (i=0,1,2,…，直到y＜x为止)，直到y＜x为止）

4.程序设计

Bresenham画圆算法绘制八分圆的VC主要代码如下：

3.2.4 椭圆算法

中点画圆算法可以推广到一般二次曲线的生成。下面讨论如何利用这种方法，对图3-17所示的标准椭圆进行扫描转换。

1.椭圆的特征

圆心在原点的椭圆方程为：

F(x,y)=b2x2+a2y2-a2b2=0

对于椭圆上的点，F（x，y）=0

对于椭圆外的点，F（x，y）＞0

对于椭圆内的点，F（x，y）＜0

由于椭圆的对称性，所以只需讨论第1象限椭圆弧的生成。在处理这段椭圆弧时，要把它分为两部分：上部分和下部分。以圆弧上斜率为1的点（即法矢量两个分量相等的点）作为分界来讨论，如图3-18所示。

椭圆上某一点（x，y）处的法矢量为：

式中，i和j分别为沿x轴和y轴方向的单位矢量。由图3-18知，在上部分，法矢量的y分量更大；而在下部分，法矢量的x分量更大。因此，若在当前中点，法矢量（2b2（xp+1），2a2（yp-0.5））的y分量比x分量大，即

b2（xp+1）＜a2（yp-0.5）

而在下一个中点，不等号改变方向，则说明椭圆弧从上部分转入下部分。

2.绘制椭圆的中点算法

绘制椭圆的中点算法与中点画圆算法类似，当确定一个像素之后，接着可在两个候选像素的中点计算一个判别式的值，并根据判别式符号确定两个候选像素哪个离椭圆更近。

（1） 上部分的算法判别式。先看椭圆弧的上部分，如图3-19所示，当前与椭圆弧最接近者是Pi（xi，yi），下一对候选像素的中点是M（xi+1，yi-0.5）。

判别式为

di=F(xi+1,yi-0.5)=b2(xi+1)2+a2(yi-0.5)2-a2b2

若di＜0，中点在椭圆内，则应取正右方像素，且判别式递推公式为

当di≥0，中点在椭圆之外，则应取右下方像素，且判别式递推公式为

（2） 判别式的初始值。由于弧的起点为（0，b），因此，第1个中点是（1，b-0.5），对应的判别式是

（3） 下部分的算法判别式。如图3-20所示，在下部分，当与椭圆弧最接近的像素是Pi（xi，yi）时，那么下一对候选像素应为正下方和右下方两个像素，中点是M（xi+0.5，yi-1）。所以当判别式di=F（xi

时，取右下方像素，下一点的判别式为

当di≥0取正下方像素，下一点的判别式为

（4） 第1象限椭圆弧中点算法。

x0=0，y0=b，d0=b2+a2（0.25-b）

当2b2（xi+1）＜2a2（yi-0.5）时，

当2b2（xi+1）＞2a2（yi-0.5）时，

（5） 程序设计（略）。

程序的运行效果如图3-21所示。

3.圆弧线宽的处理

为了生成具有宽度的圆弧，可采用与直线情形类似的方法。

当采用线刷子时，在经过曲线斜率为±1的点时，必须把线刷子在水平与垂直方向之间切换。由于线刷子总是放置成水平或垂直的，所以在曲线接近水平与垂直的地方，线条更粗一些，而在斜率接近±1的点附近，线条更细一些，如图3-22所示。

当采用正方形刷子时，无须移动刷子方向。只需顺着单像素宽的轨迹，把正方形中心对准轨迹上的像素，把方形内的像素全部用线条颜色填充。用正方形刷子绘制的曲线条，在接近水平与垂直的部分最细，而在斜率为±1的点附近最粗，这恰与线刷子画线的情形相反，如图3-23所示。