В чем заключается алгоритм Брезенхема для построения линий в компьютерной графике?

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

Принцип работы: берётся отрезок и его начальная координата x. 1 В цикле к этой координате прибавляют по единице в сторону конца отрезка. 1

На каждом шаге вычисляется ошибка — расстояние между реальной координатой y в этом месте и ближайшей ячейкой сетки. 1

Если ошибка не превышает половину высоты ячейки, то она заполняется. 1

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

Процесс завершается, когда текущая точка совпадает с конечной. 3

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