Представление линии в квадратном растре

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

Алгоритм Брезенхема - алгоритм, который позволяет построить прямую на мониторе, независимо от угла наклона прямой. Это эффективный метод, поскольку он включает в себя только целочисленные операции сложения, вычитания и умножения.

Алгоритм

Мы работаем с отрезками(экран компьютера не может быть бесконечным). По условию нам даны начало и конец отрезка. Угол его поворота может быть любым. Обозначим за [math]\displaystyle{ \alpha }[/math]. Давайте рассмотрим случай, где [math]\displaystyle{ \alpha = \frac{\pi}{4} }[/math]:
Закрасим первый пиксель. Если бы мы строили отрезок в реальной жизни, то он бы пересекал стенки клеток в разных местах. Будем опираться на этот факт и скажем, что если отрезок пересекает стенку клетки ниже середины, то мы остаемся на той же строке и закрашиваем соседнюю клетку(соседний пиксель). Если же отрезок пересекает стенку клетки выше половины, то сдвигаемся вправо, а потом вверх(т.е. по диагонали) и закрашиваем этот пиксель.
Обозначим разность координаты конца и координаты начала по оси x - dx. Соответственно по оси y - dy

Так как мы работаем с углом [math]\displaystyle{ \alpha = 45^{\circ} }[/math] заметим, что всегда должно выполняться условие dx ≥ dy.

---

Код

1. Создаем переменные d, dx, dy, где
d - величина, которая показывает, где прямая пересекла пиксель.
x - координата первого пикселя по оси x.
y - координата первого пикселя по оси y.

2. Заходим в цикл, в котором движемся по x до момента, пока не дойдем до конца отрезка. Мы предполагаем, что координата конца больше координаты начала по x. Если же наоборот, то можно поменять их местами.
3. Закрашиваем текущий пиксель.
4. Изменяем величину d, чтобы показать пересечение стенки отрезком в данном пикселе.
4.1. Если у нас d ≥ 0, то увеличиваем y(то есть поднимаемся вверх).
5. Инкрементируем x, чтобы перейти вправо.

d = 2*dy-dx;
x = x1; y = y1;
do {
    PutPixel(x, y);
    if (d<0)
        d += 2*dy;
    else{
        d += 2*(dy-dx);
        ++y;
    }
    ++x;
} while(x<=x2);

Важно

Если угол наклона более 45, то dx ≤ dy, следовательно, алгоритм "разворачивается" и мы начинаем идти не по x, а по y. В коде переменные поменяются местами.
Если угол наклона отрицательный, то мы идем не вверх(++y), а вниз(--y).