1 В русской математической литературе эту величину чаще называют угловым коэффициентом. - Примеч. пер.
10.4. Рисование прямых своими силами: алгоритм Брезенхема рисования окружности или эллипса. Алгоритм Брезенхема является классическим примером инкре-ментного алгоритма (incremental algorithm), в котором вычисляется положение каждого пиксела вдоль прямой на основе информации о предыдущем пикселе1. В нем используются только целые величины, отсутствует умножение, а также содержится компактный и эффективный внутренний цикл, генерирующий искомые пикселы.
Существуют различные вариации алгоритма Брезенхема, слегка отличающиеся между собой. Мы будем рассматривать вариант, известный под названием алгоритм средней точки (midpoint algorithm). Этот алгоритм генерирует для прямых линий в точности такие же пикселы, что и алгоритм Брезенхема, и такой подход можно расширить для рисования более сложных форм, например окружностей и эллипсов.
Предположим, что, как и ранее, нам даны целочисленные концевые точки прямой (ах, ау) и фх, Ьу). Требуется определить наилучшую последовательность промежуточных пикселов.
Для упрощения изложения метода рассмотрим частный случай, когда ах < Ьх (то есть точка Ь лежит справа от точки а) и наклон прямой находится между 0 и 1. (Позднее эти ограничения будут сняты.) Для удобства определим границы отрезка прямой по х и у:
W=bx - ах (ширина); Н = Ьу-ау (высота). (10.5)
В силу установленных нами ограничений, Я и Появляются положительными, и Я < W. Тогда по мере возрастания х от ах до Ъх соответствующее значение у возрастает от ау до Ьу, однако у растет медленнее, чем х. При возрастании х на единицу наилучшее целое значение у будет иногда оставаться неизменным, а иногда увеличиваться на 1. Алгоритм средней точки быстро определяет, которая из этих двух ситуаций имеет место. (Отметим, что у никогда не уменьшается и никогда не возрастает больше чем на 1. Почему?)
Из главы 4 мы знаем, что уравнение прямой, проходящей через точки (ах, ау) и фх, Ьу), имеет вид:
-W(y-ay) + H(x-ax) = 0.