当使用布雷森汉姆画线算法画线时， 如果线条可能不在要写入的位图的边界内 - 裁剪结果以使它们适合要写入的图像的轴对齐边界会很有用。
虽然可以先将线裁剪到矩形，然后绘制线条。这并不理想，因为它通常会给线提供略有不同的倾斜(假设正在使用 int 坐标)。
由于这是一个如此原始的操作，是否有既定的方法来剪切线，同时保持相同的形状？
如果它有帮助，这里是算法的参考实现 - 它使用 int 坐标，这避免了在绘制线条时进行 int/float 转换。
我花了一些时间研究这个：
- 问题在虚拟配音的网页上有详细的描述。
- 艾伦·蒂德曼的可能解决方案
...虽然我需要基于文本实现代码 - 看看它的效果如何。 - Bresenham的行生成算法与内置剪裁
(1995年的论文，找不到整个文档？- PDF是一个没有它引用的C代码的页面，看起来像它的付费墙)。
让我们重新构建问题，以便我们可以看到布雷森汉姆的算法是如何工作的......
假设您正在绘制一条从(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;
}
布雷森汉姆的算法只是一种在更新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);
}
可以使用Bresenham的算法，考虑剪切值，基于Kuzmin和Yevgeny P的论文：
为了完整起见，这里是该算法的工作版本，一个单一的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) - 整数除法
//无处不在。 - 许多语言(例如 C/C++)对除法使用下限舍入。
请参阅 C/C++ 中有符号整数除法的快速下限，以避免这些语言的结果略有偏差。
与本文提供的代码相比，有一些改进：
- 该线将始终沿定义的方向(从
p1到p2)绘制。 - 有时线梯度存在细微差异，因此旋转翻转点，计算线，然后变换回来 - 会给出略有不同的结果。这种不对称是由代码交换 X 轴和 Y 轴以避免代码重复引起的。
有关测试和更多示例用法，请参阅：
- Python 存储库。
- 锈蚀版本。