Бытовым примером применения этого алгоритма может послужить ситуация, когда у вас имеется 4 вазы и 10 яблок, и вам нужно разложить яблоки таким образом, чтобы вазы содержали примерно равное число яблок.
Этот алгоритм применим всегда, когда требуется распределить m сущностей по n группам, причём m / n - нецелое число (т.е. задачу нельзя решить, просто посчитав, сколько сущностей должно оказаться в каждой группе и разделив их).
Наибольшую знаменитость этот алгоритм получил благодаря использованию его для рисования наклонных линий на экране.
Алгоритм брезенхема работает следующим образом:
Нам известно, что на растровой поверхности можно закрашивать строки или столбцы пикселов. Таким образом, на растровой поверхности может быть изображены только вертикальные и только горизонтальные линии.
Стало быть, для того чтобы изобразить наклонную линию необходимо составить её из множества горизонтальных или вертикальных (в зависимости от угла наклона) линий.
Предположим что линия идёт слева направо, сверху вниз под небольшим углом к горизонтали. В этом случае наша линия будет состоять из горизонтальных отрезков, каждый из которых будет идти всё ниже и ниже по оси Y.
Нам необходимо всего-лишь определить, когда должен произойти излом горизонтального отрезка, т.е. когда отрезок должен перейти на один пиксел вниз.
Для этого введём такое понятия как фактор ошибки (или фактор погрешности). Фактор ошибки - это число, показывающие, насколько точка горизонтального ряда пикселов (т.е. горизонтального отрезка) отстаёт от соответствующей ей точки настоящего (идеального отрезка).
Горизонтальные ряды пикселов расположены на одинаковом расстоянии друг от друга по вертикали - на расстоянии в 1 пиксел. Таким образом идеальная линия может быть либо ближе к какой верхнему ряду (фактор ошибки < 0.5), либо быть между рядами (фактор ошибки = 0.5), либо быть ближе к нижнему ряду (фактор ошибки > 0.5).
Так, отслеживая изменения фактора ошибки, мы можем точно определить момент, когда линия должна уйти на один пиксел вниз. Это должно произойти когда фактор ошибки дойдёт до 0.5 .
На рисунке выше красным цветом показан идеальный отрезок. Синими линиями показаны ряды пикселов, которые должны быть закрашены, а залётным цветом показаны моменты, когда фактор ошибки достигает переломного числа (>0.5).
На VB реализация этого алгоритма будет выглядеть так:
- Код: Выделить всё
Public Sub DrawLine(ByVal XFrom As Long, ByVal YFrom As Long, ByVal XTo As Long, ByVal YTo As Long)
Dim x As Long
Dim y As Long
Dim ErrorFactor As Double
y = YFrom
For x = XFrom To XTo
DrawPoint x, y
ErrorFactor = CDbl((YTo - YFrom)) / CDbl(XTo - XFrom) * (x - XFrom) - (y - YFrom)
If ErrorFactor >= 0.5 Then
y = y + 1
End If
Next x
End Sub
Однако, эта реализация неоптимальна. Инструкция, производящая расчёт фактора ошибки подлежит значительной оптимизации.
Дело в том, что фактор ошибки - величина, растущая с одной скоростью. Поэтому достаточно вычислить, насколько за каждый шаг растёт фактор ошибки и, сохранив это значение, увеличивать на него каждый шаг фактор ошибки (а не вычислять заново).
С учётом этого, код функции примет такой вид:
- Код: Выделить всё
Public Sub DrawLine(ByVal XFrom As Long, ByVal YFrom As Long, ByVal XTo As Long, ByVal YTo As Long)
Dim x As Long
Dim y As Long
Dim ErrorFactor As Double
Dim ErrorIncrement As Double
ErrorIncrement = CDbl(YTo - YFrom) / CDbl(XTo - XFrom)
y = YFrom
For x = XFrom To XTo
DrawPoint
ErrorFactor = ErrorFactor + ErrorIncrement
If ErrorFactor > 0.5 Then
y = y + 1
ErrorFactor = ErrorFactor - 1
End If
Next x
End Sub
Здесь, когда фактор ошибки достигает критического значения, координата y увеличивается на 1, а фактор ошибки уменьшается на 1, т.к. ряд теперь стал ниже на 1 пиксел.
Но и этот код можно оптимизировать
Дело в том, что вычисления с дробными числами (а именно такими у нас являются ErrorFactor и ErrorIncrement) протекают дольше, чем с целыми числами. Поэтому, попытаемся превратить наши ErrorFactor и ErrorIncrement в целые.Как известно, если равные между собой X и Y умножит на некоторое Z, XZ и YZ будут также равны. Воспользуемся этим
Для начала умножим ErrorFactor и 0.5 на 2. Тогда 0.5 обратиться в единицу - от одного дробного числа мы уже избавились.
У нас остались ErrorIncrement и ErrorFactor. Итак, если ErrorFactor производится ErrorIncrement-ом, поэтому, если мы сделаем ErrorIncrement целым, ErrorFactor тоже станет целым.
ErrorIncrement легко сделать целым - достаточно умножить его на (XTo - XFrom). Для того, чтобы ничего не нарушилось, домножим на (XTo - XFrom) и единицу (которая в прошлой жизни была коэффициентом 0.5).
Тогда код примет следующий вид:
- Код: Выделить всё
Public Sub DrawLine(ByVal XFrom As Long, ByVal YFrom As Long, ByVal XTo As Long, ByVal YTo As Long)
Dim x As Long
Dim y As Long
Dim ErrorFactor As Long
Dim ErrorIncrement As Long
Dim DeltaX As Long
ErrorIncrement = YTo - YFrom
DeltaX = XTo - XFrom
y = YFrom
For x = XFrom To XTo
DrawPoint x, y
ErrorFactor = ErrorFactor + ErrorIncrement
If 2 * ErrorFactor > DeltaX Then
y = y + 1
ErrorFactor = ErrorFactor - DeltaX
End If
Next x
End Sub
Всё, все переменные лонговые. Код должен работать очень быстро.
Важно заметить, что наш код умеет рисовать только наклонные линии (для вертикальных или горизонтальных должен быть devision by zero или overflow). Чтобы создать функцию, которая рисовала бы любые линии, нужно написать переходник к этой - она должна менять либо менять один из знаков, либо менять x, y местами, либо менять начальные и конечные координаты, либо рисовать строго горизонтальные или вертикальные линии.
Недостатоком алгоритма Брезенхэма является то, что линии получаются грубыми, угловатыми (эффект алиасинга). Чтобы нарисовать сглаженную линию нужно использовать алгоритм Ву.