3.3 椭圆的扫描转换

中点画圆法可以推广到一般二次曲线的扫描转换，例如椭圆的扫描转换。图3.3-1所示通过坐标原点的椭圆方程为

其中a为沿x轴方向的长半轴长度，b为沿y轴方向的短半轴长度。由于椭圆具有对称性，因此只需讨论第一象限部分的椭圆的生成，其他三部分通过对称实现。在处理这段椭圆弧时，需要从弧上斜率为－1（即法向矢量为1）的点进一步把它分为上下两部分，如图3.3-2所示，法向量N＞1，即点在上一部分时，在x方向进行单位增量；法向量N＜1，即点在下一部分时，在y方向进行单位增量。

与中点画圆算法类似，首先在做选择的两个像素的中点处构造判别式，并根据判别式的正负来确定最佳逼近像素，然后，再构造下一个判别式。

假设当前最佳像素逼近点为（xi，yi），在x方向进行单位增量，构造中点为（xi+1，yi－0.5），则判别式为

若d＜0，构造的中点在椭圆内，则下一个最佳像素点为（xi+1，yi）。再构造下一个中点为（xi+2，yi－0.5），则判别式为

即增量为b2（2xi+3）。

若d≥0，构造的中点在椭圆外，则下一个最佳像素点为（xi+1，yi－1）。再构造下一个中点为（xi+2，yi－1.5），则判别式为

即增量为b2（2xi+3）+a2（－2yi+2）。

从起点（0，b）处开始构造初始中点（1，b－0.5），对应的初始判别式为

上述迭代是法向量N≥1时的算法。当N＜1时，在y方向单位增量。根据微分知识，椭圆上点（x，y）处的法向量N为

其中i和j分别为该点在x方向和y方向的单位向量。当N≥1时，法向量y分量较大；N＜1时，法向量x分量较大。因此N≥1时，即为2b2x≤2a2y⇒b2x≤a2y，由于构造的中点和椭圆上的点非常接近，可以认为构造的中点（xi+1，yi－0.5）也满足

在构造下一个中点时，如果上面的不等式不再成立，则说明这时椭圆上点的法向量N＜1，这时开始在y方向单位增量。

与在x方向的单位增量计算迭代类似，构造N＜1时的中点和判别式。假设当前最佳像素逼近点为（xi，yi），在y方向单位增量，构造中点为（xi+0.5，yi－1），则判别式为

若d＜0，构造的中点在椭圆内，下一个最佳像素点为（xi+1，yi－1）。再构造下一个中点为（xi+1.5，yi－2），则判别式为

即增量为b2（2xi+2）+a2（－2yi+3）。

若d≥0，构造的中点在椭圆外，下一个最佳像素点为（xi，yi－1）。再构造下一个中点为（xi+0.5，yi－2），则判别式为

即增量为a2（－2yi+3）。

当yi＝0时，迭代终止。

上述的椭圆中点算法函数代码参考如下：

在应用程序中生成椭圆时，可建立如下的椭圆类：

在视图窗口类建立椭圆的集合：CArray<CEllipse,CEllipse>m_ellipse_array;，通过窗口拾取椭圆的中心点和设计两个半轴的长度，或者直接通过对话框输入对应值，生成的椭圆如图3.3-3所示。椭圆生成程序的流程和代码可参考3.1节“直线的扫描转换”中的相关内容实现。