引言
给定两个点 A(x1, y1) 和 B(x2, y2) 的坐标，且满足 x1 < x2 和 y1 < y2。我们的任务是在由像素组成的计算机屏幕上找到绘制线段 AB 所需的所有中间点。请注意，每个像素都具有整数坐标。
我们之前已经讨论过针对此任务的以下算法：
在本文中，我们将探讨中点画线算法，这是对之前介绍的 Bresenham 算法的一种不同表示方式。
正如我们在上一篇文章中所讨论的，对于任何给定或已计算的上一个像素 P(Xp, Yp)，都有两个候选像素最接近该直线，它们是 E(Xp+1, Yp) 和 NE(Xp+1, Yp+1)（E 代表 East/东，NE 代表 North-East/东北）。
在中点算法中，我们执行以下操作：
- 找到两个可能的下一点的中点。E(Xp+1, Yp) 和 NE(Xp+1, Yp+1) 的中点是 M(Xp+1, Yp+1/2)。
- 如果 M 在直线上方，则选择 E 作为下一个点。
- 如果 M 在直线下方，则选择 NE 作为下一个点。
如何判断一个点是在直线上方还是下方？
为了保持算法的简洁性，我们做出以下假设：
- 我们从左向右画线。
- x1 < x2 且 y1 < y2。
- 直线的斜率在 0 到 1 之间。我们画一条从左下角到右上角的线。
除了上述假设之外的情况可以通过反射（对称）处理。
让我们考虑一条直线 y = mx + B。
我们可以将方程重写为：
y = (dy/dx)x + B 或者
(dy)x + B(dx) - y(dx) = 0
设 **F(x, y)** = (dy)x - y(dx) + B(dx) -----(1)
假设我们给定了一条直线的两个端点（基于上述假设）
-> 对于直线上的所有点
F(x, y) 的解为 0。
-> 对于直线上方的所有点，
F(x, y) 的结果为负数。
-> 对于直线下方的所有点，
F(x, y) 的结果为正数。
这种关系用于确定 M 的相对位置。
M = (Xp+1, Yp+1/2)
因此，我们的决策参数 d 为：
d = F(M) = F(Xp+1, Yp+1/2)
如何高效地从旧值计算 d 的新值？
为了简单起见，让我们将 F(x, y) 写成 ax + by + c 的形式。
其中 a = dy
b = -dx
c = B*dx
这些值我们从上面的方程 (1) 中获得。
情况 1： 如果选择了 E，那么对于下一个点：
dnew = F(Xp+2, Yp+1/2)
= a(Xp+2) + b(Yp+1/2) + c
dold = a(Xp+1) + b(Yp+1/2) + c
两个距离的差值（或增量）：
DELd = dnew – dold
= a(Xp+2)- a(Xp+1)+ b(Yp+1/2)- b(Yp+1/2)+ c-c
= a(Xp) +2a – a(Xp) – a
= a.
因此，dnew = dold + dy。（因为 a = dy）
情况 2： 如果选择了 NE，那么对于下一个点：
dnew = F(Xp+2, Yp+3/2)
= a(Xp+2) + b(Yp+3/2) + c
dold = a(Xp+1) + b(Yp+1/2) + c
两个距离的差值（或增量）：
DELd = dnew -dold
= a(Xp+2)- a(Xp+1)+ b(Yp+3/2)- b(Yp+1/2)+ c-c
= a(Xp) + 2a – a(Xp) – a + b(Yp) + 3/2b – b(Yp) -1/2b
= a + b
因此，dnew = dold + dy – dx。（因为 a = dy , b = -dx）
决策参数 d0 的初始值计算：
d0 = F(X1+1 , Y1+1/2)
= a(X1 + 1) + b(Y1 + 1/2) +c
= aX1+ bY1 + c + a + b/2
= F(X1,Y1) + a + b/2
= a + b/2 (因为 F(X1, Y1) = 0 )
d0 = dy – dx/2。（因为 a = dy, b = -dx）
输入 (X1,Y1) 和 (X2,Y2)
dy = Y2- Y1
dx = X2 - X1
// 决策参数 d 的初始值
if(dy<=dx){
d = dy - (dx/2)
x = X1 , y = Y1
// 绘制初始给定点
Plot(x , y)
// 遍历 X 的值
while(x < X2)
x = x+1
// 'E' 被选中
if (d < 0)
d = d + dy
// 'NE' 被选中
else
d = d + dy - dx
y = y+1
Plot(x,y)}
else if(dx<=dy)
{
d = dx - (dy/2)
x = X1 , y = Y1
// 绘制初始给定点
Plot(x , y)
// 遍历 Y 的值（注：原文此处逻辑是遍历斜率大于1的情况）
while(y< Y2)
y= y+1
// 'E' 被选中
if (d < 0)
d = d + dx
// 'NE' 被选中
else
d = d + dx - dy
x= x+1
Plot(x,y)
}
下面是上述思路的实现：
C++
“`
// C++ program for Mid-point line generation
#include
using namespace std;
// Header file for including graphics functions
// #include
// midPoint function for line generation
void midPoint(int X1, int Y1, int X2, int Y2)
{
// calculate dx & dy
int dx = X2 – X1;
int dy = Y2 – Y1;
if(dy<=dx){
// initial value of decision parameter d
int d = dy – (dx/2);
int x = X1, y = Y1;
// Plot initial given point
// putpixel(x,y) can be used to print pixel
// of line in graphics
cout << x << "," << y << "
";
// iterate through value of X
while (x < X2)
{
x++;
// E or East is chosen
if (d < 0)
d = d + dy