当使用Bresenham line drawing algorithm绘制一条线时，该线可能不在正在写入的位图的范围内 - 剪辑结果以使其适合正在写入的图像的轴对齐范围内是有用的。
虽然可以先将线条剪裁到矩形，然后再绘制线条。这并不理想，因为它经常给线带来稍微不同的倾斜（假设正在使用 int 坐标）。
既然这是一个原始的操作，是否有既定的方法可以在保持相同形状的同时剪断线条？
如果有帮助，这里是该算法的参考实现- 它使用 int coords，避免在绘制线条时进行 int/float 转换。
我花了一些时间研究这个：
让我们重新构建问题，这样我们就可以看到 Bresenham 的算法是如何真正起作用的......
假设您正在绘制一条大部分水平的线（对于大部分垂直的方法是相同的，但轴已切换）从(x0,y0)到(x1,y1)：
整行可以描述为（所有整数）的y函数x：
y = y0 + round( (x-x0) * (y1-y0) / (x1-x0) )
这准确地描述了您在绘制整条线时将绘制的每个像素，并且当您一致地剪切线时，它仍然准确地描述了您将绘制的每个像素——您只需将其应用于较小范围的x值。
我们可以通过分别计算除数和余数来使用所有整数数学来评估这个函数。对于x1 >= x0和y1 >= y0（否则进行正常转换）：
let dx = (x1-x0);
let dy = (y1-y0);
let remlimit = (dx+1)/2; //round up
rem = (x-x0) * dy % dx;
y = y0 + (x-x0) * dy / dx;
if (rem >= remlimit)
{
rem-=dx;
y+=1;
}
Bresenham 的算法是一种快速的方法，可以在您更新时逐步更新此公式的结果x。
下面是我们如何利用增量更新来绘制从 x=xs 到 x=xe 的同一行的部分：
let dx = (x1-x0);
let dy = (y1-y0);
let remlimit = (dx+1)/2; //round up
x=xs;
rem = (x-x0) * dy % dx;
y = y0 + (x-x0) * dy / dx;
if (rem >= remlimit)
{
rem-=dx;
y+=1;
}
paint(x,y);
while(x < xe)
{
x+=1;
rem+=dy;
if (rem >= remlimit)
{
rem-=dx;
y+=1;
}
paint(x,y);
}
如果您想对 0 进行余数比较，则可以在开头偏移它：
let dx = (x1-x0);
let dy = (y1-y0);
let remlimit = (dx+1)/2; //round up
x=xs;
rem = ( (x-x0) * dy % dx ) - remlimit;
y = y0 + (x-x0) * dy / dx;
if (rem >= 0)
{
rem-=dx;
y+=1;
}
paint(x,y);
while(x < xe)
{
x+=1;
rem+=dy;
if (rem >= 0)
{
rem-=dx;
y+=1;
}
paint(x,y);
}
根据 Kuzmin & Yevgeny P 的论文，可以使用 Bresenham 的算法，考虑到裁剪值：
为了完整起见，这里是该算法的一个工作版本，一个 Python 函数，虽然它只使用整数算术 - 所以可以很容易地移植到其他语言。
def plot_line_v2v2i(
p1, p2, callback,
clip_xmin, clip_ymin,
clip_xmax, clip_ymax,
):
x1, y1 = p1
x2, y2 = p2
del p1, p2
# Vertical line
if x1 == x2:
if x1 < clip_xmin or x1 > clip_xmax:
return
if y1 <= y2:
if y2 < clip_ymin or y1 > clip_ymax:
return
y1 = max(y1, clip_ymin)
y2 = min(y2, clip_ymax)
for y in range(y1, y2 + 1):
callback(x1, y)
else:
if y1 < clip_ymin or y2 > clip_ymax:
return
y2 = max(y2, clip_ymin)
y1 = min(y1, clip_ymax)
for y in range(y1, y2 - 1, -1):
callback(x1, y)
return
# Horizontal line
if y1 == y2:
if y1 < clip_ymin or y1 > clip_ymax:
return
if x1 <= x2:
if x2 < clip_xmin or x1 > clip_xmax:
return
x1 = max(x1, clip_xmin)
x2 = min(x2, clip_xmax)
for x in range(x1, x2 + 1):
callback(x, y1)
else:
if x1 < clip_xmin or x2 > clip_xmax:
return
x2 = max(x2, clip_xmin)
x1 = min(x1, clip_xmax)
for x in range(x1, x2 - 1, -1):
callback(x, y1)
return
# Now simple cases are handled, perform clipping checks.
if x1 < x2:
if x1 > clip_xmax or x2 < clip_xmin:
return
sign_x = 1
else:
if x2 > clip_xmax or x1 < clip_xmin:
return
sign_x = -1
# Invert sign, invert again right before plotting.
x1 = -x1
x2 = -x2
clip_xmin, clip_xmax = -clip_xmax, -clip_xmin
if y1 < y2:
if y1 > clip_ymax or y2 < clip_ymin:
return
sign_y = 1
else:
if y2 > clip_ymax or y1 < clip_ymin:
return
sign_y = -1
# Invert sign, invert again right before plotting.
y1 = -y1
y2 = -y2
clip_ymin, clip_ymax = -clip_ymax, -clip_ymin
delta_x = x2 - x1
delta_y = y2 - y1
delta_x_step = 2 * delta_x
delta_y_step = 2 * delta_y
# Plotting values
x_pos = x1
y_pos = y1
if delta_x >= delta_y:
error = delta_y_step - delta_x
set_exit = False
# Line starts below the clip window.
if y1 < clip_ymin:
temp = (2 * (clip_ymin - y1) - 1) * delta_x
msd = temp // delta_y_step
x_pos += msd
# Line misses the clip window entirely.
if x_pos > clip_xmax:
return
# Line starts.
if x_pos >= clip_xmin:
rem = temp - msd * delta_y_step
y_pos = clip_ymin
error -= rem + delta_x
if rem > 0:
x_pos += 1
error += delta_y_step
set_exit = True
# Line starts left of the clip window.
if not set_exit and x1 < clip_xmin:
temp = delta_y_step * (clip_xmin - x1)
msd = temp // delta_x_step
y_pos += msd
rem = temp % delta_x_step
# Line misses clip window entirely.
if y_pos > clip_ymax or (y_pos == clip_ymax and rem >= delta_x):
return
x_pos = clip_xmin
error += rem
if rem >= delta_x:
y_pos += 1
error -= delta_x_step
x_pos_end = x2
if y2 > clip_ymax:
temp = delta_x_step * (clip_ymax - y1) + delta_x
msd = temp // delta_y_step
x_pos_end = x1 + msd
if (temp - msd * delta_y_step) == 0:
x_pos_end -= 1
x_pos_end = min(x_pos_end, clip_xmax) + 1
if sign_y == -1:
y_pos = -y_pos
if sign_x == -1:
x_pos = -x_pos
x_pos_end = -x_pos_end
delta_x_step -= delta_y_step
while x_pos != x_pos_end:
callback(x_pos, y_pos)
if error >= 0:
y_pos += sign_y
error -= delta_x_step
else:
error += delta_y_step
x_pos += sign_x
else:
# Line is steep '/' (delta_x < delta_y).
# Same as previous block of code with swapped x/y axis.
error = delta_x_step - delta_y
set_exit = False
# Line starts left of the clip window.
if x1 < clip_xmin:
temp = (2 * (clip_xmin - x1) - 1) * delta_y
msd = temp // delta_x_step
y_pos += msd
# Line misses the clip window entirely.
if y_pos > clip_ymax:
return
# Line starts.
if y_pos >= clip_ymin:
rem = temp - msd * delta_x_step
x_pos = clip_xmin
error -= rem + delta_y
if rem > 0:
y_pos += 1
error += delta_x_step
set_exit = True
# Line starts below the clip window.
if not set_exit and y1 < clip_ymin:
temp = delta_x_step * (clip_ymin - y1)
msd = temp // delta_y_step
x_pos += msd
rem = temp % delta_y_step
# Line misses clip window entirely.
if x_pos > clip_xmax or (x_pos == clip_xmax and rem >= delta_y):
return
y_pos = clip_ymin
error += rem
if rem >= delta_y:
x_pos += 1
error -= delta_y_step
y_pos_end = y2
if x2 > clip_xmax:
temp = delta_y_step * (clip_xmax - x1) + delta_y
msd = temp // delta_x_step
y_pos_end = y1 + msd
if (temp - msd * delta_x_step) == 0:
y_pos_end -= 1
y_pos_end = min(y_pos_end, clip_ymax) + 1
if sign_x == -1:
x_pos = -x_pos
if sign_y == -1:
y_pos = -y_pos
y_pos_end = -y_pos_end
delta_y_step -= delta_x_step
while y_pos != y_pos_end:
callback(x_pos, y_pos)
if error >= 0:
x_pos += sign_x
error -= delta_y_step
else:
error += delta_x_step
y_pos += sign_y
示例使用：
plot_line_v2v2i(
# two points
(10, 2),
(90, 88),
# callback
lambda x, y: print(x, y),
# xy min
25, 25,
# xy max
75, 75,
)
笔记：
image_width - 1, image_height - 1）// 无处不在。论文中提供的代码有一些改进：
p1到p2）。有关测试和更多示例用法，请参阅：