![[LineBresenham.gif]]
это алгоритм, определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками. Это один из старейших алгоритмов в [машинной графике](https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%BD%D0%B0%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D0%BA%D0%B0 "Машинная графика") — он был разработан [Джеком Элтоном Брезенхэмом](https://ru.wikipedia.org/wiki/%D0%91%D1%80%D0%B5%D0%B7%D0%B5%D0%BD%D1%85%D1%8D%D0%BC,_%D0%94%D0%B6%D0%B5%D0%BA_%D0%AD%D0%BB%D1%82%D0%BE%D0%BD "Брезенхэм, Джек Элтон") в компании [IBM](https://ru.wikipedia.org/wiki/IBM "IBM") в [1962 году](https://ru.wikipedia.org/wiki/1962_%D0%B3%D0%BE%D0%B4 "1962 год"). Алгоритм широко используется, в частности, для рисования линий на экране компьютера. Существует обобщение алгоритма Брезенхэма для построения кривых 2-го порядка.
При работе с [[grid-based positioning (Сеточное позиционирование)|сеточным позиционированием]] алгоритм Брезенхема:
1. **Инициализация**: Выбираются две точки (начальная и конечная) линии. Рассчитываются разницы по горизонтальной (`dx`) и вертикальной (`dy`) осям между этими точками.
2. **Определение шагов**: Алгоритм определяет, в каком направлении (по оси X или Y) следует двигаться быстрее, основываясь на том, какая разница (`dx` или `dy`) больше.
3. **Вычисление ошибки**: Вычисляется значение ошибки, которое помогает определить, когда следует сделать шаг в направлении меньшей разницы (например, по вертикали, если `dx` > `dy`).
4. **Итеративный процесс**: Линия строится путем последовательного выбора ближайшей к идеальной линии сеточной точки на каждом шаге. При этом алгоритм корректирует ошибку, и на основе ее значения решает, когда делать шаг в "медленном" направлении.
5. **Завершение рисования**: Процесс продолжается до тех пор, пока не будет достигнута конечная точка линии.
Этот алгоритм идеален для применения в компьютерных играх и других приложениях, где требуется рисование прямых линий на сетке с ограниченными ресурсами, поскольку он обеспечивает хорошее приближение к идеальной линии при минимальных вычислительных затратах.
### Пример кода на C\#
```csharp
using System;
using System.Collections.Generic;
// Класс для представления позиции на сетке.
public class GridPosition
{
public int x { get; set; } // Координата x позиции.
public int z { get; set; } // Координата z позиции.
// Конструктор для установки координат позиции.
public GridPosition(int x, int z)
{
this.x = x;
this.z = z;
}
// Переопределение метода ToString для печати позиции в формате (x, z).
public override string ToString()
{
return
quot;({x}, {z})";
}
}
// Вспомогательный класс для работы с сеткой.
public class GridHelper
{
// Метод для получения линии между двумя позициями.
public List<GridPosition> GetLineBetween(GridPosition start, GridPosition end)
{
List<GridPosition> line = new List<GridPosition>(); // Список для хранения позиций линии.
// Начальные координаты линии.
int x = start.x;
int z = start.z;
// Вычисление разницы координат между начальной и конечной позициями.
int dx = Math.Abs(end.x - start.x);
int dz = Math.Abs(end.z - start.z);
// Определение направления движения по осям.
int sx = start.x < end.x ? 1 : -1;
int sz = start.z < end.z ? 1 : -1;
// Ошибка e2 используется для определения следующего шага.
int err = (dx > dz ? dx : -dz) / 2;
int e2;
while (true) // Начинаем построение линии.
{
line.Add(new GridPosition(x, z)); // Добавляем текущую позицию в линию.
if (x == end.x && z == end.z) break; // Если достигли конечной позиции, прерываем цикл.
e2 = err;
if (e2 > -dx) { err -= dz; x += sx; } // Двигаемся по оси x.
if (e2 < dz) { err += dx; z += sz; } // Двигаемся по оси z.
}
return line; // Возвращаем построенную линию.
}
}
// Основной класс программы.
public class Program
{
public static void Main()
{
var gridHelper = new GridHelper(); // Создание экземпляра вспомогательного класса.
var start = new GridPosition(1, 1); // Начальная позиция.
var end = new GridPosition(7, 3); // Конечная позиция.
var line = gridHelper.GetLineBetween(start, end); // Получение линии между позициями.
// Выводим позиции линии на консоль.
foreach (var position in line)
{
Console.WriteLine(position);
}
}
}
```