05. Алгоритмы Брезенхема разложения отрезков в растр. Простой, целочисленный, общий алгоритмы Брезенхема. - p1xelse/CG GitHub Wiki

Понятие об ошибке заложил Брезенхем. Именно на этом понятие основывается работа алгоритма. Ошибкой называется расстояние между действительным положением отрезка и ближайшим пикселом сетки растра.

Согласно алгоритму на каждом шаге одна из координат - либо x, либо y (выбирается большее из приращений по модулю) изменяется на ±1, другая координата меняется на 0 или ±1. (± выбирается в зависимости от квадранта)

Поскольку при реализации алгоритма на ЭВМ быстрее анализировать не само значение ошибки, а ее знак, то истинное значение ошибки смещается на - 0.5. Пусть f - значение ошибки на очередном i-м шаге, Yи - ордината идеального отрезка, а Yi - ордината пиксела, выбранного для аппроксимации отрезка на том же i-м шаге, m - тангенс угла наклона отрезка Поскольку на первом шаге высвечивается пиксел с начальными координатами, то для него f = 0, поэтому задаваемое предварительно значение f = m - 0,5 является фактически ошибкой для следующего шага. Приведем основные расчетные соотношения, используемые в алгоритме.

Различают простой и общий алгоритмы Брезенхема. Простой алгоритм Брезенхема предназначен для построения отрезков, расположенных в первом октанте. В этом случае на каждом шаге координата X пиксела всегда получает единичное приращение, а координата Y изменяется либо на ноль, либо на единицу в зависимости от расстояния между действительным положением отрезка и ближайшей точкой растра, аппроксимирующей на данном шаге отрезок.

В общем алгоритме Брезенхема большее по модулю из приращений принимается равным шагу растра, то есть единице, причем знак приращения совпадает со знаком разности конечной и начальной координат отрезка:

delta X = sign(Xк - Xн), если  |Xк - Xн| >= |Yк - Yн|
delta Y = sign(Yк - Yн), если  |Yк - Yн| > |Xк -Xн|

Значение другой координаты идеального отрезка для следующего шага определяется как Yиi+1 = Yиi + m , поскольку приращение ординаты совпадает с величиной одного катета прямоугольного треугольника, а другой катет равен шагу сетки растра, то есть единице.

Ошибка на очередном шаге вычисляется как

(Поскольку в алгоритме и программе не надо сохранять значения ошибок для всех шагов, то последнее выражение можно записать как f = f + m).

В зависимости от полученного значения ошибки выбирается пиксел с той же ординатой (при f < 0) или пиксел с ординатой, на единицу большей, чем у предыдущего пиксела (при f >= 0).

Поскольку предварительное значение ошибки вычисляется заранее, то есть f + m вычислено на предыдущем шаге, то во втором случае останется только вычесть единицу из значения ошибки: f = f - 1, так как в этом случае Yi+1= Yi + 1, что не учитывалось ранее при расчетах.

Простой алгоритм Брезенхема (для первого октанта) :

1. Ввод исходных данных (Xн, Yн), (Xк, Yк)
2. X = Xн ; Y = Yн
3. dx = Xк - Xн ; dx = Xк - Xн  // Вычисление приращений
7. m = dy / dx ; e = m - 0.5
8. Цикл определения отрезка (по i от 1 до dx + 1) // шаг = 1
   8.1. Высвечивание T(x, y)
   8.2. Если e >= 0, то 
    1) y = y + 1
    2) e = e - 1 
   8.3. e = e + m
   8.4. Конец цикла
9. Конец

Общий алгоритм Брезенхема действительный (целочисленный):

1. Ввод исходных данных (Xн, Yн), (Xк, Yк)
2. X = Xн ; Y = Yн
3. dx = Xк - Xн ; dx = Xк - Xн  // Вычисление приращений
4. Sх = sign(dx) ; Sy = sign(dy)  // Вычисление шагов изменения каджой координаты
5. dx = |dx|; dy = |dy|
6. Если dx > dy, то обмен = 0, иначе обмен = 1; t = dx; dx = dy; dy = t // Меняем местами приращения, чтобы в dy 
большее из этих двух приращения и итерация на 1 производилась по dy
7. m = dy / dx ; e = m - 0.5 (для челочисленного e = 2dy - dx)
8. Цикл определения отрезка (по i от 1 до dx + 1) // шаг = 1
   8.1. Высвечивание T(x, y)
   8.2. Если e >= 0, то 
    1) если обмен = 0, то y = y + sy; иначе x = x + sx
    2) e = e - 1 // (для целочисленного e = e - 2dx) 
   8.3. Если обмен = 0, то x = x + sx ; иначе y = y + sy
   8.4. e = e + m // (для целочисленного e = e + 2dy)
   8.5. Конец цикла
9. Конец