2016-11-30 2 views
3

При рисовании строки с Bresenham line drawing algorithm, , где строка может не быть в пределах границ битового массива, записываемого в - было бы полезно скопировать результаты, чтобы они соответствовали границам, выровненным по оси изображения, на которое написано.Как использовать алгоритм рисования линии Bresenham с отсечением?

В то время как его можно сначала закрепить линию на прямоугольник, затем нарисуйте линию. Это не идеально, так как он часто дает немного другой наклон к линии (при условии, что используются внутренние координаты).

Поскольку это такая примитивная операция, существуют ли установленные методы для отсечения линии при сохранении одинаковой формы?

В случае, если это помогает, here is a reference implementation of the algorithm - он использует внутренние координаты, что позволяет избежать преобразования int/float при рисовании линии.


Я провел некоторое время, глядя на это:

+0

Отсечение не должны изменять наклон, если вы используете координаты с плавающей точкой. Вы ищете идеальный матч? –

+0

Я хотел бы иметь возможность использовать внутренние координаты, если это возможно, чтобы избежать много преобразования float/int, поскольку текущий код очень эффективен с помощью int coords. Я предполагаю, что документ по этой теме был выпущен, потому что просто использование float coords не так эффективно - добавлена ​​ссылка на ссылочный код в вопросе. – ideasman42

+0

Я прочитал первую и вторую ссылку на ссылки, и я должен признать, что немного запутался в том, что случилось с «дрянным» методом.Ваши границы выровнены по оси; координаты устанавливаемых пикселей изменяются монотонно; вы точно знаете, когда нужно переключаться с «не помещать пиксель» в «поместить пиксель» в «не помещать пиксель»; не знаю, где проблема – AakashM

ответ

1

Давайте реструктурировать проблему таким образом, мы можем видеть, как алгоритм 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.

Вот как мы можем сделать использование дополнительных обновлений привлечь часть той же самой линии от й = хза х = х:

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); 
} 
+0

Несмотря на то, что этот подход кажется правильным, я нашел реализацию из статьи Кузьмина и Евгения П, и ее довольно немного более активное участие, чем этот ответ, - хотя в основном он просто проверяет угловые случаи и учитывает обе оси. – ideasman42

+0

Извините @ ideaman42, это просто не так сложно. Ну, вам нужно найти xs и xe для вашего обрезающего прямоугольника - легко для границ x, но немного утончен для границ y из-за округления. если у вас есть проблемы с этим, дайте мне знать, и я покажу расчет. –

+0

Правильно, его не сложно вычислить значения spesific - однако я пытался получить обрезающие и не обрезающие версии, давая * точно * те же результаты для видимого сегмента линии. Оказывается, существует некоторая разница в методе, описанном в статье * Kuzmin & Евгений П. * (не связанный с отсечением). Я ошибался как ошибки в алгоритме, рассматривая наклоны несколько иначе - но, похоже, это не ошибка, а очень незначительная разница. Я отправил код как отдельный ответ. – ideasman42

1

алгоритм Bresenham можно использовать, принимая значения отсечения во внимание, основываясь на работе Кузьмин & Евгений P:

Для полноты, heres рабочая версия алгоритма, единственная функция 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, чтобы избежать дублирования кода.

Для испытаний и больше пример использования, см:

+0

Я преобразовал его в C, работает очень хорошо. Одно препятствие заключалось в понимании того, что «//» является целым делением, а не префиксом комментария;) + Kudos ideasman42! – Anonymous

+0

@Anonymous yw - обратите внимание, что int div в C будет по-разному основан на знаке. Отмечу в ответ – ideasman42

+0

OH! Питон привел меня на пол с этим! Благодаря! – Anonymous