【LCD画圆】算法系列之十一：圆生成算法
【超给力追-女技巧】【企鹅:⒈０１⒍.x.９５２б】 算法系列之十一：圆生成算法
分类： 算法系列
2012-02-12 21:45 6828人阅读 评论(21) 收藏 举报
输入您的搜索字词 提交搜索表单
在平面解析几何中，圆的方程可以描述为(x – x0)2 + (y – y0)2 = R2，其中(x0,
y0)是圆心坐标，R是圆的半径，特别的，当(x0, y0)就是坐标中心点时，圆方程可以简化为x2 + y2 =
R2。在计算机图形学中，圆和直线一样，也存在在点阵输出设备上显示或输出的问题，因此也需要一套光栅扫描转换算法。为了简化，我们先考虑圆心在原点的圆的生成，对于中心不是原点的圆，可以通过坐标的平移变换获得相应位置的圆。
在进行扫描转换之前，需要了解一个圆的特性，就是圆的八分对成性。如图（1）所示：
图（1）圆的八分对称性
圆心位于原点的圆有四条对称轴x = 0、y = 0、x = y和x
= -y，若已知圆弧上一点P(x，y)，就可以得到其关于四条对称轴的七个对称点：（x, -y）、（-x, y）、（-x,
-y）、（y, x）、（y, -x）、（-y, x）、（-y,
-x），这种性质称为八分对称性。因此只要能画出八分之一的圆弧，就可以利用对称性的原理得到整个圆。
有几种较容易的方法可以得到圆的扫描转换，首先介绍一下直角坐标法。已知圆方程：x2
+ y2 = R2，若取x作为自变量，解出y，得到：
在生成圆时先扫描转换四分之一的圆周，让自变量x从0到R以单位步长增加，在每一步时可解出y，然后调用画点函数即可逐点画出圆。但这样做，由于有乘方和平方根运算，并且都是浮点运算，算法效率不高。而且当x接近R值时(圆心在原点)，在圆周上的点（R，0）附近，由于圆的斜率趋于无穷大，因浮点数取整需要四舍五入的缘故，使得圆周上有较大的间隙。接下来介绍一下极坐标法，假设直角坐标系上圆弧上一点P(x，y)与x轴的夹角是θ，则圆的极坐标方程为：
x = Rcosθ y = Rsinθ
生成圆是利用圆的八分对称性，使自变量θ的取值范围为(0，45°)就可以画出整圆。这个方法涉及三角函数计算和乘法运算，计算量较大。直角坐标法和极坐标法都是效率不高的算法，因此只是作为理论方法存在，在计算机图形学中基本不使用这两种方法生成圆。下面就介绍几种在计算机图形学中比较实用的圆的生成算法。
中点画圆法
首先是中点画圆法，考虑圆心在原点，半径为R的圆在第一象限内的
八分之一圆弧，从点（0, R）到点（R- , R-
）顺时针方向确定这段圆弧。假定某点Pi(xi,
yi)已经是该圆弧上最接近实际圆弧的点，那么Pi的下一个点只可能是正右方的P1或右下方的P2两者之一，如图（2）所示：
图（2）中点划线法示例 构造判别函数： F(x, y）= x2 + y2 –
当F(x, y）= 0，表示点在圆上，当F(x, y） 0，表示点在圆外，当F(x, y）
0，表示点在圆内。如果M是P1和P2的中点，则M的坐标是（xi + 1, yi – 0.5），当F（xi + 1, yi –
0.5） 0时，M点在圆内，说明P1点离实际圆弧更近，应该取P1作为圆的下一个点。同理分析，当F（xi + 1, yi –
0.5） 0时，P2离实际圆弧更近，应取P2作为下一个点。当F（xi + 1, yi – 0.5）= 0时，P1和P2都可以作为圆的下一个点，算法约定取P2作为下一个点。
现在将M点坐标（xi + 1, yi –
0.5）带入判别函数F(x, y），得到判别式d： d = F（xi + 1, yi – 0.5）= (xi + 1)2 + (yi – 0.5)2 – R2
0，则取P1为下一个点，此时P1的下一个点的判别式为：
d’ = F（xi + 2, yi – 0.5）= (xi + 2)2 + (yi – 0.5)2 – R2
展开后将d带入可得到判别式的递推关系： d’ = d + 2xi + 3
0，则取P2为下一个点，此时P2的下一个点的判别式为： d’ = F（xi + 2, yi – 1.5）= (xi + 2)2 + (yi – 1.5)2 – R2
展开后将d带入可得到判别式的递推关系： d’ = d + 2(xi - yi) +
特别的，在第一个象限的第一个点（0, R）时，可以推倒出判别式d的初始值d0：
d0 = F(1, R – 0.5) = 1 – (R – 0.5)2 – R2 = 1.25 - 根据上面的分析，可以写出中点画圆法的算法。考虑到圆心不在原点的情况，需要对计算出来的坐标进行了平移，下面就是通用的中点画圆法的源代码：
26?void MP_Circle(int xc 28?int x, y; 29?double d;
CirclePlot(xc , yc , x 35?while(x y)
CirclePlot(xc , yc , x
?参数xc和yc是圆心坐标，r是半径，CirclePlot()函数是参照圆的八分对称性完成八个点的位置计算的辅助函数。
改进的中点画圆法－Bresenham算法
中点画圆法中，计算判别式d使用了浮点运算，影响了圆的生成效率。如果能将判别式规约到整数运算，则可以简化计算，提高效率。于是人们针对中点画圆法进行了多种改进，其中一种方式是将d的初始值由1.25
– R改成1 –
R，考虑到圆的半径R总是大于2，因此这个修改不会响d的初始值的符号，同时可以避免浮点运算。还有一种方法是将d的计算放大两倍，同时将初始值改成3
– 2R，这样避免了浮点运算，乘二运算也可以用移位快速代替，采用3 –
2R为初始值的改进算法，又称为Bresenham算法： 52?void Bresenham_Circle(int xc 54?int x, y,
CirclePlot(xc , yc , x 60?while(x y)
CirclePlot(xc , yc , x 正负判定画圆法
除了中点画圆算法，还有一种画圆算法也是利用当前点产生的圆函数进行符号判别，利用负反馈调整以决定下一个点的产生来直接生成圆弧，
o R b I t 程 序 设 计 与 算 法
