|
发表于 2018-5-11 18:07:19
|
显示全部楼层
本帖最后由 王涛 于 2018-5-11 18:09 编辑
谢谢,分析。
下面是Bresenham's line and circle algorithm数学模型
可是看了半天代码分析和这个模型就是关联不起来。
https://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html
(x, y +ε)的下一个点为(x, y + ε + m),这里ε为累加误差。
可以看出,当ε+m < 0.5时,绘制(x + 1, y)点,否则绘制(x + 1, y + 1)点。
每次绘制后,ε将更新为新值:
ε = ε + m ,如果(ε + m) < 0.5
ε = ε + m – 1, 其他情况
这里判别条件的 (ε + m) < 0.5
即 2*(ε + m) < 1
即 2*(ε + dy / dx) < 1 (由于m = dy / dx)
即 2*(ε* dx + dy) < dx (同乘以dx)
令ξ = ε*dx 可得
ξ = ξ + dy, 如果2*(ξ + dy) < dx
ξ = ξ + dy – dx, 其他情况
可以看到,此时运算已经全变为整数了。以下为算法的伪代码:
ξ ← 0, y ← y1
For x ← x1 to x2 do
Plot Point at (x, y)
If (2(ξ + dy) < dx)
ξ ←ξ + dy
Else
y ← y + 1,ξ ←ξ + dy – dx
End If
End For |
|