DDA（digital differential analyzer）
由直线的斜截式方程引入
对于正斜率的线段，如果斜率<=1，则以单位x间隔(δx=1)取样，并逐个计算每一个y值
Y= Y+ m （m为由初始点确定的斜率）
对于斜率>1的线段
X= X+ 1/m （m为由初始点确定的斜率）
起始端点在于右侧时 ”+” -> ”-”
#include "stdlib.h"
#include "math.h"
inline int round(const float a){return int (a + 0.5);}
//实现算数取整
void lineDDA(int x0, int y0, int xEnd, int yEnd)
{
int dx = xEnd - x0, dy = yEnd - y0, steps, k;
float xIncrement, yIncrement, x = (float)x0, y = (float)y0;
if(fabs(dx)>fabs(dy))
{
steps = fabs(dx);
}
else
{
steps = fabs(dy);
}
//比较斜率
xIncrement = float(dx)/float(steps);
yIncrement = float(dy)/float(steps);
setpixel(round(x),round(y));
for(k=;k<steps;k++)
{
x += xIncrement;
y += yIncrement;
setpixel(round(x),round(y));
}
//增量绘图
}
Bresenham 画线算法
Bresenham算法通过计算下一个理论点与其相邻栅格的距离构造了决策参数，而后利用决策参数进行递推绘点。
dlower = y - yk = m(xk+1)+b - yk
dupper = (yk+1) - y = yk + 1 – m(xk+1)-b
决策参数p = △x(dlower - dupper) = 2△y*xk - 2△x*yk + c
|m|<1时的Bresenham画线算法为：
- 输入线段的两个端点，并将左端点储存在(x0,y0)中
- 将(x0,y0)装入帧缓存，画出第一个点；
- 计算常量△x, △有，△2y和2△y-2△x，并得到决策参数的第一个值：
P0 = 2△y - △x
4.从k = 0开始，在沿线段路径的每个xk处，进行下列检测：
如果pk<0,下一个要绘制的点是(xk+1，yk)，并且
pk+1 = pk+2△y
否则，下一个要绘制的点是(xk+1，yk+1)，并且
pk+1 = pk+2△y-2△x
5.重复步骤4，△x-1次
#include<stdlib.h>
#include<math.h> /*|m|<1.0时候的bresenham算法*/ void lineBres(int x0, int y0, int xEnd, int yEnd)
{
int dx = fabs(xEnd - x0), dy = fabs(yEnd - y0);
int p = * dy - dx;
int twoDy = * dy, twoDyminusDx = * (dy - dx);
int x, y; /*根据斜率正负决定起始点和终结点*/
if (x0 > xEnd)
{
x = xEnd;
y = yEnd;
xEnd = x0;
}
else
{
x = x0;
y = y0;
}
setPixel(x, y); while (x < xEnd)
{
x++;
if (p < )
p += twoDy;
else
{
y++; p += twoDyMinusDx;
}
setPixel(x, y)
}
}