Bresenham 算法
1965 年,Bresenham 为数字绘图仪开发了一种绘制直线的算法,该算法同样使用于光栅扫描显示器,被称为 Bresenham 算法。
原理
算法的目标是选择表示直线的最佳光栅位置。Bresenhan 算法在主位移方向上每次递增一个单位。另一个方向的增量为 0 或 1,取决于理想直线于最近网格点的距离,这一距离称为误差项,误差项用 d 表示。
当 x x x 方向递增一个单位,有 d = d + k d = d+ k d=d+k; 则
y
i
+
1
=
{
y
i
+
1
;
d
≥
0.5
y
i
d
<
0.5
y_{i+1} = \begin{cases} y_i + 1; &\quad d \geq 0.5\\ y_i &\quad d < 0.5 \end{cases}
yi+1?={yi?+1;yi??d≥0.5d<0.5?
误差项初始值
d
0
=
0
d_0 = 0
d0?=0, 如果
d
≥
0.5
d \geq 0.5
d≥0.5,
y
y
y 方向递增一个单位并且将
d
d
d 减 1.
消除 0.5 的影响
令 e = d ? 0.5 e = d -0.5 e=d?0.5. 当 x x x 方向走一步,有 e = e + k e = e + k e=e+k, 则
y i + 1 = { y i + 1 ; e ≥ 0 y i e < 0.5 y_{i+1} = \begin{cases} y_i + 1; &\quad e \geq 0\\ y_i &\quad e < 0.5 \end{cases} yi+1?={yi?+1;yi??e≥0e<0.5?
e 0 = ? 0.5 e_0 = -0.5 e0?=?0.5 , 如果 e ≥ 0 e \geq 0 e≥0, 则 e = e ? 1 e = e -1 e=e?1
消除浮点数的影响,斜率和 e e e, 进行整数化
当
0
≤
k
≤
1
0 \leq k \leq 1
0≤k≤1,
Δ
x
\Delta x
Δx 为正
e
=
2
Δ
x
e
=
2
Δ
x
(
d
?
0.5
)
=
?
Δ
x
+
2
Δ
x
d
e = 2 \Delta x e = 2 \Delta x (d-0.5) = -\Delta x + 2 \Delta x d
e=2Δxe=2Δx(d?0.5)=?Δx+2Δxd
初始值
e
0
=
?
Δ
x
e_0 = -\Delta x
e0?=?Δx
当 x 方向走一步,有
e
+
=
2
Δ
y
e += 2 \Delta y
e+=2Δy
如果 e ≥ 0 e \geq 0 e≥0 有
e = 2 Δ x ( e ? 1 ) = 2 Δ x e ? 2 Δ x e ? = 2 Δ x e = 2 \Delta x (e-1) = 2 \Delta x e - 2 \Delta x \\ e -= 2 \Delta x e=2Δx(e?1)=2Δxe?2Δxe?=2Δx
算法
- 设置像素点的颜色
- 读入直线的两个端点坐标
- 取 e e e 的初始值为 e 0 = ? 0.5 e_0 = -0.5 e0?=?0.5
- 从起点开始,沿着 x x x 轴方向每递增一个单位,有 e + = 2 Δ y e += 2 \Delta y e+=2Δy
- 当 ≥ 0 \geq 0 ≥0 时,下一个像素更新为 ( x i + 1 , y i + 1 ) (x_i + 1, y_i + 1) (xi?+1,yi?+1), 同时将 e e e 更新为 e ? = 2 Δ x e -= 2 \Delta x e?=2Δx, 否则,下一个像素更为 ( x i + 1 , y i + 1 ) (x_i + 1, y_i +1) (xi?+1,yi?+1)
- 绘制像素点,执行 x + + x++ x++ 操作到终点
void BresenhamLine(CDC* pDC, CPoint P0, CPoint P1)
{
COLORREF crColor = RGB(0, 0, 0);
int dx = P1.x - P0.x;
int dy = P1.y - P0.y;
int e = - dx;
for (int x=P0.x, y=P0.y; x < P1.x; x++) {
pDC->SetPixelV(x, y, crColor);
e += 2 * dy;
if (e >= 0) {
y++;
e -= 2 * dx;
}
}
}
整数 Bresenham 算法是一种经典的直线光栅化算法, 使用了最小的计算量,使得单点生成算法已经没有改进的余地。
参考 《计算几何算法与实现》孔令德
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!