中点画圆法中,计算判别式d使用了浮点运算,影响了圆的生成效率。如果能将判别式规约到整数运算,则可以简化计算,提高效率。于是人们针对中点画圆法进行了多种改进,其中一种方式是将d的初始值由1.25 – R改成1 – R,考虑到圆的半径R总是大于2,因此这个修改不会影响d的初始值的符号,同时可以避免浮点运算。还有一种方法是将d的计算放大两倍,同时将初始值改成3 – 2R,这样避免了浮点运算,乘二运算也可以用移位快速代替,采用3 – 2R为初始值的改进算法,又称为Bresenham算法:
void Bresenham_Circle(int xc, int yc, int r)
{
int x, y, d;
x = 0;
y = r;
d = 3 - 2 * r;
CirclePlot(xc, yc, x, y);
while (x < y)
{
if (d < 0)
{
d = d + 4 * x + 6;
}
else
{
d = d + 4 * (x - y) + 10;
y--;
}
x++;
CirclePlot(xc, yc, x, y);
}
}
通过EasyX实现:
#include <graphics.h>
#include <conio.h>
// 使用 Bresenham 画圆法
void Circle_Bresenham(int x, int y, int r, int color)
{
int tx = 0, ty = r, d = 3 - 2 * r;
while (tx <= ty)
{
// 利用圆的八分对称性画点
putpixel(x + tx, y + ty, color);
putpixel(x + tx, y - ty, color);
putpixel(x - tx, y + ty, color);
putpixel(x - tx, y - ty, color);
putpixel(x + ty, y + tx, color);
putpixel(x + ty, y - tx, color);
putpixel(x - ty, y + tx, color);
putpixel(x - ty, y - tx, color);
if (d < 0) // 取上面的点
d += 4 * tx + 6;
else // 取下面的点
d += 4 * (tx - ty) + 10, ty--;
tx++;
}
}
// 主函数
int main()
{
initgraph(640, 480);
// 测试画圆
Circle_Bresenham(320, 240, 200, RED);
Circle_Bresenham(320, 240, 101, RED);
// 按任意键退出
_getch();
closegraph();
return 0;
}
结果如下:
参考资料:
https://codebus.cn/yangw/a/bresenham-s-circle-algorithm