一个算法只有整形加法,没有浮点运算,没有取整运算才是我们最想要的算法。
一、圆弧扫描算法
下面仅以圆心在原点,半径R为整数的圆为例,讨论圆的生成算法。
圆的方程,那么,,如果这样直接画圆的话,其缺点为:
①:运算复杂,有浮点运算,还有开方,最后Y还有个取整运算。
②:画的圆也不均匀。在下面半个圆中可以看出,当斜率小时,x变化1,y变化小,进而画的比较密,反之亦然。如图所示:
二、角度DDA法
显然也不适合用算法实现。
三、中点画圆算法
利用圆的八对称性,只需要讨论圆。
P为当前点亮像素,那么下一个点亮像素可能是P1()或P2()。选取的原则看P1和P2的中点M。若M在圆内,取P1,反之亦然。那么如何看M在圆内还是圆外?把M点带入圆方程,若大于0,则表示在圆外。如图所示:
判别规则为:
算法描述为:
四、Bresenham画圆算法
如图所示,是已选中的一个表示圆弧上的点,根据圆弧的走向,下一个点应该从或中选择。那么选择的原则是什么?
显然,分别把和带入圆的隐式方程,若时,选,否则选。
把上式弄成增量的形式:
令,当选,否则选。
那么如何快速计算,设的坐标为,则坐标为,的坐标为,为:
其中是有两种情况的,分别将两种情况带入得到对比和之间的关系: