直线扫描算法主要包含三种算法，DDA算法、中点画线算法、Bresenham直线算法。

这三种算法都要事先要确定两个端点（起点和终点），从起点开始每次走一步，每走一步画一个点，直至到达终点。

（x，y）坐标实际上是像素点的坐标，那么必须得是整数。以下算法得到的坐标若不为整数，都应该进行四舍五入的操作。

前提

1.png

这个前提也比较好理解，因为如果朝斜率大的方向走，可能没走几步就走完了，那画出来的直线就是离散的。

以下我们只讨论朝x方向移动的情况。（y方向的情况是一样的）

1. DDA算法

DDA算法实际上是根据斜截式直线方程来画的。

但这么做实际上是比较消耗性能的，因为斜截式方程，它涉及到了乘法运算。因此我们需要通过增量思想对它进行优化。

DDA.png

这样转换后，我们就可以根据当前的位置来找到下一步的位置，且每次计算只需要进行一次浮点的加法运算，一次四舍五入取整即可。

2. 中点画线算法

中点画线算法实际上是根据一般式直线方程来画的。它是通过判断中点在直线的下方还是上方，来决定下一步的坐标位置。

Ax+By+C>0，（ x , y ）在直线上方

Ax+By+C<0，（ x , y ）在直线下方

Ax+By+C=0，（ x , y ）在直线上

中点画线算法.png

但这样也是非常消耗性能的，把中点带入F(x, y)中，会涉及到2个乘法，4个加法。我们依然可以通过增量的方式来对它进行优化。

• 首先我们先来证明下A,B,C都是整数。
  
  1.png

• 接着我们来对刚才的算法进行优化。

2.png

这样我们就优化到每次只需要一次整数加法即可，且还不需要四舍五入。因此它要更优于DDA算法。

3. Bresenham直线算法

Breseham算法是通过比较d(交点与交点下方最近的点的距离)来进行选择的。d每次按照k的大小增加。

Bresenham算法.png

但这么做依旧和DDA算法一样，会涉及到浮点数k的加法。我们可以通过换元的方式对它进行下优化。

Bresenham算法2.png

这样就能使得每次进行一次或两次的整数加法运算，不需要四舍五入。效率高于DDA，低于中点画线算法。

但Bresenham算法不依赖直线方程，使得它能有更宽泛的适用范围。