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

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

Суть алгоритма Брезенхэма

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

1. Основная задача – пройти по всем пикселям (точкам) растровой сетки, которые наиболее точно приближают идеальную (математическую) прямую между двумя заданными точками $(x_0, y_0)$ и $(x_1, y_1)$.
2. Ключевая концепция – использовать «накопление ошибки» (ошибкой считается отклонение пикселя от реальной непрерывной линии), чтобы понять, когда следует сместить линию по оси $y$ (или $x$, в зависимости от ориентации).

Алгоритм обходит координаты (обычно по одной из осей — по оси $x$, если линия не слишком «крутая»), определяя, когда и как нужно сделать «шаг» по второй оси.

---

Шаги (классический подход):

1. Вычислить разности по осям:

   $$dx = |x_1 - x_0|,\quad dy = |y_1 - y_0|$$

   Эти значения говорят нам, насколько «длинный» отрезок по $x$ и по $y$.

2. Определить приращения (направления) по X и Y:

   $$sx = \begin{cases} 1, & \text{если } x_0 < x_1 \\ -1, & \text{иначе} \end{cases} \quad sy = \begin{cases} 1, & \text{если } y_0 < y_1 \\ -1, & \text{иначе} \end{cases}$$

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

3. Определить «ошибку» (err).

   • В классическом варианте алгоритма Брезенхема часто инициализируют её как $dx - dy$ или $dx + dy$ (в разных вариациях). Ниже в коде приведена одна из распространённых формул инициализации err = dx + dy (при условии, что dy берётся со знаком минус).
   • Смысл «ошибки» (error) в том, что она аккумулирует расхождение между идеальной линией и текущим пикселем.

4. Основной цикл: пока мы не дойдём до конечной точки $(x_1, y_1)$:

   • Закрашиваем (или отмечаем) текущий пиксель $(x_0, y_0)$.
   • Смотрим «удвоенную ошибку» $e2 = 2 \cdot err$. Она позволяет выяснить, насколько сильно мы отклонились.
   • Если $e2$ больше или равна $\text{dy}$ (учитывая знак dy), значит, пора «сместиться» по оси $x$.
   • Если $e2$ меньше или равна $\text{dx}$, значит, пора «сместиться» по оси $y$.
   • Обновляем переменные err, x0, y0 соответствующим образом.

5. Завершение: когда $(x_0, y_0)$ совпадает с $(x_1, y_1)$, алгоритм заканчивает работу.

---

Пример реализации на C#

Пример кода ниже предполагает, что у вас есть Bitmap bmp, на котором вы хотите нарисовать линию цветом Color color. Метод SetPixel(...) выставляет цвет конкретного пикселя на изображении.

csharp
using System;
using System.Drawing;

public static class BresenhamExample
{
    public static void DrawLineBresenham(Bitmap bmp, 
                                         int x0, int y0, 
                                         int x1, int y1, 
                                         Color color)
    {
        // 1. Определяем «шаги» и модули dx, dy
        int dx = Math.Abs(x1 - x0);
        int dy = -Math.Abs(y1 - y0);
        
        // 2. Определяем направление приращений
        int sx = x0 < x1 ? 1 : -1;
        int sy = y0 < y1 ? 1 : -1;
        
        // 3. Инициализируем "ошибку"
        // Заметьте, что здесь она = dx + dy,
        // а не dx - dy. Но dy взяли со знаком минус.
        int err = dx + dy; 
        
        while (true)
        {
            // "Рисуем" пиксель (x0, y0)
            bmp.SetPixel(x0, y0, color);

            // Если дошли до конечной точки, выходим из цикла
            if (x0 == x1 && y0 == y1) break;

            // Рассчитываем удвоенную ошибку
            int e2 = 2 * err;
            
            // Проверяем условие смещения по X
            if (e2 >= dy)
            {
                err += dy;
                x0 += sx;
            }
            
            // Проверяем условие смещения по Y
            if (e2 <= dx)
            {
                err += dx;
                y0 += sy;
            }
        }
    }
}

Объяснение кода пошагово

1. dx и dy

   • dx = Math.Abs(x1 - x0) — это ширина отрезка по оси $x$.
   • dy = -Math.Abs(y1 - y0) — высота отрезка по оси $y$ со знаком минус.
     Такой вариант записи (с -Math.Abs(...)) часто встречается в коде, упрощающем дальнейшее использование err.

2. sx и sy

   • Определяются как +1 или -1, чтобы приращивать координаты в направлении от начальной точки к конечной.
   • Например, если $x_0 < x_1$, то sx = 1, иначе sx = -1.

3. err

   • Здесь инициализируется как err = dx + dy.
   • Поскольку dy уже отрицательный, получается нечто близкое к dx - |dy|.
   • Алгоритм отслеживает, когда и как мы превышаем «границу» между «следовать по x» и «следовать по y».

4. Цикл while

   • Рисуем текущий пиксель SetPixel(x0, y0, color).
   • Если уже достигли конечной точки, завершаем цикл.
   • Вычисляем e2 = 2 * err.
     • Если e2 >= dy, то смещаемся по оси $x$.
     • Если e2 <= dx, то смещаемся по оси $y$.
   • При каждом смещении корректируем err, добавляя к ней либо dy, либо dx (либо и то, и другое, если линия «дышит» по обеим осям).

5. Выход

   • Когда $(x_0, y_0)$ становится равно $(x_1, y_1)$, линия завершена.

---

Использование

Чтобы протестировать, вы можете создать Bitmap bmp подходящего размера, вызвать метод DrawLineBresenham, а затем, например, сохранить результат:

csharp
using System;
using System.Drawing;

public class Program
{
    public static void Main()
    {
        // Создаём "холст"
        Bitmap bmp = new Bitmap(200, 200);
        
        // Рисуем линию цветом Black (чёрным)
        BresenhamExample.DrawLineBresenham(bmp, 10, 10, 180, 150, Color.Black);

        // Сохраняем результат
        bmp.Save("result.png");
        
        Console.WriteLine("Линия нарисована и сохранена в result.png.");
    }
}

После выполнения в папке с программой появится файл result.png с проведённой прямой линией.

---

Заключение

Алгоритм Брезенхэма ценится за простоту и эффективность: он не требует вычисления дробных частей (как, например, при использовании уравнения прямой $y = mx + b$ с плавающей точкой). Для большинства задач растровой графики, где важна скорость, Bresenham остаётся одним из самых популярных решений для построения линий.

Ниже приведено объяснение на интуитивном уровне, без «страшной» математики. Попробуем представить, что вы буквально идёте «по клеточкам» от стартовой точки к конечной, пытаясь держаться как можно ближе к воображаемой прямой.

---

Представьте лист в клетку

1. У вас есть листок в клеточку (как школьная тетрадь), каждая клетка — это пиксель на экране.
2. Выставьте пальцем на клетку, где начинается линия (это начальная точка).
3. В другой части листа пометьте конечную точку.

Вам надо «пройтись» по клеткам так, чтобы получилась плавная линия, максимально близкая к настоящей прямой, но шагая только по клеткам (вправо, влево, вверх или вниз — по соседним клеточкам).

---

Как человек «на глаз» выбирает клетки

Если вы попытаетесь сами «прокрасться» от начала к концу по клеткам:

• Вы примерно прикинете, что линия идёт правее (или левее), и будете с каждым шагом уходить в нужную сторону по X (горизонталь).
• Но иногда заметите, что линия «поднимается» или «спускается» по Y (вертикаль), и значит, надо сделать шаг вверх или вниз, чтобы не «отстать» от воображаемой прямой.

Этот процесс очень похож на то, что делает алгоритм:

Он периодически «смотрит», насколько вы «съехали» вбок относительно реальной прямой, — если слишком сильно, то делает дополнительный шаг вверх (или вниз).

Так получается «лесенка» из пикселей, которая идёт максимально близко к воображаемой линии.

---

Идея «накопления ошибки»

В алгоритме есть понятие «ошибки» (error). Простыми словами:

1. Ошибка растёт, когда вы «двигаетесь» только по горизонтали (или вертикали), и из-за этого ваша текущая позиция (клетка) начинает чуть-чуть «отставать» от реальной прямой, которая может идти под углом.
2. Когда «ошибка» становится достаточно большой, это значит, что пора сделать дополнительный шаг в вертикальном (или горизонтальном) направлении, чтобы вернуться к воображаемой линии и не «съехать» слишком далеко.

Алгоритм даёт простой способ «подсчитывать» эту ошибку так, чтобы каждый раз знать, когда именно сделать этот самый «дополнительный» шаг.

---

В чём фишка?

• Не нужны дробные числа. Алгоритм работает с целыми значениями (и со знаками «+» или «–»). В старых компьютерах (да и часто в современных графических движках) это быстрее и проще.
• Линия получается ровная, без «дроблений» и скачков.

Результат — последовательность пикселей, которые максимально точно повторяют геометрическую прямую, но с учётом того, что у нас есть дискретная сетка.

---

Как это выглядит в коде (простое понимание без формул)

Пусть у нас есть:

• Начальные координаты $(x_0, y_0)$
• Конечные координаты $(x_1, y_1)$

Мы хотим пройти от первой точки ко второй, двигаясь на каждом шаге либо по X (вправо или влево), либо по Y (вверх или вниз). Код (условно) делает так:

1. Определяем, в какую сторону надо двигаться по X и по Y (вправо или влево, вверх или вниз).
2. Задаём «ошибку» (изначально 0 или близкое к тому).
3. Рисуем текущую клетку (в коде: SetPixel).
4. Идём по пикселям:
   • Делаем главный шаг (например, по X, если линия более «полого» идёт слева направо).
   • Считаем, что из-за этого шага стала чуть больше «ошибка» (мы «отклоняемся» от идеальной диагонали).
   • Если ошибка слишком большая, делаем дополнительный шаг по Y (вверх или вниз) и обнуляем (или корректируем) ошибку.

Повторяем, пока не дойдём до конечной точки.

---

Пример с воображаемой прогулкой

• Начинаем в клетке $(0, 0)$.
• Знаем, что надо дойти до $(7, 4)$. То есть в идеале нам нужно в сумме сделать 7 шагов вправо и 4 шага вверх.
• Алгоритм «пробует» каждый раз двигаться вправо (потому что это основное направление — у нас 7 шагов вправо, что больше, чем 4 вверх).
• Но после каждого шага мы проверяем: «Не пора ли двинуться и вверх тоже?». Потому что надо же как-то набрать 4 шага вверх за время, пока мы шагаем 7 раз вправо.
• Как только «ошибка» говорит «ты уже запоздал с подъемом», мы делаем 1 шаг вверх.
• В итоге выйдет «ступенчатая» линия, которая из (0,0) приведёт нас в (7,4).

На каждый такой шаг мы закрашиваем клетку (pixel) на экране, и в результате получим ровную ломаную, максимально похожую на непрерывную линию.

---

Резюмируя

• Алгоритм Брезенхэма — это способ пошагово «идти» по пикселям от начала до конца, решая в каждый момент, нужен ли дополнительный вертикальный/горизонтальный сдвиг, чтобы остаться как можно ближе к воображаемой прямой.
• Не нужно глубоко залезать в геометрические формулы. Главное — понять, что мы аккуратно «размазываем» шаги по одной оси (X) и по другой (Y), чтобы прийти из одной точки в другую самым ровным маршрутом по клеткам.

Вот и всё, что происходит под капотом.

Ниже приведён пример кода на C#, который рисует линию алгоритмом Брезенхэма. Сначала сам код, а затем максимально простое объяснение, без сложной математики, чтобы было понятно даже тем, кто не силён в формулах.

Пример кода на C#

csharp
using System;
using System.Drawing;

public static class BresenhamDrawer
{
    public static void DrawLine(Bitmap bmp, 
                                int x0, int y0, 
                                int x1, int y1, 
                                Color color)
    {
        // 1) Считаем, насколько линия "растянута" по горизонтали (dx) и вертикали (dy)
        int dx = Math.Abs(x1 - x0);
        int dy = Math.Abs(y1 - y0);

        // 2) Определяем направление, в какую сторону шагать:
        //    - если конечная точка правее начальной, идём вправо (sx = 1), иначе — влево (sx = -1)
        //    - если конечная точка выше начальной, идём вверх (sy = 1), иначе — вниз (sy = -1)
        int sx = (x0 < x1) ? 1 : -1;
        int sy = (y0 < y1) ? 1 : -1;

        // 3) "Ошибку" начинаем с разницы dx - dy.
        //    (Это внутренняя переменная, которая нужна для понимания,
        //     когда "переключаться" между горизонтальным и вертикальным шагом.)
        int err = dx - dy;

        while (true)
        {
            // "Закрашиваем" пиксель в текущих координатах
            bmp.SetPixel(x0, y0, color);

            // Если мы уже дошли до конечной точки, выходим из цикла
            if (x0 == x1 && y0 == y1) break;

            // 4) Проверяем, нужно ли сместиться по X или Y (или обоим сразу)
            int e2 = 2 * err;  // Вспомогательное значение

            // Если e2 больше, чем -dy, значит, пора сдвинуться по X
            if (e2 > -dy) 
            {
                err -= dy;
                x0 += sx;
            }

            // Если e2 меньше, чем dx, значит, пора сдвинуться по Y
            if (e2 < dx) 
            {
                err += dx;
                y0 += sy;
            }
        }
    }
}

Как запустить и проверить

csharp
class Program
{
    static void Main(string[] args)
    {
        // Создаём "холст" 200x200 пикселей
        using (Bitmap bmp = new Bitmap(200, 200))
        {
            // Рисуем линию чёрным цветом с (10,10) до (180,150)
            BresenhamDrawer.DrawLine(bmp, 10, 10, 180, 150, Color.Black);

            // Сохраняем результат в файл
            bmp.Save("myline.png");
            Console.WriteLine("Линия нарисована и сохранена как myline.png");
        }
    }
}

После запуска вы увидите в папке с программой файл myline.png, на котором будет прямая линия, нарисованная «лестничным» способом (по пикселям).

---

Объяснение «на пальцах», без сложных формул

1. Представьте лист в клетку
   У нас есть «начальная клетка» $(x_0, y_0)$ и «конечная клетка» $(x_1, y_1)$. Нужно «пройти» по клеткам так, чтобы в итоге получилась линия, максимально похожая на обычную (математическую) прямую.

2. Двигаемся по чуть-чуть
   Мы хотим идти по горизонтали (вправо или влево) и время от времени приподниматься (или опускаться) по вертикали. Всё, чтобы не «съехать» слишком далеко от воображаемой прямой.

3. Ошибку можно вообразить как «накопление отклонения»

   • Если мы слишком долго идём вбок и совсем не поднимаемся, реальная линия (которая идёт под углом) «ушла» уже выше. Это «отклонение» мы называем «ошибкой».
   • Как только ошибка перевалила некий порог, мы «исправляемся» — делаем шаг вверх (или вниз). При этом ошибка «сбрасывается» или уменьшается.
   • После такого шагания «два шага вправо — один вверх» (просто как пример) мы всё время находимся рядом с настоящей прямой, но при этом рисуем только целые пиксели.

4. Почему это быстрее обычных формул?

   • Алгоритм Брезенхэма не требует «дробных» (вещественных) вычислений вроде 1.2345. Он оперирует в основном целыми числами и знаками «плюс/минус».
   • Поэтому раньше (и сейчас) его часто используют в компьютерной графике для отрисовки, ведь он работает быстро и легко.

5. В коде

   • dx и dy — это, грубо говоря, «сколько надо пройти по горизонтали» и «по вертикали».
   • sx и sy — «двигаться ли вправо или влево», «вверх или вниз».
   • err — переменная, показывающая, как далеко мы уже «ушли» от идеальной линии, и когда пора сделать дополнительный вертикальный/горизонтальный шаг.

Каждый проход цикла:

• Рисует пиксель (текущую клетку).
• Рассматривает ошибку: нужно ли сделать дополнительный «шаг» вверх/вниз или достаточно только вправо/влево.
• Изменяет err, x0, y0 (наши «координаты» в сетке пикселей).

Когда мы достигаем конечной точки, цикл останавливается — линия готова.

---

Итог

• Главная мысль: мы последовательно «шагаем» от начала к концу, в основном двигаясь по оси X (если линия вытянута по горизонтали) или по Y (если по вертикали). В нужные моменты «подпрыгиваем» на одну клетку вверх/вниз (или вправо/влево, если линия почти вертикальная).
• Без формул это можно описать так: «Посмотри, куда идёт воображаемая линия, и, если мы слишком отклонились, сделай шаг и по другой оси, чтобы вернуться как можно ближе».
• Код лишь аккуратно автоматизирует эти «шаги» через переменную err, чтобы всё работало быстро и точно.