클리핑과 함께 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

당신이 방법은 주로 수직에 대해 동일합니다 (주로 수평선을 그리는 말할 수 있습니다 ... 우리가 Bresenham의 알고리즘이 실제로 어떻게 작동하는지 볼 수 있도록의 문제를 재구성하자,하지만 축으로 전환) (x0,y0)(x1,y1) 내지 :

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

,536,913 :

전체 라인 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; 
} 

Bresenham의 알고리즘은 당신이 x을 업데이트 할 때 점진적으로이 수식 결과를 업데이트하기 위해 단지 빠른 방법입니다.여기

우리가 증분 업데이트의 사용은 X = XE에 X = XS에서 매우 동일한 라인의 부분을 그릴 수 있도록하는 방법은 다음과 같습니다

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으로부터 나머지 비교를 수행하려는 경우

, 당신 단지 처음에 상쇄 할 수

Bresenham 알고리즘이 사용될 수있다

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.