中点画线法根据直线的斜率(k)分为四种情况:[0,1)、[1,+∞)、[-1,0)、(-∞,-1)
首先输入直线的起点和终点,根据起点终点计算斜率:
假设两端点为:(x0,y0)、(x1,y1)
则直线方程为:(y-y1)/(y0-y1) = (x-x1)/(x0-x1)
转化为一般式:(y0 - y1)x +(x1 - x0)y + x0y1 - x1y0=0,则令a=y0-y1,b=x1-x0,c=x0y1-x1y0
则直线斜率:k=-a/b
先只考虑第一种情况(k∈[0,1)):
当F(xi+1,yi+0.5)>0时,点(xi+1,yi+0.5)在直线上方,点(xi+1,yi)距离直线更近,当F(xi+1,yi+0.5)=0时,x增加1,y不变,则d1=F(xi+2,yi+0.5)=a(xi+2)+b(yi+0.5)+c=d+a,d的增量为a
当d=0时,x增加1,y增加1,当d=0时,x增加1,y减少1,当d=0时,y减少1,x不变,当d>0时,x增加1,y减少1,增量为:
delta1=2*(-b)
delta2=2*(a-b)
c#语言的完整画线算法如下:
1 ///2 /// 中点画线算法 3 ///4 /// 起始点x坐标 5 /// 起始点y坐标 6 /// 终点x坐标 7 /// 终点y坐标 8 /// 画线的颜色 9 public void drawline(int x0, int y0, int x1, int y1, Color color) 10 { 11 //使用同一个bitmap时才可以获得相应的颜色12 //Bitmap bitmap = new Bitmap(500, 500); 13 int temp; 14 //将输入的两个顶点进行排序,可以从x小的一侧进行画线 15 if (x0 > x1) 16 { 17 temp = x0; 18 x0 = x1; 19 x1 = temp; 20 temp = y0; 21 y0 = y1; 22 y1 = temp; 23 } 24 int x, y; 25 float k, a, b, d, delta1, delta2; 26 a = y0 - y1; 27 b = x1 - x0; 28 k = -1 * a / b; 29 d = 2 * a + b; 30 //k∈[0,+∞) 31 if (k >= 0) 32 { 33 //k∈[0,1) 34 if (k < 1) 35 { 36 delta1 = 2 * a; 37 delta2 = 2 * (a + b); 38 x = x0; 39 y = y0; 40 if (x > 0 && y > 0 && x < 500 && y < 500) 41 { 42 bitmap.SetPixel(x, y, color); 43 } 44 while (x =0,选择正右方的像素填充 47 if (d >= 0) 48 { 49 x++; 50 d += delta1; 51 } 52 //d 0 && y > 0 && x < 500 && y < 500) 61 { 62 bitmap.SetPixel(x, y, color); 63 } 64 } 65 } 66 //k∈[1,+∞) 67 else 68 { 69 delta1 = 2 * b; 70 delta2 = 2 * (a + b); 71 x = x0; 72 y = y0; 73 if (x > 0 && y > 0 && x < 500 && y < 500) 74 { 75 bitmap.SetPixel(x, y, color); 76 } 77 while (x =0,选择右上方的像素进行填充 80 if (d >= 0) 81 { 82 x++; 83 y++; 84 d += delta2; 85 } 86 //d 0 && y > 0 && x < 500 && y < 500) 93 { 94 bitmap.SetPixel(x, y, color); 95 } 96 } 97 } 98 } 99 //k属于(-∞,0)100 else101 {102 //k∈[-1,0)103 if (k >= -1)104 {105 delta1 = 2 * a;106 delta2 = 2 * (a - b);107 x = x0;108 y = y0;109 if (x > 0 && y > 0 && x < 500 && y < 500)110 {111 bitmap.SetPixel(x, y, color);112 }113 while (x =0,选择右下方像素进行填充116 if (d >= 0)117 {118 x++;119 y--;120 d += delta2;121 }122 //d 0 && y > 0 && x < 500 && y < 500)129 {130 bitmap.SetPixel(x, y, color);131 }132 }133 }134 //斜率小于-1135 else136 {137 delta1 = 2 * (a - b);138 delta2 = 2 * (-b);139 x = x0;140 y = y0;141 if (x > 0 && y > 0 && x < 500 && y < 500)142 {143 bitmap.SetPixel(x, y, color);144 }145 while (x =0,选择正下方的像素进行填充148 if (d >= 0)149 {150 y--;151 d += delta2;152 }153 //d 0 && y > 0 && x < 500 && y < 500)161 {162 bitmap.SetPixel(x, y, color);163 }164 }165 }166 }167 //提供显示168 Graphics g = this.CreateGraphics();169 g.DrawImage(bitmap, new Rectangle(1, 1, 500, 500));170 }View Code*注:点(x0,y0)与点(x1,y1)的顺序不能反,如果交换顺序的话对应的x,y的加减逻辑会发生变化,在这里(x0,y0)是开始画线的起点,虽然交换二者的顺序不会导致直线方程的改变,但是会导致判别式增量的改变