中点画线法（Midpoint Line Algorithm）是一种画线（Line Drawing）算法，用来在计算机屏幕上绘制线条。

它的基本思想是从线段的起点和终点出发，按照一定的规则向终点逐步逼近，并在途中以控制变量的方式得出每个像素点的坐标，从而绘制出所需的线条。

具体实现中，中点画线法通过计算线段斜率的变化情况，来分为斜率小于1和大于等于1两种情况，并采用Bresenham的对称性原理，以中点的颜色来控制每个像素点的生长方向，从而获得较高的绘制效率和图像质量表现。

总的来说，中点画线法是一种高效且易于实现的线段绘制算法，也是计算机图形学领域最基本的算法之一。

当前像素点为 ( x p , y p ) (x_p,y_p) (xp​,yp​)，下一个像素点为 P 1 P1 P1或 P 2 P2 P2。 设 M = ( x p + 1 , y p + 0.5 ) M=(x_p+1,y_p+0.5) M=(xp​+1,yp​+0.5)为 P 1 P1 P1与 P 2 P2 P2之中点， Q Q Q为理想直线与 x = x p + 1 x=x_p+1 x=xp​+1垂线的交点。将 Q Q Q与 M M M的 y y y坐标进行比较。 当 M M M在 Q Q Q的下方，则 P 2 P2 P2应为下一个像素点；当 M M M在 Q Q Q的上方，则 P 1 P1 P1应为下一个像素点。

d = F ( M ) = F ( x p + 1 , y p + 0.5 ) = a ( x p + 1 ) + b ( y p + 0.5 ) + c d=F(M)=F(x_p+1,y_p+0.5)=a(x_p+1)+b(y_p+0.5)+c d=F(M)=F(xp​+1,yp​+0.5)=a(xp​+1)+b(yp​+0.5)+c 其中， a = y 0 − y 1 , b = x 1 − x 0 , c = x 0 y 1 − x 1 y 0 a=y_0-y_1, b=x_1-x_0, c=x_0y_1-x_1y_0 a=y0​−y1​,b=x1​−x0​,c=x0​y1​−x1​y0​.

若当前像素处于：

d ≥ 0 d\geq 0 d≥0情况，则取正右方像素 P 1 ( x p + 1 , y p ) P1(x_p+1, y_p) P1(xp​+1,yp​)，要判下一个像素位置，应计算 d 1 = F ( x p + 2 , y p + 0.5 ) = a ( x p + 2 ) + b ( y p + 0.5 ) = d + a d1=F(x_p+2, y_p+0.5)=a(x_p+2)+b(y_p+0.5)=d+a d1=F(xp​+2,yp​+0.5)=a(xp​+2)+b(yp​+0.5)=d+a 增量为 a a a。

d < 0 d 0 d>0，则中点 ( x , y m ) (x_, y_m) (x,​ym​)在 L ( Q ) L(Q) L(Q)的上方，此时应该取右边的像素点 P 1 ( x p + 1 , y p ) P1(x_p+1,y_p) P1(xp​+1,yp​)，即 x x x加1、 y y y不变。此时， d d d的值增加 d 1 d1 d1，即 d = d + d 1 d=d+d1 d=d+d1。

如果 d < 0 d0 d>0还是 d < 0 d < 0 d (1, 1) -> (2, 1) -> (3, 2) -> (4, 2) -> P1 (5, 2)

如下图：