画线算法解决的是数学上没有宽度大小的直线如何映射到像素矩阵中。数学上的直线是由没有大小的点必须映射到显示器的像素单位上。以像素为单位，则整个显示范围其实是一个整数区间。于是，一些数学计算出来的小数像素要具体落到哪些像素上，就需要这些个画线算法来决定。而其最基本最原始的方案就是就近原则。即理想点与哪个像素近就取那一个。怎么来找这个最近的像素，还要尽可能的快找到？如何评判快慢，计算机指令越少越简单就越快。请看下面最著名的三种算法。
选取基准变量，基准量每次增长一个像素，另一个要么不变，要么增长。不变还是增长取决于理想点的y到底离谁更近。所以有四舍五入法，也有中点判断法。求直线还得利用数学公式。说到底啊，还是在用计算机hack数学公式。
dda画线算法
这个算法hack的是斜截式直线方程 y = kx + b。根据斜率，分别算出固定的步进长度，然后逐步逼近终点，在x和y的确定上，使用的是四舍五入法。利用了计算机浮点数与整数的截断操作。这算是直接求点型。所以，这个算法是y=kx+b 公式加上四舍五入法。
void line_dda(struct point start, struct point end, struct color line_color, struct paint *painter)
{
int dx = end.x - start.x;
int dy = end.y - start.y;
int steps = abs(dx) >= abs(dy) ? abs(dx) : abs(dy);
float xi = (float)dx / steps;
float yi = (float)dy / steps;
float x = (float)start.x + 0.5; //加0.5是为了四舍五入
float y = (float)start.y + 0.5;
for(int i = 0; i <= steps; i++){
pixel((int)x, (int)y, line_color, painter);
x += xi;
y += yi;
}
}
midpoint画线算法
这个算法hack的是一般式直线方程 ax + by + c = 0。但他不直接利用该公式求x和y，而是根据像素排列规则（整数，矩形）来决定x和y是不变还是增加1。具体做法就是将待选的两个像素的中点代入方程做计算，结果只有三种，等于0，小于0，大于0。所以，这个算法是ax+by+c=0公式加上中点判断法。
if(d == 0)
// 两个备选点离理想点距离一样，随便取一个即可
else if(d < 0)
// 中点在理想点下面，即上面那个备选点离理想点更近，取之
else
// 中点在理想点上面，即下面那个备选点离理想点更近，取之
一般的教科书示例代码只描述了以x为基准量且终点位于起点的第一象限内的情况。还有其它7种情况。但都可以通过转换（x与y互换，起点与终点互换等等）来统一成上述算法。
void swap(int *a, int *b)
{
int t = *a;
*a = *b;
*b = t;
}
void line_midpoint(struct point start ,struct point end, struct color line_color, struct paint *painter)
{
int dx, dy, d, incry, incre, incrne, slope=0;
int x1 = start.x;
int y1 = start.y;
int x2 = end.x;
int y2 = end.y;
dx = abs(x1-x2);
dy = abs(y1-y2);
if(dy>dx){
swap(&x1, &y1);
swap(&x2, &y2);
swap(&dx, &dy);
slope = 1;
}
if(x1 > x2){
swap(&x1, &x2);
swap(&y1, &y2);
}
if(y1 > y2){ incry = -1; }
else{ incry = 1; }
d = 2*dy-dx;
incre = 2*dy;
incrne = 2*(dy-dx);
while(x1 <= x2){
if(slope){ pixel(y1, x1, line_color, painter); }
else{ pixel(x1, y1, line_color, painter); }
x1++;
if(d < 0){ d+= incre; }
else{ y1 += incry; d += incrne; }
}
}
Bresenham画线算法
这个算法其实是结合了前两种算法的思想，采用的是y=kx+b 公式加上中点判断法。
使用y=kx+b这个公式意味着如果x轴的增量是1，则y轴的增量就是斜率k，而最终y的确定就由k与中点确定。假设起点从原点出发且位于第一象限，设y轴偏移量为d，则初始d=0，之后d=d+k，如果d>0.5，说明离上面的点近，则y+1，d-1。对于偏移量d，可以理解成数学公式上算出来的y值与显示器上光栅化需要的y值之间的补偿值。简言之，y(理论) ＝ y(现实) + d。
void line_bresenham(struct point start, struct point end, struct color line_color, struct paint *painter)
{
int x1 = start.x;
int y1 = start.y;
int x2 = end.x;
int y2 = end.y;
int dx = abs(x1-x2);
int dy = abs(y1-y2);
int steps = dx>dy ? dx : dy;
int xi = x1 < x2 ? 1 : -1;
int yi = y1 < y2 ? 1 : -1;
int err = (dx>dy ? dx : -dy)>>1, e2;
for(int i = 0; i <= steps; i++){
pixel(x1, y1, line_color, painter);
e2 = err;
if(e2 > -dx){ err -= dy; x1 += xi; }
if(e2 < dy){ err += dx; y1 += yi; }
}
}
Bresenham画圆算法
同样的思想，数学公式＋求最近点。该算法采用的是x^2 + y^2 = r^2公式加上中点判定法求最近点。推理方式也是将两种最近点带入公式，得出步进偏移量。然后根据偏移量的符号来选择点。然后根据圆的八方向特性（对称），找到一个点之后，通过对称性，可直接得到另外7个点。
void plot(int cx, int cy, int x, int y, struct color pixel_color, struct paint * painter)
{
pixel(cx+x, cy+y, pixel_color, painter); pixel(cx+y, cy+x, pixel_color, painter);
pixel(cx-x, cy+y, pixel_color, painter); pixel(cx-y, cy+x, pixel_color, painter);
pixel(cx+x, cy-y, pixel_color, painter); pixel(cx+y, cy-x, pixel_color, painter);
pixel(cx-x, cy-y, pixel_color, painter); pixel(cx-y, cy-x, pixel_color, painter);
}
void circle(int cx, int cy, int radius, struct color circle_color, struct paint *painter)
{
int x = 0;
int y = radius;
int d = 1 - radius; /* 1.25 - r */
plot(cx, cy, x, y, circle_color, painter);
while(x <= y){
if(d<0){
d += 2*x+3;
}else{
d += 2*(x-y)+5;
--y;
}
++x;
plot(cx, cy, x, y, circle_color, painter);
}
}
总结
不谈实现，单说原理，所谓画线算法是计算机图形学的特殊算法，这玩意毫无科学价值，只是对现实物理现象（显示器上面的像素排列）的一种妥协。所以从根源上讲，这只是工程。
至于这几种画线算法，其基本原则是：1）正确的找到线条，2）合理的表示在显示器上。前者利用了画线数学公式，后者需要hack找出最优点，如四舍五入法，中点判定法。
以此推之，如果要寻求新的画线算法，方法就是实现上述两个原则，即使用一种线条公式确定理论线条，再辅以手段寻求最优值即可“发明”一种新的画线算法。
如下表所示：
| y=kx+b | ax+by+c=0 | … | |
|---|---|---|---|
| 四舍五入法 | dda 算法 | … | |
| 中点判定法 | bresenham 算法 | midpoint 算法 | … |
至于画圆算法，因为数学公式就这么一个，所以也玩不出什么花样，只能在求最近点上面做文章。当然也可以使用数值微分法（四舍五入法），直接解方程开平方求y的值，只是那样就太慢了，这里就没讨论了。另外，Bersenham画圆算法好像也叫中点画圆算法。