直线段的矢栅转换算法（DDA算法、中心画线算法、Bresenham算法）

以下为drawLine.cpp,分别对相应的原理进行了注释，只需调用相应的函数即可实现。

#include "drawLine.h" #include "setPixel.h" #include "cmath" void DDALine(int x0, int y0, int x1, int y1) { //DDA算法实现画直线 float x=x0,y=y0; float dx=x1-x0; float dy=y1-y0; float xadd,yadd; //定义x,y方向增量 int step; //定义总的步数 if(abs(dx)>abs(dy)){ //dx绝对值大于dy，则表明线斜率在1a,2a,3a,4a区域，此时x增加1或-1，y增加k或-k. step=abs(dx); //此时步数为x方向长度 float yadd=(float)dy/(float)step; float xadd=(x1 - x0) > 0 ? 1 : -1; //分别用dx,dy除步数得到x,y方向增量值 for(int i=0;i<=step;i++){ //利用总步数建立循环 setPixel(x,int(y+0.5)); //填充点 y=y+yadd; x=x+xadd; //x,y方向分别进行增加相应的分量 } } else{ //dy绝对值大于dx，斜率在1b,2b,3b,4b区间，此时交换x,y，并将步数用|dy|代替. step=abs(dy); yadd=(y1 - y0) > 0 ? 1 : -1; xadd=(float)dx/(float)step; for(int i=0;i<=step;++i){ setPixel(int(x+0.5),int(y)); y=y+yadd; x=x+xadd; } } } void swap_value(int &a,int &b){ //交换两个参数数值的函数 int temp=a; //temp为中间参数 a=b; b=temp; } void midpoint_line(int x0,int y0,int x1,int y1){ int a, b, d2, x, y, flag = 0; if (abs(x1 - x0) < abs(y1 - y0)) //如果|k|>1，则将两个点进行交换，并让flag为1. { swap_value(x0,y0); swap_value(x1,y1); flag = 1; //判断|k|值与1的关系，0到1时为0，>1时为1. } if (x0 > x1) { //保证x0<x1，则可以把画3，4区域线合并到1，2区域中。 swap_value(x0, x1); swap_value(y0, y1); } a = y0 - y1; b = x1 - x0; d2 = 2*a + b; //摆脱小数点，提高效率，d0=2a+b if (y0 < y1) { //k>0时，即画1a和3a区域,同时画出交换x,y过后在1a,3a区域的1b,3b区域. x = x0; y = y0; setPixel(x,y); //绘制点，先绘制x0,y0. while (x < x1) //直到绘制到x1终点截至，利用while循环绘制. { if(d2 < 0) //di小于0时，y增加，di增加2a+2b { x++; y++; d2 =d2+ 2*a + 2*b; } else { //di大于0时，y不变，di增加2a x++; d2 =d2+ 2 * a; } if(flag) //|k|>1,此时x,y已交换，绘制时需要交换x,y. setPixel(y, x); else setPixel(x, y); //0=<|k|<1,此时直接绘制相应点. } } else { //k<0,此时绘制4a和2a区域，同时画出交换x,y过后在2a,4a区域的2b,4b区域. x = x1; y = y1; setPixel(x, y); while (x >x0) { if (d2 < 0){ x--; y++; d2 = d2-2 * a + 2 * b; } else { x--; d2 =d2- 2 * a; } if (flag) //|k|>1，交换x,y，绘制 setPixel(y, x); else setPixel(x, y); } } } void Bresenham_line1(int x0,int y0,int x1,int y1){ //方法一，代码较长 int dx = x1 - x0; //x偏移量 int dy = y1 - y0; //y偏移量 int ux = dx >0 ? 1 : -1; //x伸展方向 int uy = dy >0 ? 1 : -1; //y伸展方向 int dx2 = abs(dx << 1); //x偏移量乘2 int dy2 = abs(dy << 1); //y偏移量乘2 if (abs(dx)>abs(dy)) //以x为增量方向计算 { int e = -dx; //e = -0.5 * 2 * dx,把e 用2 * dx* e替换 int x = x0;//起点x坐标 int y = y0;//起点y坐标 while (x!=x1+ux) { setPixel(x,y); e = e + dy2; //来自 2*e*dx= 2*e*dx + 2dy if (e > 0) //e是整数且大于0时表示要取右上的点（否则是右下的点） { if (y!=y1) { y += uy; } e = e - dx2;//2*e*dx = 2*e*dx - 2*dx } x += ux; } } else {//以y为增量方向计算 int e = -dy; //e = -0.5 * 2 * dy,把e 用2 * dy* e替换 int x = x0;//起点x坐标 int y = y0;//起点y坐标 while (y!=y1+uy) { setPixel(x,y); e = e + dx2;//来自 2*e*dy= 2*e*dy + 2dy if (e > 0)//e是整数且大于0时表示要取右上的点（否则是右下的点） { if (x!=x1) { x += ux; } e = e - dy2;//2*e*dy = 2*e*dy - 2*dy } y += uy; } } } void Bresenham_line(int x0,int y0,int x1,int y1 ){ //方法二，较简便 setPixel(x0,y0); int dx, dy; int flag=0; dx = abs(x1-x0); dy = abs(y1-y0); if (dx == 0 && dy == 0) //如果就x0,y0一个点，则绘制结束. return; if (dy > dx) //如果|k|>1，则将x,y值进行交换，同时令flag=1,做好标记 { flag = 1; swap_value(x0,y0); swap_value(x1,y1); swap_value(dx,dy); } int tx = (x1 - x0) > 0 ? 1 : -1; //判断位置关系确定步长正负 int ty = (y1 - y0) > 0 ? 1 : -1; int curx = x0 + 1; int cury = y0; //将第一个点作为初值赋予curx,cury变量 int dS = 2 * dy; int dT = 2 * (dy-dx); int d =dS-dx; while (curx != x1) //利用x进行循环 { if (d >= 0) { //根据d进行区分 d += dT; cury += ty; } else{ d += dS; } if (flag) //flag为1时，x,y需要进行交换. setPixel(cury,curx); else setPixel(curx, cury); curx+=tx; } } void draw_line(int x0, int y0, int x1, int y1) { //需要时调用相应的方法 DDALine(x0,y0,x1,y1); //midpoint_line(x0,y0,x1,y1); //Bresenham_line(x0,y0,x1,y1); //Bresenham_line1(x0,y0,x1,y1); //舍弃 }