Алгоритм Брезенхема

Уравнение прямой на плоскости

Напомним, что прямая на плоскости — это множество всевозможных точек, координаты \(x,y\) которых удовлетворяют уравнению вида

\[Ax+By+C=0\]

для каких-то \(A,B,C\) (\(A\) и \(B\) не должны быть одновременно равны нулю).

У этого уравнения есть очень простой геометрический смысл. Пусть \(X,Y\) — произвольная точка прямой. Тогда \(C=-AX-BY\). Поэтому уравнение можно переписать в виде

\[A(x-X)+B(y-Y)=0\]

Слева (в предположении ортонормированности системы координат) — скалярное произведение вектора с координатами \(A,B\) и направляющего вектора прямой. Равенство скалярного произведения нулю — перпендикулярность. То есть уравнение прямой дословно говорит о том, что прямая — множество всех точек, радиус-вектор которых (относительно некоторой фиксированной точки) перпендикулярен некоторому фиксированному вектору.

Коэффициенты \(A\) и \(B\) легко вычислить, если знать координаты каких-нибудь двух точек на прямой. Если прямая проходит через точки \(x_0,y_0\) и \(x_1,y_1\), то можно взять

\[ A = y_1 - y_0;\qquad B = x_0 - x_1 \]

или любые другие числа, пропорциональные этой паре.

Изображение прямой

Для того, чтобы изобразить прямую на растровом изображении, нужно пометить все пиксели, достаточно близкие к этой прямой (из-за того, что растровое изображение представляет собой целочисленную решётку, уравнению прямой точно удовлетворяет довольно мало пикселей).

В качестве критерия близости пикселя к прямой можно использовать результат его подстановки в левую часть рассмотренного выше уравнения прямой: этот результат является (если вспомнить геометрический смысл скалярного произведения) расстоянием от пикселя до прямой (нормированным величиной \(\sqrt{A^2+B^2}\)).

Именно такой критерий использует алгоритм Брезенхема, строящий отрезок между парой заданных точек. Этот алгоритм (точнее, одну из многочисленных его вариаций) можно грубо описать так:

1. Выбираем два перпендикулярных напраления, направленных от начальной точки отрезка в сторону конечной. Например, вправо и вверх.
2. Закрашиваем начальный пиксель.
3. Создаём переменную, хранящую значение левой части уравнения для текущего пикселя. Её начальное значение — ноль.
4. Пока мы не попали в конечную точку, делаем шаг в одном из выбранных в пункте 1 направлений в зависимости от знака переменной из пункта 3 (или её близости к нулю). Соответствующим образом обновляем эту переменную и красим текущий пиксель.

Основное достоинство этого алгоритма — он вообще не использует никакой арифметики, кроме сложения и сравнения с нулём.

Приведём две различных реализации этого алгоритма. Первая реализация работает при условии того, что конечная точка строго правее начальной и не ниже её.

def mark_pixel(image, x, y):
    put_pixel(image, x, y, 255, 255, 255)

def draw_line(image, x0, y0, x1, y1):
    y = y0
    error = 0
    A = y1-y0
    B = x0-x1

    for x in range(x0, x1+1):
        mark_pixel(image, x, y)
        
        while error > 0:
            y += 1
            error += B
            mark_pixel(image, x, y)
        
        x += 1
        error += A
    
    mark_pixel(image, x, y)

Вторая реализация более полноценна и работает всегда:

def sign(x):
    if x > 0: return 1
    if x < 0: return -1
    return 0

def draw_line(image, x0, y0, x1, y1):
    x,y = x0,y0
    error = 0
    
    A = y1-y0
    B = x0-x1
    dx, dy = -sign(B), sign(A)

    while x != x1 or y != y1:
        mark_pixel(image, x, y)

        ex = error + A*dx
        ey = error + B*dy

        if abs(ex) < abs(ey):
            x    += dx
            error = ex
        else:
            y    += dy
            error = ey

    mark_pixel(image, x, y)