3.2 圆的扫描转换

3.2.1 圆的扫描转换概述

圆的扫描转换就是在屏幕像素点阵中确定一组最佳逼近于圆的像素点，并用指定的颜色显示出来。

当圆心在坐标原点时，圆的方程为x2+y2＝R2；当圆心不在坐标原点时，首先获得圆心通过坐标原点的圆的最佳像素逼近点，再对像素逼近点进行坐标平移即可。

由于圆具有对称性，在进行扫描转换时，只需迭代生成八分之一圆的最佳像素逼近点，圆的其他部分通过简单的坐标对称就可以直接得到，如图3.2-1所示。假设已知圆上的一个点（x，y），则利用对称性，可得到圆上其他的七个点（x，－y），（－x，y），（－x，－y），（y，x），（y，－x），（－y，x），（－y，－x）。

3.2.2 中点画圆算法

中点画圆法和直线的中点画线法的原理类似，首先，构造圆的隐式方程

圆上的点F（x，y）＝0，圆外的点F（x，y）＞0，圆内的点F（x，y）＜0，在直角坐标第一象限，从点（0，R）到的八分之一圆弧内，x值按像素单位递增，y值逐渐减少。构造判别式

若d≥0，则该点在圆外，如图3.2-2（a）所示，最佳像素逼近点应取（xi+1，yi－1），则构造下一个像素点的判别式为

即增量为2（xi－yi）+5。

若d＜0，则该点在圆内，如图3.2-2（b）所示，最佳像素逼近点应取（xi+1，yi），则构造下一个像素点的判别式为

即增量为2xi+3。

初始的构造点为（1，R－0.5），判别式为

在上述方法中，初始判别式的计算中出现了小数，可以通过乘以4将小数转换为整数，则迭代算法可改进为

d≥0，取（xi+1，yi－1），d1＝d+8（xi－yi）+20

d＜0，取（xi+1，yi），d1＝d+8xi+12

中点画圆算法的函数参考代码如下：

3.2.3 Bresenham画圆算法

圆的Bresenham算法和直线的Bresenham算法类似，在迭代时，也是通过判断圆上的点与附近像素点距离的差值正负，来获得最佳像素逼近点。在迭代时，也是只需计算直角坐标第一象限从（0，R）到的八分之一圆弧最佳逼近点，其他点通过对称得到。

设圆的当前最佳逼近点为（xi，yi），则当xi+1＝xi+1时，y2＝R2－（xi+1）2，下一个最佳逼近点为（xi+1，yi）或者（xi+1，yi－1），如图3.2-3所示。则构造下面的判别式：

令pi＝d1－d2，则

若pi＞0，则取点（xi+1，yi－1），再下一个像素点的判别式为

即增量是4（xi－yi）+10。

若pi≤0，则取点（xi+1，yi），再下一个像素点的判别式为

即增量是4xi+6。

在（0，R）点时可得判别式的初值：

Bresenham画圆算法的函数代码参考如下：

通过比较Bresenham画圆算法代码和中点画圆算法，可以看到，虽然两种算法的基本原理和推导过程不同，但是算法的构造迭代公式却基本上是相同的，因此两种算法的计算速度也是相同的。

在应用程序中生成圆时，可以按照如下方法建立圆的结构类：

在视图窗口类中建立圆的集合：CArray<CCircle,CCircle>m_circle_array;，利用鼠标在视图窗口拾取圆心，并设计或者输入圆的半径值，也可以类似直线生成程序，利用橡皮筋技术实时生成，并比较中点画圆算法和Bresenham画圆算法，如图3.2-4所示。圆生成程序的流程和代码可参考3.1节“直线的扫描转换”中的相关内容实现。

3.2.4 圆弧段的扫描转换

圆弧段的扫描转换是指仅将圆中的任意一段圆弧利用一组屏幕像素点最佳逼近，并用指定的颜色显示出来。圆弧段的扫描转换也可以利用圆的扫描转换方法的中点画圆算法或者Bresenham算法的思路实现，但是，由于圆弧段在圆上的位置具有任意性，圆弧段的长度和两个端点的位置也是任意的，所以，圆弧段的扫描转换实现方法比整个圆在标准的八分之一圆弧上通过镜像生成的扫描转换方法复杂。

圆上两点之间对应的圆弧段有两个，为了具有确定性，设其中一个点为圆弧的起点，另外一个点为圆弧的终点，从起点到终点顺时针方向的这段圆弧为所求的圆弧段。

首先，利用轴线、45°及135°线作镜像线将圆划分成如下八个区域，按顺时针方向分别用数字0～7进行编号，如图3.2-5所示。整圆的中点画圆算法和Bresenham画圆算法都是首先在圆的0号区域进行迭代生成，其他区域的点利用镜像对称性生成。点之间的对称性可以利用坐标变换矩阵表示，设0号区域的矩阵为，则其他区域的坐标变换矩阵分别为，由于对称性，矩阵T（4）、T（5）、T（6）、T（7）可以分别通过将矩阵T（0）、T（1）、T（2）、T（3）乘以－1获得到。

设圆上0区域的一个点（x0，y0）用向量表示为［x0 y0］，则其在其他区域的镜像点——例如i区域的镜像点（x，y）——的向量为该点向量乘以i区域的坐标变换矩阵得到：

相反，当圆上点在其他区域，例如k区域的一个点（x1，y1），如要获得其在0区域的镜像对应点，可通过该点的向量乘以k区域坐标变换矩阵的逆矩阵计算得出：

同理，圆上其他某个区域内的圆弧段在0区域上也对应了一段圆弧，那么，只要在0区域上对与其对应的圆弧段的最佳像素逼近点利用中点画线算法或者其他算法进行迭代生成，但是对像素点不进行颜色显示，而是通过坐标变换矩阵仅在要求的圆弧段上的像素显示颜色，这样，就实现了其他圆弧区域内的任意圆弧段的扫描转换。这种方法的关键是要准确找到圆弧段在0区域所对应的位置以及起始和终止点。

设圆弧段的起点为（xs，ys），终点为（xe，ye），圆弧所在圆的圆心为（xc，yc），半径为R。圆弧段的起点（xs，ys）和终点（xe，ye）的位置关系有两种情况，第一种情况是起点和终点在同一个区域内，第二种情况是起点和终点不在同一个区域，即横跨几个区域。这两种情况需要分别考虑。

当起点和终点在同一个区域内时，扫描转换方法即为上述的圆上其他某个区域内的圆弧的生成方法：用起点和终点的向量乘以所在区域的坐标变换矩阵的逆矩阵即得两点在0区域的对应点，对0区域的两点之间的圆弧进行迭代生成，然后转换到起点和终点所在的区域显示。设起点（xs，ys）的对应点是（x0，y0），终点（xe，ye）的对应点是（x1，y1），如图3.2-6所示。如果镜像转换后圆弧的方向发生了变化，那么应将起点和终点互换。

由于圆弧段不一定是完整的八分之一圆弧，利用算法迭代生成时，计算初始判别式值的构造点不再是（0，R），而是起点（x0，y0）。例如中点画圆算法的初始判别式的值为

和圆的算法处理方法相同，将判别式乘以4，把小数变成整数：

同样，迭代的终止条件也要修改为圆弧画到终点（x1，y1）时结束。利用上述算法即可绘制出整个部分都在一个区域内的圆弧段。

当起点和终点横跨几个区域时，即不在同一个区域的情况，为了生成圆弧，首先将圆弧段分成三个部分分别处理，这三部分分别是起点所在区域的圆弧段、终点所在区域的圆弧段以及起点和终点之间隔着的几个八分之一区域的圆弧段，如图3.2-7所示。这样划分后，起点和终点所在的圆弧段就符合同在一个区域的情况，这时，圆弧段的另外一个端点在镜像线上，利用上述一个区域内的圆弧段的扫描转换方法就可以生成。在具体实现时需要注意，同样的圆弧段处在不同的区域时，在0区域对应的圆弧段的位置是不同的，同一个区域的起点和终点的圆弧段在0区域对应的圆弧段的位置也是不同的。设起点（xs，ys）所在的区域是Is，在0区域的对应点是（x0，y0）。

当Is∈［0，2，4，6］时，起点部分的圆弧段在0区域对应的是段圆弧；

当Is∈［1，3，5，7］时，起点部分的圆弧段在0区域对应的是［（0，R），（xs，ys）］段圆弧。

同样区域的终点部分的圆弧在0区域对应的圆弧段和起点部分的圆弧在0区域对应的圆弧段恰好相反。

圆弧起点和终点之间隔着的中间几个区域部分的圆弧是0区域的八分之一圆弧段的整数倍，利用中点画圆算法或者Bresenham画圆算法将0区域的圆弧段迭代生成后，通过其他几个区域的坐标变换矩阵获得对应区域的像素点，即可得到这几个部分的圆弧段。

起点部分的圆弧、终点部分的圆弧以及中间部分的圆弧合在一起就是所需生成的圆弧段。

由于起点和终点在圆上的位置是任意的，起点和终点所在的区域也是任意的，但是，圆弧段是指顺时针方向从起点到终点的圆弧，为了使区域具有连贯性，应该保证终点所在区域的编号不小于起点区域的编号。设终点所在的区域是Ie，对Ie作如下处理：

当Ie＜Is时，Ie＝Ie+8。

在计算所在区域的坐标变换矩阵或者逆矩阵时，将Ie与8求余数：Ie＝Ie%8，即得准确的区域编号。

上述圆弧段实现方法的函数代码参考如下：

上述代码中，查找圆弧端点所在的区域编号的函数如下：

其中，计算区域坐标变换矩阵的函数为：

利用坐标变换矩阵生成区域的像素点和变换逆矩阵获得在0区域的对应点的函数为：

下面是代码中用到的具体一个圆弧段的生成函数，其中迭代生成点的方法利用的是中点画圆算法的原理：

上述算法生成圆弧段的效果图如图3.2-8所示。

除了利用圆心、起点和终点确定圆弧外，利用其他方式也可以确定一个圆弧段。例如，圆上三个点确定一个圆弧，已知圆心、起点和圆弧角也可以确定一个圆弧。利用其他方式得到的圆弧可以通过计算转换成圆心、起点、终点的圆弧段表示。由于圆弧段是整圆的一部分，圆弧段也可以通过圆的裁剪生成，为了使圆和圆弧具有统一的表示方法，对圆的结构类作如下进一步的改进：