Bresenham的圆算法python bresenham算法画圆原理

文章目录

• 前言
• Bresenham 画圆算法原理

• 两个近似
• 构造判别式
• 圆与网格点的关系

• 关系由来
• 关系含义

• pi
• 画圆
• 程序伪码

• 圆与网格点的关系图示

前言

首先简要介绍一下生成圆的方法：

1. 直接利用圆的方程生成圆
2. 利用圆的对称性生成圆

方法一由于会涉及到浮点运算等因素，不采取该方案。

ps. 这部分想要知道为什么可以参考 计算机图形学 圆及椭圆的扫描转换_百度文库 前面一点。

方法二的原理如下图，利用圆的对称性，我们只需要对一个八分圆进行扫描转换。

在这里我们不妨选择第一象限上斜率绝对值小于1的那八分圆进行扫描转换，以及假设圆心为 (0, 0) 。也就是下图。

友情提示：圆在某点的斜率是该点处切线斜率。圆心不在 (0, 0) 处的点可以通过平移得到。

Bresenham 画圆算法原理

如下图，在 0≤x≤y 的 1/8 圆周上，像素坐标 x 值单调增加，y 值单调减少。

设第 i 步已确定是要画圆上的像素点，看第 i+1 步像素点应如何确定。下一个像素点只能是或者中的一个 。

具体选哪个就得看

1. 更小，下一个像素点就选
2. 更小，下一个像素点就选
3. 一样大，选哪个都行。

比较方法就是做差：，然后将结果与0进行比较。

那么问题是

两个近似

近似方法：
将 CH 近似为
将 DB 近似为

由大图显而易见可以知道 CH 和 DB 的值：

这里由于涉及到了根号运算，因此又做了一个近似：

构造判别式

我们不妨构造如下判别式

圆与网格点的关系

关系由来

圆与网格点有且仅有上述5种关系，情况分别如上：

其中的BCEF均为该网格上的中点。

首先，我们得再次强调的一点是，在 0≤x≤y 的 1/8 圆周上的每点的斜率绝对值都小于1。即它们与 x 轴负方向的倾角都不能超过图中的 FE 线段。

由于，我们现在点亮的点是 ，所以圆与 x=1 的交点应该在 BF 之间。由于此段圆弧的斜率均小于1，因此圆与 x=2 的交点应该在 CE 之间，由此上上图中的 5 条圆弧都有了解释：
圆弧1：圆与 x=1 的交点在 BP 间，且该圆斜率变化很小（半径很大）
圆弧4，5：我个人认为是在接近 y=x 这条直线处的网格可以产生这种情况

关系含义

构造判别式：

1. 精确圆弧是③，则
   
   
2. 若精确圆弧是①或②，显然H是应选择点，而此时，必有。
3. 若精确圆弧是④或⑤，显然D是应选择点，而此时，必有。

得出结论： 做判别量， 时，选H点为下一个像素点，

因为 代表此次选择哪个点的判别式，如果我们知道下一次选点的判别式和其关系就可以节省很多思考。所以我们要从 计算 。
ps. 对 数学意义的解释：此次点亮的点我们称做，下一次点亮的点我们就称做 。 的值和 是有递推关系的（ ，见关系由来下的图）。而此次我们将判断点亮哪个点的判别式记作 ，类似的，下次判断点亮哪个点的判别式我们就记作

1. 当 时，应选D点，此时 D 点的 y 坐标和 P 的 y 坐标的关系是 ，带入上式有：
   
2. 当 时，应选H点，此时 H 点的 y 坐标和 P 的 y 坐标的关系是 ，带入上式有：
   

画圆

画圆的起始点是(0, R)，即 ，带入前式。即令 i=1 ，就得到：

剩下的递推就行。

程序伪码

void BresenhamCircle(int R){     
	int x,y,p;
	x=0;  y=R;
	p=3-2*R;
	for(;x<=y;x++){       
		SetPixel(x,y);
		if(p>=0){
			p+=4*(x-y)+10;
			y--;
		}
		else {
			p+=4*x+6;
		}
	}
}

根据对称性，只需修改语句 SetPixel(x,y)，画八个对称的点，就可以画出全部圆周。若加一个平移，就可以画出圆心在任意位置的圆周

圆与网格点的关系图示

情况一：
其中

情况五：，那条横线是 y=77.5
其中

时间有限，姑且只画这俩。