文章目录
- 前言
- Bresenham 画圆算法原理
- 两个近似
- 构造判别式
- 圆与网格点的关系
- 关系由来
- 关系含义
- p i p_i pi 递推
- 画圆
- 程序伪码
- 圆与网格点的关系图示
前言
首先简要介绍一下生成圆的方法：
- 直接利用圆的方程生成圆
- 利用圆的对称性生成圆
方法一由于会涉及到浮点运算等因素，不采取该方案。
ps. 这部分想要知道为什么可以参考 计算机图形学 圆及椭圆的扫描转换_百度文库 前面一点。
方法二的原理如下图，利用圆的对称性，我们只需要对一个八分圆进行扫描转换。
在这里我们不妨选择第一象限上斜率绝对值小于1的那八分圆进行扫描转换，以及假设圆心为 (0, 0) 。也就是下图。
友情提示：圆在某点的斜率是该点处切线斜率。圆心不在 (0, 0) 处的点可以通过平移得到。
Bresenham 画圆算法原理
如下图，在 0≤x≤y 的 1/8 圆周上，像素坐标 x 值单调增加，y 值单调减少。
设第 i 步已确定 （ x i , y i ） （x_i, y_i） （xi,yi）是要画圆上的像素点，看第 i+1 步像素点 （ x i + 1 , y i + 1 ） （x_{i+1}, y_{i+1}） （xi+1,yi+1）应如何确定。下一个像素点只能是 H （ x i + 1 , y i ） H（x_i+1, y_i） H（xi+1,yi）或者 D （ x i + 1 , y i − 1 ） D（x_i+1,y_i-1） D（xi+1,yi−1）中的一个 。
具体选哪个就得看 d H 和 d D d_H 和 d_D dH和dD 二者的比较了：
- d H d_H dH 更小，下一个像素点就选 H （ x i + 1 , y i ） H（x_i+1, y_i） H（xi+1,yi）
- d D d_D dD 更小，下一个像素点就选 D （ x i + 1 , y i − 1 ） D（x_i+1,y_i-1） D（xi+1,yi−1）
- 一样大，选哪个都行。
比较方法就是做差： d H − d D d_H - d_D dH−dD，然后将结果与0进行比较。
那么问题是 d H 和 d D d_H 和 d_D dH和dD 二者的值是怎么求得呢？这里就涉及到一个近似：
两个近似
近似方法：
将 CH 近似为 d H d_H dH
将 DB 近似为 d D d_D dD
由大图显而易见可以知道 CH 和 DB 的值：
C H = O H − O C = ( x i + 1 ) 2 + y i 2 − R = d H CH = OH - OC = \sqrt{(x_i+1)^2 + y_i^2} - R = d_H CH=OH−OC=(xi+1)2+yi2−R=dH
D H = O B − O D = R − ( x i + 1 ) 2 + ( y i − 1 ) 2 = d D
