中点算法直线画法

1. 直线方程F（x, y） = ax + by + c

　　直线经过两点 startPoint（X0， Y0）， endPoint（X）

　　其中：

　　a = Y0 - Y1；

　　b = X1 - X0;

　　c = X0Y1 - X1Y0;

　　且对于直线上的点：F（x, y） == 0

2. 取中点M带入方程 d = F（x+1， y + 0.5）判定d的符号：

　　如果 > 0,则M在直线上方，应该取正右边的点

　　如果 < 0, 则M在直线下方，应盖取右上方的点，

3. 采用增量计算，可以提高运行效率

　　(1)如果取正右方的P1点，则 d1 = F(xp+2, yp + 0.5) = d + a

　　　增量：deltD1 = a;

　　(2)如果取右上方的P2点，则 d2 = F(xp+2, yp + 1.5) = d + a + b

　　　增量：deltD2 = a + b;

4. d的初值，

　　d0 = F（x0+1, y0+0.5）= F(X0,Y0) + a + 0.5b ,且由于（X0， Y0）在直线上，所以f (x0,y0)= 0

　　所以：d0 = a + 0.5b;

5. 算法优化

　　（1）由于我们每次只是考虑d的符号，所以为了减少浮点运算，同时将上述相关变量扩大2倍，优化的方案是： a + a 取代直接的 a*2；

　　（2）这样，同样以步进增量地推判定后续位置，便于硬件提高计算效率，继而提高算法实现效率。

　　现在符号：

　　deltD1 = a + a;

　　deltD2 = a + a + b + b;

　　d0 = a + a + b；

　　或者：di+1 = di + deltD2 　　(di < 0, 右上方点)；

　　或者：di+1 = di + deltD1　　(di > 0，正右方点);

6. 算法实现如下；

　　算法评价：

　　因中点算法在推导递推项时，采用的是默认中点M在F(x,y)线上面或先下面，由于不同象限的下一个点的关系不一样，随意局限算法只能服务标准的第一象限，而在其他象限，则可以通过旋转等方法进行“转化”绘制。

 1 void CCGProjectWorkView::midPoint_Line(const int startPos[], const int endPos[], const float lineColor[])
 2 {
 3     //仅限于第一象限的绘制
 4     glPushMatrix();
 5     int a, b, deltA, deltB, distJunpFactor, pointX, pointY;
 6     a = startPos[1] - endPos[1];
 7     b = endPos[0] - startPos[0];
 8     distJunpFactor = a + a + b;//初值
 9     deltA = a + a;
10     deltB = a + a + b + b;
11     pointX = startPos[0];
12     pointY = startPos[1];
13 
14     glColor3f(lineColor[0], lineColor[1], lineColor[2]);
15     glBegin(GL_POINTS);
16         glVertex3f(pointX, pointY, 0);
17         int deltDisX = abs(endPos[0] - startPos[0]);
18         int i =0;
19         while (i < deltDisX)
20         {
21             if (distJunpFactor < 0)//符合左下闭合原则，即= 0， 取正右边位置
22             {
23                 pointX += 1;
24                 pointY += 1;
25                 distJunpFactor += deltB;
26             }
27             else
28             {
29                 pointX += 1;
30                 distJunpFactor += deltA;
31             }
32             glVertex3f(pointX, pointY, 0);
33             ++i;
34         }
35     glEnd();
36     glPopMatrix();
37 
38 }