欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

直线绘制算法

程序员文章站 2022-03-22 15:57:45
...

问题:已知起点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≤1x2<x1的情形与上面0≤m≤1x1<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种情况(0m≤1x2<x10≤m≤1x1<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<0x1<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;
            }
        }
    }
}