直线绘制算法

问题：已知起点p1(x1,y1)和终点p2(x2,y2)，绘制直线段p1p2.

Bresenham算法

(参考文章：https://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html)

算法：对于斜率m∈[0,1]，已知当前点，下一个点亦即增加1时，值取还是。

 

如图所示，红色直线表示理论直线，实际要绘制的直线过第一个点，ε为实际点和理论点的误差，这里需要根据该误差确定下一点的纵坐标取y还是y+1.

很明显，下一点的纵坐标的理论值y+ε+m<y+0.5即ε+m<0.5时，下一点应取(x+1,y)；否则取点(x+1,y+1)。

当接着绘制下一点时即x增加到x+2，误差ε需要更新，当上一步操作取点(x+1,y)亦即ε+m<0.5时，

否则亦即，

将ε+m<0.5两边同时乘以2去掉小数部分，将斜率m改写为，两边同时乘以dx，则不等式变为：

令δ=dxε，则上式变为：2(δ+dy)<dx

根据上面更新ε值，相应地也要更新δ：

                                                   (当2(δ+dy)<dx)

                                                  (当2(δ+dy)≥dx)

可以看到此时已经全部变为整数运算，因此对应的C++代码为：

void plotLine(const int x1, const int y1, const int x2, const int y2)
{
    //只考虑dx>=dy>=0的情形
    int dx = x2-x1;
    int dy = y2-y1;
    int y = y1;
    int eps = 0;
    for (int x = x1; x != x2; x++)
    {
        setPixel(x,y);
        eps += dy;
        if(2*eps >= dx)
        {
            y++;
            eps = eps-dx;
        }
    }
}

上面只是考虑了斜率0≤m≤1， x1<x2的情况，实际还有下面七种情形：

如果对每种情形枚举一次，那么代码将变得非常臃肿。我们发现斜率0<m≤1，x2<x1的情形与上面0≤m≤1，x1<x2的情形，改变的仅仅是增量的大小是1和-1的区别，因此上述代码变形为：

void plotLine(const int x1, const int y1, const int x2, const int y2)
{
    //只考虑0>dx>dy的情形
    int dx = x2-x1;
    int dy = y2-y1;
    int y = y1;
    int eps = 0;
    for (int x = x1; x != x2; x--)
    {
        setPixel(x,y);
        eps += dy;
        if(2*eps <= dx) //注意这里dx<0, dy<0
        {
            y--;
            eps = eps-dx;
        }
    }
}

综合上述2种情况(0≤m≤1，x2<x1和0≤m≤1，x1<x2)，增加2个变量ux，uy，当dx>0，x增量为正，否则为负；当dy>0，y增量为正，否则为负。代码变为：

void plotLine(const int x1, const int y1, const int x2, const int y2)
{
    //只考虑斜率0≤m≤1的情形
    int dx = x2-x1;
    int dy = y2-y1;
    int y = y1;
    int eps = 0;
    int ux = ((dx > 0) << 1) - 1;//x 增量方向，1 or -1
    int uy = ((dy > 0) << 1) - 1;//y 增量方向，1 or -1
    dx = abs(dx);
    dy = abs(dy); //这里取绝对值是为了下面2*eps >= dx条件的判断
    for (int x = x1; x != x2; x += ux)
    {
        setPixel(x,y);
        eps += dy;
        if(2*eps >= dx)
        {
            y += uy;
            eps = eps-dx;
        }
    }

对于斜率m为负的情况，如下图-1<m<0，x1<x2，按照同样的方法分析，当前绘制点为(x,y)，当 时，取（x+1,y-1），否则取点(x+1,y)。这里ϵ和m均小于0.

 

上述不等式去掉绝对值符号变为：

, 

令,上式变为：

更新误差δ：

 

我们对比观察，斜率0≤m≤1的情况的代码中，对dx、dy取绝对值已经包含了这种-1<m<0的情形，因此这种情况代码不变。

对于斜率大于1的情况，我们只需要将x，y轴反转一下，即将上面斜率小于1的情况中的x轴看成是y轴，y轴看成是x轴。因此代码如下：

void plotLine(const int x1, const int y1, const int x2, const int y2)
{
    //只考虑斜率0≤m≤1的情形
    int dx = x2-x1;
    int dy = y2-y1;
    int x = x1;
    int eps = 0;
    int ux = ((dx > 0) << 1) - 1;//x 增量方向，1 or -1
    int uy = ((dy > 0) << 1) - 1;//y 增量方向，1 or -1
    dx = abs(dx);
    dy = abs(dy);//这里取绝对值是为了下面2*eps >= dx条件的判断
    for (int y = y1; y != y2; y += uy)
    {
        setPixel(x,y);
        eps += dx;
        if(2*eps >= dy) //注意这里dx<0, dy<0
        {
            x += ux;
            eps = eps-dy;
        }
    }
}

 

综合上述几种情况，Bresenham直线算法代码如下：

void plotLine(const int x1, const int y1, const int x2, const int y2)
{
    int dx = x2 - x1;
    int dy = y2 - y1;
    int ux = ((dx > 0) << 1) - 1;
    int uy = ((dy > 0) << 1) - 1;
    int x = x1, y = y1, eps = 0; 
    dx = abs(dx);
    dy = abs(dy);
    if (dx > dy)
    {
        for (x = x1; x != x2; x += ux)
        {
            SetPixel(x,y);
            eps += dy;
            if ((2*eps) >= dx)
            {
                y += uy;
                eps -= dx;
            }
        }
    }
    else
    {
        for (y = y1; y != y2; y += uy)
        {
            SetPixel(x,y);
            eps += dx;
            if ((2*eps) >= dy)
            {
                x += ux;
                eps -= dy;
            }
        }
    }
}