如何使用Bresenham的线条绘制算法进行裁剪？

Question

当使用Bresenham line drawing algorithm, 画线时，行可能不在要写入的位图范围内 - 剪切结果以便它们适合要写入的图像的轴对齐边界将很有用。

尽管可能首先将线条剪切为矩形，然后绘制线条。这是不理想的，因为它往往会给线（假设使用int coords）略有不同。

由于这是一个如此简单的操作，是否已经建立了在保持相同形状的同时剪切线的方法？

如果有帮助，here is a reference implementation of the algorithm - 它使用int坐标，避免int/float转换，同时画线。

---

我花了一些时间寻找到这一点：

• 问题进行了详细的描述virtual-dub's web page。
• Possible solution from Alan Tiedemann
  ...虽然我需要基于文本实现代码 - 看看它的工作效果如何。
• Bresenham's Line Generation Algorithm with Built-in Clipping
  （从1995年开始的纸张，找不到整个文档？ - PDF是一个单独的页面，没有它引用的C代码，看起来像它的付费墙）。

Answer 1

让我们重新定义这个问题，所以我们可以看到布氏算法真正起作用...

比方说你是画一个主要水平线（该方法对于大部分垂直相同，但与轴切换）从(x0,y0)到(x1,y1)：

y = y0 + round((x-x0) * (y1-y0)/(x1-x0)) 

：

实线可以在x术语（所有整数）被描述为y的函数

这描述了绘制完整线时要绘制的每个像素，并且当您一致地剪切线时，它仍会精确地描述每个像素 - 您只需将其应用于较小范围的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); 
} 

Answer 2

布氏算法可以使用，以基于由库兹明&叶夫根尼·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++）都使用分区舍入。
  请参阅Fast floor of a signed integer division in C/C++以避免对这些语言产生稍微偏差的结果。

有超过在纸张提供的代码一些改进：

• 该生产线将总是在定义（从p1到p2）方向画出。
• 线条渐变有时会有细微的差异，所以旋转点，计算线条，然后变形 - 会产生稍微不同的结果。不对称是由代码交换X轴和Y轴引起的，以避免代码重复。

---

对于测试和更多的使用例子，请参阅：

• The Python repository。如果使用浮点坐标
• Rust version.