Breaseman算法绘制直线算法公式推导|步骤|程序

　BreaseMan算法优点：

　　（1）不必计算直线的斜率，因此不用做除法；

　　（2）不用浮点数，只用整数；

　　（3）制作整数的加减乘除，和乘2操作，乘2操作可以直接用移位运算来处理；

　　（4）BresenMan算法的运算速度非常快。

明白了数学原理，我们很快能确定算法步骤：

1. 输入线段的起点和终点。

2. 判断线段的斜率是否存在（即起点和终点的x坐标是否相同），若相同，即斜率不存在，
只需计算y方向的单位步进（△Y+1次），x方向的坐标保持不变即可绘制直线。

3. 计算线段的斜率k，分为下面几种情况处理
　　a. k等于0，即线段平行于x轴，即程序只需计算x方向的单位步进，y方向的值不变

　　b. |k|等于1，即线段的x方向的单位步进和y方向的单位步进一样，皆为1。直接循环△X次计算x和y坐标。

4. 根据输入的起点和终点的x、y坐标值的大小决定x方向和y方向的单位步进是1还是-1
5. 画出第一个点。

7. 若|k| <1，设m =0,计算P0，如果Pm>0，下一个要绘制的点为（Xm+单位步进，Ym），
　　Pm+1 = Pm -2*△Y;
　　否则要绘制的点为（Xm+单位步进，Ym+单位步进）
　　Pm+1 = Pm+2*△X-2*△Y；

8. 重复执行第七步△X-1次；

9. 若|k| >1，设m =0,计算Q0，如果Qm>0，下一个要绘制的点为（Xm，Ym+单位步进），
　　Pm+1 = Pm -2*△X;
　　否则要绘制的点为（Xm+单位步进，Ym+单位步进）
　　Pm+1 = Pm+2*△Y-2*△X；

10. 重复执行第9步△Y-1次；

算法实现步骤二：

　　在算法实现之前，由上述的分析，则需要考虑的问题如下：

　　（1）因为BresenHam算法不考虑斜率，只需要考虑：选择X或者Y作为步进坐标轴，通过|delatX| 与|deltY|的比较获得；

　　即，如果|delatX| >= |deltY|，则选择X轴作步进坐标轴，反之，则选择Y作为坐标轴；

　　（2）步进轴的递进方向问题： deltY = endY - startY； deltX = endX - startY；通过比较 deltY，与deltX的符号获取；

　　即，如果endX >= startX , 则 X作为步进坐标轴步进为 +1，否则为 -1；

　　同理： endY >= startY , 则Y作为步进坐标轴步进为： +1，否则为-1；

　　（3）因为不考虑斜率是否大于1，所以，我们选择“deltX”与deltY之间最大的作为步进边，即所在的坐标轴作为步进坐标轴；

　　即，在程序中，将变化最大的作为步进坐标轴，同时，要添加标记isInterchange，如果变化设置为true，然后在考虑Y_m+1的步进坐标的变化，即Xm+1的取舍X_m 或者X_m +/- 1；

　　（4）以下的程序实现，是以前面介绍的算法推导为基础，需要注意的是，因为此实现算法的步进迭代过程，与步进坐标轴是分开的，所以：如果下一个坐标的“不是步进坐标轴”的坐标轴变量只需要同时在绘制点时之前进行修改，而在修改步进坐标轴变量是不需要绘制“点”。

参考：

　　前面的博客：http://www.cnblogs.com/icmzn/p/5043365.html

　（转载请注明出处：http://www.cnblogs.com/icmzn/p/5043436.html）

　　晚上的东西不能轻易相信，之前从网上download下一个程序，尼玛，程序是错误的，花了整个一个上午来修改这个程序，所以对待网上的东西不要轻易相信，要有批判的思维。

　　下面是我亲自调试通过后的程序：

　　（1）考虑了步进坐标轴的选取问题，以及其他问题。

 1 void CCGProjectWorkView::bresenHam_Line(const int startPos[], const int endPos[], const float lineColor[])
 2 {
 3     glPushMatrix();
 4     //绘制直线
 5     float x, y, deltX, deltY, jugeFacor, temp;
 6     //BresenMan算法实现
 7     //起始点
 8     x = startPos[0];
 9     y = startPos[1];
10     //x或y方向的delt值
11     deltX = abs(endPos[0] - startPos[0]);
12     deltY = abs(endPos[1] - startPos[1]);
13     int sX, sY;//判定是否步进的方向
14     bool isInterchange = false;//斜率问题,xy是否需要交换绘制
15     if ((endPos[0] - startPos[0]) >= 0)//判定x方向的前后，
16         sX = 1;
17     else
18         sX = -1;//X反向递进
19     if ((endPos[1] - startPos[1]) >= 0)
20         sY = 1;
21     else
22         sY = -1;//Y反向递进
23     //根据斜率处理,deltX始终保持最大的数据
24     if (deltY > deltX)
25     {
26         temp = deltX;
27         deltX = deltY;
28         deltY = temp;
29         isInterchange = true;
30     }
31     //判定是Dupper - Dbotton ,所以符号 JugePactor < 0 ,取右上，> 0, 取右边，相对来说
32     jugeFacor = deltX - 2*deltY;//判定项，决定下一个坐标的取值问题
33     glColor3f(lineColor[0], lineColor[1], lineColor[2]);
34     glBegin(GL_POINTS);
35     glVertex3f(x, y, 0);//在xoy平面绘制
36     for (int i= 0; i < deltX; i++)
37     {
38         if (jugeFacor < 0)//只能取top，且符合左下闭合原则，即=0时，取下面位置
39         {//取右上位置（相对而言）
40                 x += sX;
41                 y += sY;
42             glVertex3f(x, y, 0);//绘制此点
43             jugeFacor = jugeFacor + 2*deltX - 2*deltY;
44         } 
45         else
46         {//取botton, 取右边位置（相对而言），则只需要修改“步进”坐标轴变量
47             if (isInterchange)//xy斜率需要处理化，以y为单位步进方向
48                 y += sY;
49             else
50                 x += sX;
51             glVertex3f(x, y, 0);//绘制此点
52             jugeFacor = jugeFacor - 2*deltY;
53 
54         }
55         if (i == deltX-1 )
56         {
57             int stop = 0;
58         }
59     }
60     glEnd();
61     glPopMatrix();
62 }