直线绘制的三个著名的常用算法(三)Bresenham算法

(3)Bresenham算法

——>【画线算法不依赖于直线方程】
——>【提供了一个更一般的算法,不仅有好的效率还有更广泛的适用范围】

算法思想:通过各行、各列象素中心构造一组虚拟网格线,按照直线起点到终

点的顺序,计算直线与各垂直网格线的交点,然后根据误差项的符号确定该列

象素中与此交点最近的象素。


每次x+1,y的递增(减)量为0或1,它取决于实际直线与最近光栅网格点的距离,这个距离最大误差为0.5

误差项d的初值为0,d=d+k,一旦d>=1,就把它减去1,保证d的相对性,且在0、1之间。

将算法效率提高——>也处理成整数加法:

改进一:令e=d-0.5





Bresenham算法很像DDA算法,都是加斜率

但DDA算法是每次求一个新的y以后取整来画,

而Bresenham算法是判断符号来决定上下两个点。

所以Bresenham算法集中了DDA和中点两个算法的优点,而且应用范围广泛。


【小结】计算机科学问题的核心就是算法。
         把一个含乘法和一个加法的普通直线算法,是如何通过改进和完善其性能,最终变成整数加法的一个精彩过程。

原文地址:https://www.cnblogs.com/Penglimei/p/9669257.html