Как использовать алгоритм рисования линий Брезенхема с отсечением?

Давайте переформулируем задачу, чтобы увидеть, как на самом деле работает алгоритм Брезенхема...

Допустим, вы рисуете в основном горизонтальную линию (метод тот же, что и для большей части вертикальной, но с переключением осей) от (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);
}

Можно использовать алгоритм Брезенхема с учетом значений отсечения на основе статьи Кузьмина и Евгения П.:

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