直线生成算法

DDA算法

数值微分法即DDA法（Digital Differential Analyzer），是一种基于直线的微分方程来生成直线的方法。

一、直线DDA算法描述：

设\((x_{1}, y_{1})\)和\((x_{2}, y_{2})\)分别为所求直线的起点和终点坐标，由直线的微分方程得

\[\frac{\mathrm{dy}}{\mathrm{d}x}=\frac{y_{2}-y_{1}}{x_{2}-x_{1}}=\frac{\Delta y}{\Delta x}=m\qquad (2-1) \]

\(m\)为直线的斜率

可通过计算由x方向的增量△x引起\(y\)的改变来生成直线：

\[x_{i+1}=x_{i}+\Delta x\qquad (2-2)\\ y_{i+1}=y_{i}+\Delta y=y_{i}+\Delta x·m\qquad (2-3) \]

也可通过计算由y方向的增量△y引起\(x\)的改变来生成直线：

\[y_{i+1}=y_{i}+\Delta y\qquad (2-4)\\ x_{i+1}=x_{i}+\Delta x=x_{i}+\frac{\Delta y}{m}\qquad (2-5) \]

式(2－2)至(2－5)是递推的。

二、直线DDA算法思想：

　　选定\(x_{2}-x_{1}\)和\(y_{2}-y_{1}\)中较大者作为步进方向(假设\(x_{2}-x_{1}\)较大)，取该方向上的增量为一个像素单位（\(\Delta x=1\)），然后利用式(2－1)计算另一个方向的增量\(\Delta y = \Delta x \times m = m\)。通过递推公式\((2－2)\)至\((2－5)\)，把每次计算出的\((x_i+1，y_i+1)\)经取整后送到显示器输出，则得到扫描转换后的直线。

　　之所以取\(x_{2}-x_{1}\)和\(y_{2}-y_{1}\)中较大者作为步进方向，是考虑沿着线段分布的像素应均匀，这在下图中可看出。

　　另外，算法实现中还应注意直线的生成方向，以决定\(\Delta x\)及\(\Delta y\)是取正值还是负值。

三、直线DDA算法实现：

已知直线的两端点坐标：\((x_{1}, y_{1})\)和\((x_{2}, y_{2})\)
已知画线的颜色：color
计算两个方向的变化量：

\[dx = x_{2}-x_{1}\\ dy = y_{2}-y_{1} \]
求出两个方向最大变化量的绝对值：

\[steps = max(|dx|, |dy|) \]
计算两个方向的增量（考虑了生成方向）：

\[x_{in}=\frac{dx}{steps}\\ y_{in}=\frac{dy}{steps} \]
设置初始像素坐标：

\[x=x_{1}\\y=y_{1} \]
用循环实现直线的绘制：

for(i = 1; i <= steps; i++) {
    // 在(x，y)处，以color色画点
	putpixel(x，y，color);
	x=x+xin;
	y=y+yin;
}

五、直线DDA算法特点：

该算法简单，实现容易，但由于在循环中涉及实型数的运算，因此生成直线的速度较慢。

六、代码实现

#include<Windows.h>
#include<graphics.h>
#include<conio.h>
#include<math.h>

void dda_line(int xa, int ya, int xb, int yb, int c);

int main(int argc, _TCHAR *argv[]) {
    int gd = DETECT, gm; /*图形屏幕初始化*/
    initgraph(&gd, &gm, "");
    dda_line(100, 100, 200, 200, 255);
    getch();
    closegraph();
    return 0;
}

void dda_line(int xa, int ya, int xb, int yb, int c) {
    float delta_x, delta_y, x, y;
    int dx, dy, steps, k;
    dx = xb - xa;
    dy = yb - ya;
    if (abs(dx) > abs(dy))steps = abs(dx);
    else steps = abs(dy);
    delta_x = (float) dx / (float) steps;
    delta_y = (float) dy / (float) steps;
    x = xa;
    y = ya;
    putpixel(x, y, c);
    for (k = 1; k <= steps; k++) {
        x += delta_x;
        y += delta_y;
        putpixel(x, y, c);
    }
}

Bresenham算法

从上面介绍的DDA算法可以看到，由于在循环中涉及实型数据的加减运算，因此直线的生成速度较慢。

在生成直线的算法中，Bresenham算法是最有效的算法之一。Bresenham算法是一种基于误差判别式来生成直线的方法。

一、直线Bresenham算法描述：

　　它也是采用递推步进的办法，令每次最大变化方向的坐标步进一个像素，同时另一个方向的坐标依据误差判别式的符号来决定是否也要步进一个像素。

　　我们首先讨论\(m={\frac{\Delta y}{\Delta x}}\)，当\(0≤m≤1\)且\(x_{1}<x_{2}\)时的Bresenham算法。从DDA直线算法可知这些条件成立时，公式\((2-2)\)、\((2-3)\)可写成：

\[x_{i+1}=x_{i}+1\qquad (2-6)\\ y_{i+1}=y_{i}+m\qquad (2-7) \]

　　有两种Bresenham算法思想，它们各自从不同角度介绍了Bresenham算法思想，得出的误差判别式都是一样的。

二、直线Bresenham算法思想之一：

　　由于显示直线的像素点只能取整数值坐标，可以假设直线上第i个像素点坐标为\((x_{i}, y_{i})\) ，它是直线上点\((x_{i}, y_{i})\) 的最佳近似，并且\(x_{i}=x_{i}\)（假设\(m<1\)），如下图所示。那么，直线上下一个像素点的可能位置是\((x_{i}+1,y_{i})\)或\((x_{i}+1,y_{i}+1)\)。

　　由图中可以知道，在\(x=x_{i}+1\)处，直线上点的y值是\(y=m(x_{i}+1)+b\)，该点离像素点\((x_{i}+1, y_{i})\)和像素点\((x_{i}+1, y_{i}+1)\)的距离分别是\(d1\)和\(d2\)：

\[d1=y-y_{i}=m(x_{i}+1)+b-y_{i}\qquad(2-8)\\ d2=(y_{i}+1)-y=(y_{i}+1)-m(x_{i}+1)+b\qquad(2-9) \]

　　这两个距离差是

\[d1-d2=2m(x_i+1)-2y_i+2b-1\qquad(2-10) \]

　我们来分析公式\((2-10)\)：

当此值为正时，\(d1>d2\)，说明直线上理论点离\((x_{i}+1,y_{i}+1)\)像素较近，下一个像素点应取\((x_{i}+1,y_{i}+1)\)。
当此值为负时，\(d1<d2\)，说明直线上理论点离\((x_{i}+1,y_{i})\)像素较近，则下一个像素点应取\((x_{i}+1,y_{i})\)。
当此值为零时，说明直线上理论点离上、下两个像素点的距离相等，取哪个点都行，假设算法规定这种情况下取\((x_{i}+1,y_{i}+1)\)作为下一个像素点。

因此只要利用\((d1-d2)\)的符号就可以决定下一个像素点的选择。为此，我们进一步定义一个新的判别式：

\[p_i=\Delta x \cdot (d1-d2)=2\Delta y*x_i-2\Delta x\cdot y_i+c\qquad(2-11) \]

式\((2-11)\)中的\(\Delta x=(x_2-x_1)>0\)，因此\(p_i\)与\((d_1-d_2)\)有相同的符号；这里\(\Delta y=y_2-y_1, m=\frac{\Delta y}{\Delta x}, c=2\Delta y+\Delta x(2b-1)\)。

下面对式\((2-11)\)作进一步处理，以便得出误差判别递推公式并消除常数c。

将式\((2-11)\)中的下标\(i\)改写成\(i+1\)，得到：

\[p_{i+1}=2\Delta y\cdot x_i-2\Delta x*y_i+1+c\qquad(2-12) \]

　　将式\((2-12)\)减去\((2-11)\)，并利用\(x_i+1=x_i+1\)，可得：

\[p_i+1=p_i+2\Delta y-2\Delta x\cdot(y_{i+1}-y_i)\qquad(2-13) \]

　　再假设直线的初始端点恰好是其像素点的坐标，即满足：

\[y_1=mx_1+b\qquad(2-14) \]

　　由式\((2-11)\)和式\((2-14)\)得到p1的初始值：

\[p_1=2\Delta y-\Delta x\qquad(2-15) \]

　　这样，我们可利用误差判别变量，得到如下算法表示\((2-16)\)：

初始

\[p_1=2\Delta y-\Delta x \]

当\(p_i\ge0\)时

\[y_{i+1}=y_i+1\\ x_{i+1}=x_i+1\\ p_{i+1}=p_i+2(\Delta y-\Delta x) \]
否则

\[y_{i+1}=y_i\\ x_{i+1}=x_i+1\\ p_{i+1}=p_i+2\Delta y \]

从式\((2-16)\)可以看出，第\(i+1\)步的判别变量\(pi+1\)仅与第\(i\)步的判别变量\(p_i\)、直线的两个端点坐标分量差\(\Delta x\)和\(\Delta y\)有关，运算中只含有整数相加和乘2运算，而乘2可利用算术左移一位来完成，因此这个算法速度快并易于硬件实现。

三、直线Bresenham算法思想之二：

　　由于像素坐标的整数性，数学点\((x_i,y_i)\)与所取像素点\((x_i,y_{ir})\)间会引起误差(\(\varepsilon_i\))，当\(x_i\)列上已用像素坐标\((x_i,y_{ir})\)表示直线上的点\((x_i,y_i)\)，下一直线点\(B(x_{i+1},y_{i+1})\)，是取像素点\(C(x_{i+1},y_{ir})\)，还是\(D(x_{i＋1},y_{(i+1)r})\)呢？

　　设\(A\)为\(CD\)边的中点，正确的选择：

　　若\(B\)点在\(A\)点上方，选择\(D\)点；否则，选\(C\)点。

　　用误差式描述为：

\[\varepsilon(x_{i+1})=BC-AC=(y_{i+1}-y_{ir})-0.5\qquad(2-8') \]

　　求递推公式：

\[\varepsilon(x_{i+2})=(y_{i+2}-y_{(i+1)r})-0.5 = y_{i+1}+m-y{(i+1)r}-0.5\qquad(2-9') \]

　　当\(ε(x_{i+1})\ge0\)时，选\(D\)点，\(y_{(i+1)r} = y_{ir}+1\)：

\[\varepsilon(x_{i+2})=y_{i+1}+m-y_{ir}-1-0.5=\varepsilon(x_{i+1})+m-1\qquad(2-10') \]

　　当\(ε(x_{i+1})<0\)时，选\(C\)点，\(y_{(i+1)r} = y_{ir}\)：

\[\varepsilon(x_{i+2})=y_{i+1}+m-y_{ir}-0.5=\varepsilon(x_{i+1})+m\qquad(2-11') \]

　　初始时：

\[\varepsilon(x_{s+1})=BC-AC=m-0.5\qquad(2-12') \]

　　为了运算中不含实型数，同时不影响不等式的判断，将方程两边同乘一正整数。

　　令方程两边同乘\(2\cdot\Delta x\)，即\(d=2\cdot\Delta x·ε\)，则：

　　初始时：

\[d=2\Delta y-\Delta x\qquad(2-13') \]

　　递推式：

当\(d\ge0\)时：

{
    d = d + 2(deltaY - deltaX);
    y++;
    x++;
}

否则：
```
{
    d = d + 2 * deltaY;
    x++; 
}
```

四、直线Bresenham算法实现

　条件：\(0≤m≤1\)且\(x_1<x_2\)

输入线段的两个端点坐标和画线颜色：\(x1,y1,x2,y2,color\)；
设置像素坐标初值：\(x=x_1,y=y_1\)；
设置初始误差判别值：\(p=2\cdot\Delta y-\Delta x\)；
分别计算：\(\Delta x=x_2-x_1, \Delta y=y_2-y_1\)；
循环实现直线的生成：

for (x = x1; x <= x2; x++) {
    putpixel(x, y, color);
    if (p >= 0) {
        y = y + 1;
        p = p + 2 * (deltaY - deltaX);
    } else {
        p = p + 2 * deltaY;
    }
}

五、直线Bresenham算法完善

　　现在我们修正\((2-16)\)公式，以适应对任何方向及任何斜率线段的绘制。如下图所示，线段的方向可分为八种，从原点出发射向八个区。由线段按图中所示的区域位置可决定xi+1和yi+1的变换规律。

　　容易证明：当线段处于①、④、⑧、⑤区时，以\(\mid\Delta x\mid\)和\(\mid\Delta y\mid\)代替前面公式中的\(\Delta x\)和\(\Delta y\)，当线段处于②、③、⑥、⑦区时，将公式中的\(\mid\Delta x\mid\)和\(\mid\Delta y\mid\)对换，则上述两公式仍有效

在线段起点区分线段方向

六、直线Bresenham算法特点

由于程序中不含实型数运算，因此速度快、效率高，是一种有效的画线算法。

七、直线Bresenham算法程序

void Bresenhamline(int x1, int y1, int x2, int y2, int color) {
	int x, y, dx, dy, s1, s2, p, temp, interchange, i;
	x = x1;
	y = y1;
	dx = abs(x2 - x1);
	dy = abs(y2 - y1);

	if (x2 > x1) {
		s1 = 1;
	} else {
		s1 = -1;
	}

	if (y2 > y1) {
		s2 = 1;
	} else {
		s2 = -1;
	}

	if (dy > dx) {
		temp = dx;
		dx = dy;
		dy = temp;
		interchange = 1;
	} else {
		interchange = 0;
	}

	p = 2 * dy - dx;
	for (i = 1; i <= dx; i++) {
		putpixel(x, y, color);
		if (p >= 0) {
			if (interchange == 0) {
				y = y + s2;
			} else {
				x = x + s1;
				p = p - 2 * dx;
			}
		}
		if (interchange == 0) {
			x = x + s1;
		} else {
			y = y + s2;
		}
		p = p + 2 * dy;
	}
}

#include <iostream>
#include <graphics.h>
using namespace std;
//中点画线法
void line1(int x1, int y1, int x2, int y2) {
    int x, y, d0, d1, d2, a, b;
    y = y1;
    a = y1 - y2;      //直线方程中的a的算法
    b = x2 - x1;      //直线方程中的b的算法
    d0 = 2 * a + b;   //增量初始值
    d1 = 2 * a;       //当>=0时的增量
    d2 = 2 * (a + b); //当<0时的增量
    for (x = x1; x <= x2; x++) {
        putpixel(x, y, GREEN); //打亮
        if (d0 < 0) {
            y++;
            d0 += d2;
        } else {
            d0 += d1;
        }
    }
}
//Bresenham画线算法
void line2(int x1, int y1, int x2, int y2) {
    int x, y, dx, dy, d;
    y = y1;
    dx = x2 - x1;
    dy = y2 - y1;
    d = 2 * dy - dx; //增量d的初始值
    for (x = x1; x <= x2; x++) {
        putpixel(x, y, GREEN); //打亮
        if (d < 0) {
            d += 2 * dy;
        } else {
            y++;
            d += 2 * dy - 2 * dx;
        }
    }
}
int main() {
    initgraph(640, 480);       //打开EGE初始化
    line1(200, 160, 400, 400); //画线
    getch();                   //等待用户操作
    closegraph();              //关闭图形
    return 0;
}