如何使用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.