用 C++ 实现画直线算法，通过实验学习并掌握数值微分算法 (DDA) 以及 Bresenham 算法。

1. 实现数值微分法(DDA) 直线算法
   打开line.cpp 文件，完成DDADrawLine 函数。函数的传入参数包括直线起点beginPoint 以及直线终点endPoint。需要实现DDA 画线算法，然后将计算出的点存入result 中。
2. 实现Bresenham 直线算法
   打开line.cpp 文件，完成BresenhamDrawLine 函数。函数的传入参数包括直线起点beginPoint以及直线终点endPoint。需要实现BresenhamDrawLine 画线算法，然后将计算出的点存入result 中。

1、实现DDA算法

1.1 原理分析及算法描述

在绘制直线的过程中，所绘制的后一个点就是前一个点加上单位增量后四舍五入到整数像素点的过程，从而一步步逼近直线。

假设起点的坐标为整数，直线方程为y=kx+b, k的取值在0到1之间, x每递增1, y相应地递增k。因为像素的坐标为整数, 所以y要四舍五入。当k>1时, 将对x和y的操作反过来，即y每递增1,x相应地递增1/k。

1.2 代码实现与分析

std::vector<Point> DDADrawLine(Point beginPoint, Point endPoint)
{
    // @TODO implement DDA draw line algorithm here.
    /*
    draw line between beginPoint and endPoint
    save all points into result
    */
    std::vector<Point> result;
    int step = max(abs(endPoint.x - beginPoint.x), abs(endPoint.y - beginPoint.y));//取x,y中变化较大的一方的变化量为步长
    double dx = 0, dy = 0;
    if (step) {
        dx = (endPoint.x - beginPoint.x) * 1.0 / step;
        dy = (endPoint.y - beginPoint.y) * 1.0 / step;
    }//计算x,y的单位增量
    result.push_back(beginPoint);//插入起点

    double dx = 0, dy = 0;
    if (step) {
        dx = (endPoint.x - beginPoint.x) * 1.0 / step;
        dy = (endPoint.y - beginPoint.y) * 1.0 / step;
    }
    result.push_back(beginPoint);
    double x = beginPoint.x, y = beginPoint.y;
    //开始迭代，次数为步长的数值
    for (int i = 0; i < step; i++) {
        x += dx, y += dy;
        int x1 = x, y1 = y;
        if (abs(dx) == 1) {//如果单位步长为x的单位增量
            //对y进行四舍五入操作
            y1 = y > 0 ? (int)(y + 0.5) : (int)(y - 0.5);
        }
        else {//如果单位步长为y的单位增量
            //对x进行四舍五入的操作
            x1 = x > 0 ? (int)(x + 0.5) : (int)(x - 0.5);
        }
        Point t;//设置临时变量t，保存当前迭代的像素点坐标
        t.x = x1, t.y = y1;
        result.push_back(t);//向结果中插入计算得出的像素点坐标
    }
    return result;
}

2、实现 Bresenham 算法

2.1 原理分析与算法描述

因指向方向和斜率的不同，直线在平面象限中共有8种情况。在此先选取一种情况进行分析。

设给定起点$(x_0,y_0)$和终点$(x_1,y_1)$，由两点所确定的直线为y=kx+b,x的单位增量为1
$$△x=x_1-x_0>0,△y=y_1-y_0,k=△y/△x,|k|<=1$$
由直线方程计算出下一个要绘制的点为
$$x_{i+1}=x_i+1,y_{i+1}=k{x}_{i+1}+b;$$
选取距离该点最近的整数像素点，该像素点的$y$坐标只能为$y_i或y_{i+1}$

两个候选的像素点到交点的距离为
$$d_{upper}={\hat{y}}_i+1-y_{i+1},d_{lower}=y_{i+1}-{\hat{y}}_i$$

$$d_{lower}-d_{upper}=2k(x_i+1)-2{\hat{y}}_i+2b-1$$

因我们只关心$d_{lower}-d_{upper}$的正负，且$△x$大于0，所以可将上式转化为下式
$$p_k=△x(d_{lower}-d_{upper})=2△y\cdot x_i-2△x\cdot {\hat{y}}_i+(2b-1)△x+2△y$$
经计算后
$$p_0=2△y-△x$$

$$若p<0,p_{k+1}=p_k+2△y,若p>=0,p_{k+1}=p_k+2△y-2△x$$

2.2 代码实现

//Line.cpp中附有完整代码
std::vector<Point> result;
int dx = endPoint.x - beginPoint.x, dy = endPoint.y - beginPoint.y;//计算总变化量
double k = 0;
if (abs(dx))k = abs(dy)*1.0 / abs(dx);
int x = beginPoint.x, y = beginPoint.y;
result.push_back(beginPoint);

if (dx > 0 && dy > 0&&k<1) {//此为上述讨论的情况
    int pk = 2 * dy - dx;
    int times = 0;
    //开始迭代
    while (times < abs(dx)) {//因为k<1.所以x的变化量dx更大，以其绝对值为迭代次数
        x++;
        //判断决策变量pk
        if (pk < 0) {
            pk = pk + 2 * dy;
        }
        else {
            pk = pk + 2 * dy - 2 * dx;
            y++;
        }
        Point t;
        t.x = x; t.y = y;
        result.push_back(t);//插入计算后的像素点
        times++;
    }
}

可以通过上述分析的情况推导出其他7种情况：（注：下面说的某条线属于某个象限指的是该线的指向）

对于相同象限，斜率不同的情况，就是将直线作关于y=x(或y=-x)的对称直线，对应到代码中就是将所有的y和x调换位置，但输出位置不变。

对于不同象限，斜率相同的情况，就是将点$(x_0,y_0),(x_1,y_1)$,进行正负号的改变，将其转移到第一象限中进行运算，输出的点再进行一次符号改变（即还原其原始符号）。

对于象限不同，斜率也不同的情况，就将上述两种情况结合，以此类推。

在Line.cpp中有剩余情况的完整代码实现，此处不再赘述。

结果展示

DDA 算法

Bresenham 算法

分析总结

1. DDA 算法与Bresenham 算法的区别

   1.1 效率

   • DDA是最简单的线条绘制算法，但涉及浮点数运算，且对每个新像素点都要进行四舍五入操作，比较耗时。
   • Bresenham 算法效率相对较高，计算速度快，因为它在迭代过程中不涉及浮点数运算。

   1.2 涉及的计算

   • DDA涉及浮点数运算和四舍五入操作，不利于用硬件实现。
   • Bresenham基本只做整数加减法和乘2运算，而乘2运算可以用硬件移位实现。

   1.3 计算结果

   • DDA的误差较大，因为对于下一个绘制点，它并不是与理想点比较，而是在上一个点的基础上选择下一个点，而只有第一个点是理想点，所以随着绘制点数的增大，误差会越来越大。

   1.4 精度

   • 从DDA算法中得到的点不够准确，通过该算法绘制的线中可以看到一些中断点和之字形线条。
   • Bresenham算法生成的点比DDA算法更准确，但生成的线条依旧不够光滑，它无法处理锯齿点。

2. 比较两个算法的运行速度

   编写小型测试程序比较两个算法的运行速度

   测试说明：分别利用两种算法绘制5000个点。

   DDA 算法

Bresenham算法

可见，在绘制5000个点的情况下，两种算法运行速度十分接近。