Алгоритм Брезенхэма для отрезков прямых

 

Трудности применения процедуры LINE состоят в том, что ок­ругление у до целого значения требует времени и, кроме того, у и т должны быть вещественными переменными или двоичными дробями, но не целыми переменными, так как тангенс угла наклона есть дробь. Более привлекателен в этом отношении алгоритм Брезенхэма [58], поскольку для него необходима только целая арифметика. Вещест­венные переменные не используются совсем и, следовательно, ок­ругление не требуется. Для простоты будем считать, что тангенс угла наклона принимает значения в диапазоне 0-1. В алгоритме используется управляющая переменная di, которая на каждом шаге пропорциональна разности между s и t (рис. 11.2). На рис. 11.2 приведен i-й шаг, когда пэл Pi-1 уже найден как ближайший к реальному изображаемому отрезку, и теперь требуется определить, какой из пэлов должен быть установлен следующим: T или S;. Если s<t, то Si ближе к отрезку и необходимо выбрать

Рис 11.1. Пошаговое вычисление у, при котором выбор пэла (обозначаемого чер­ным кружком) осуществляется путем округления у.

его; в про­тивном случае ближе будет Ti. Другими словами, если s-t < 0, выбирается Si, в противном случае выбирается Ti.

Изображаемый отрезок проводится из точки (x1, y1) в точку (x2t y2). Пусть первый отрезок находится ближе к началу коорди­нат, тогда перенесем обе точки при помощи Т(-x1, -y1) так, чтобы начальной точкой отрезка стала точка (0, 0),

 

Рис. 11.2. Геометрическое обоснование алгоритма Брезенхэма. Черными круж­ками обозначены пэлы, выбранные с помощью этого алгоритма.

а конечной - (dx, dy), где dx -= x 2— x 1 и dy = y 2— y 1. Уравнение прямой теперь имеет вид y = (dy / dx) x. Обозначим координаты (после переноса) Р_i-1 через (r, q), как показано на рис. 11.2. Тогда S_i = (r+l, q) и Т_i = (r+1, q+1).

Из рис. 11.2 следует, что

 

 Поэтому .            (11.1)

Если s-t <0 выбираем S_i. Преобразуя выражение (11.1), получаем

dx (s—t) = 2(r*dy—q*'dx) + -2dy - dx.

 

Величина dx положительна, поэтому dx(s—t)<0 можно использо­вать в качестве проверки при выборе S_i. Обозначим часть неравен­ства через d_i. Тогда

.

Поскольку r=x_i-1 и q=y_i-1, то

Прибавляя 1 к каждому из индексов, имеем

 

Вычитая d_i из d_i+i, получаем

         (11.2)

Известно, что x_i - x_i-1 = 1. Учитывая это, запишем

Если d_i >= 0, выбирается T_i, тогда y_i=y_i-1+1 и

Если же d_i < 0, выбирается S_i, тогда y_i=y_i-1 и

Если di >= 0, выбирается Ti, тогда yi=yi-1+1 и

                                        (11.3)

Если же di < 0, выбирается Si, тогда yi=yi-1 и

                                                   (11.4)

 

Таким образом, мы получили итеративный способ вычисления di+1 по предыдущему значению di и выбора между Si и Ti. Начальное значение di можно найти из выражения (11.2) при i = 1 с учетом того, что (х0, y0) = (0, 0). Тогда

 

                                                (11.5)

 

Для вычисления по формулам (11.3) — (11.5) требуются мини­мальные арифметические возможности: они включают сложение, вычитание и сдвиг влево (для умножения на 2). Это важно, посколь­ку исключается длительная по времени операция умножения. Более того, как видно из следующей реализации алгоритма Брезенхэма (отметим, что эта версия работает только для отрезков, тангенсы углов наклона которых находятся в диапазоне 0 - 1; обобщение алгоритма предоставляем читателю выполнить в качестве упражне­ния), выполняемый в нем цикл очень прост:

РАСТРОВАЯ РАЗВЕРТКА ЛИТЕР

 

В гл. 3 рассмотрен общий метод изображения литер, основанный на матрице точек. Тот же метод используется и при построении раст­ровых изображений: точечное представление литеры помещается в заданную позицию буфера регенерации. Наименьшей сеткой, с по­мощью которой можно описывать литеры с приемлемым качеством, является сетка 5 х 7; для представления прописных и строчных литер необходима матрица размером 5 x 9. Для символов более высокого качества требуется еще большая матрица.