Алгоритм Брезенхема (англ. Bresenham's line algorithm) — это алгоритм, определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками. Это один из старейших алгоритмов в машинной графике — он был разработан Джеком Е. Брезенхемом (Jack E. Bresenham) в компании IBM в 1962 году. Алгоритм широко используется, в частности, для рисования линий на экране компьютера.

В алгоритме используется управляющая переменная $d_i$, которая на каждом шаге пропорциональна разности между $s$ и $t$ (см. рис.1). На рисунке 1 приведен i-ый шаг, когда пиксель $P_{i-1}$ уже найден как ближайший к реальному изображаемому отрезку, и теперь требуется определить, какой из пикселей должен быть установлен следующим: $T_i$ или $S_i$.

Если $s < t$, то $S_i$ ближе к отрезку и необходимо выбрать его; в противном случае ближе находится $T_i$. Другими словами, если $s - t < 0$, то выбирается $S_i$; иначе выбирается $T_i$.

Отрезок в примере (на рис.1) проводится из точки $(x_1, y_1)$ в точку $(x_2, y_2)$. Пусть первая точка находится ближе к началу координат, тогда вычтем из соответствующих координат $x_1$ и $y_1$ тем самым перенеся первую точку в начало координат, тогда конечная окажется в $(Δx, Δy)$, где $Δx = x_2 - x_1$, $Δy = y_2 - y_1$. Уравнение прямой теперь имеет вид $y = x\frac{Δy}{Δx}$. В рассматриваемом примере предполагается, что $Δx >= Δy$ и $Δy >= 0$.

Из рисунка 1 следует, что

$$s = \frac{Δy}{Δx}(x + 1) - y, \\
t = y + 1 - \frac{Δy}{Δx}(x + 1)$$

поэтому

$$s - t = 2 \frac{Δy}{Δx}(x + 1) - 2y - 1$$

Домножим обе части равенства на Δx:

$$Δx(s - t) = 2(Δy\cdot x - y\cdot Δx) + 2Δy - Δx$$

Так как $Δx > 0$, то величину $Δx(s-t)$ можно использовать в качестве критерия для выбора пикселя. Обозначим эту величину $d_i$:

$$d_i = 2(Δy\cdot x_{i-1} - y_{i-1}\cdot Δx) + 2Δy - Δx$$

Так как $d_i$ надо считать на каждом шаге, рассчитаем величину $Δ_i$ — приращения $d_i$:

$$Δ_i = d_i - d_{i-1} = 2Δy(x_i - x_{i-1}) - 2Δx(y_i - y_{i-1})$$

Известно, что $x_i – x_{i-1} = 1$.

Если $d_i >= 0$, то выбираем $T_i$, т.е. $y_i — y_{i-1} = 1$ (перемещаем точку по y), а $Δ_i$ тогда равно

$$Δ_i = 2(Δy - Δx)$$

Если $d_i < 0$, то выбираем $S_i$, т.е. $y_i — y_{i-1} = 0$ (у не меняется), тогда $Δ_i = 2Δy$.

Таким образом, мы получили итеративную формулу для вычисления критерия d_i.

Начальное значение $d_1 = 2Δy - Δx$.

Важно учитывать, что такой алгоритм требует определения ещё одного параметра — значения, определяющего изменение y_i. В примере мы предполагали $Δy >= 0$, а потому при перемещении точки изменяли значение на +1. Если значение $Δy < 0$, то изменение происходит на -1.

Аналогично рассматривается случай, когда $Δx < Δy$. Алгоритм Брезенхэма в своей реализации требует учёт всех возможных ситуаций взаимного расположения точек.

Код алгоритма Брезенхемма построения линии на JavaScript:

function drawLine(x1, y1, x2, y2) {
    var deltaX = Math.abs(x2 - x1);
    var deltaY = Math.abs(y2 - y1);
    var signX = x1 < x2 ? 1 : -1;
    var signY = y1 < y2 ? 1 : -1;
    var d = deltaX - deltaY;
    plot(x2, y2); // Ставим точку собственной функцией, т.к. JS не имеет оператора точки
    while(x1 != x2 || y1 != y2) 
    {
        plot(x1, y1);
        var d2 = d * 2;
        if(d2 > -deltaY) 
        {
            d -= deltaY;
            x1 += signX;
        }
        if(d2 < deltaX) 
        {
            d += deltaX;
            y1 += signY;
        }
    }
}