易懂的Bresenham算法计算圆上各点坐标

Bresenham简介：

在我们内部开发使用的一个工具中，我们需要几乎从 0 开始实现一个高效的二维图像渲染引擎。比较幸运的是，我们只需要画直线、圆以及矩形，其中比较复杂的是画直线和圆。画直线和圆已经有非常多的成熟的算法了，我们用的是Bresenham的算法。

计算机是如何画直线的？简单来说，如下图所示，真实的直线是连续的，但我们的计算机显示的精度有限，不可能真正显示连续的直线，于是我们用一系列离散化后的点（像素）来近似表现这条直线。

如下图：

　而Bresenham直线算法是用来描绘由两点所决定的直线的算法，它会算出一条线段在 n 维光栅上最接近的点。这个算法只会用到较为快速的整数加法、减法和位元移位，常用于绘制电脑画面中的直线。是计算机图形学中最先发展出来的算法。

对于圆来说，我们可以利用其对称性，求出八分之一圆上所有点的坐标，那么其余七部分所有坐标便全都求了出来，以至于为什么是八分，其原因就是：八分之一部分可以保证切线斜率绝对值在[0,1]之间，这才是使用Bresenham算法的基础。而实现Bresenham的根本之道便是求出迭代决策公式 —— 距离相减求误差，判断误差正负选增量方向；

具体推导过程：

由于篇幅原因，转载一下别人的推导公式：https://blog.csdn.net/mayh554024289/article/details/44781531（实话：时间关系，编者懒。。。公式不想推。）

最后得到的便是下面的算法步骤中的第4步判别式；

算法步骤：

1、输入圆的半径r;

2、计算初始值d=1.25-r，x=0，y=r;

3、根据对称性计算出八分圆中另外的七个对称点；

4、判断d的符号，若d>0,则将d+=2x+3，否则将d+=2（x-y）+5，并且将y--；最后再将x++;

5、当x<y时，重复3、4步骤，否则结束；

#include<cstdio>
#include<cmath>
int main() {int r;printf("请输入半径：\n");scanf("%d",&r);int a,b;printf("请输入圆心坐标");scanf("%d%d",&a,&b);int d=1-r;int x=0;int y=r;for(; x<y; ++x) {printf("第一象限上:(%d，%d)\n",x+a,y+b);printf("第一象限下:(%d，%d)\n",y+a,x+b);printf("第二象限上:(%d，%d)\n",y+a,-x+b);printf("第二象限下:(%d，%d)\n",x+a,-y+b);printf("第三象限下:(%d，%d)\n",-x+a,-y+b);printf("第三象限上:(%d，%d)\n",-y+a,-x+b);printf("第四象限下:(%d，%d)\n",-y+a,x+b);printf("第四象限上:(%d，%d)\n",-x+a,y+b);printf("\n");if(d<=0)d+=2*x+3;else {y--;d+=2*(x-y)+5;}}return 0;
}