Краткие теоретические сведения. Алгоритм выбирает оптимальные растровые координаты для представления отрезка

Алгоритм выбирает оптимальные растровые координаты для представления отрезка. В процессе работы одна из координат — либо x, либо у (в зависимости от углового коэффициента) — изменяется на единицу. Изменение другой координаты (либо на нуль, либо на единицу) зависит от расстояния между действительным положением отрезка и ближайшими координатами сетки. Такое расстояние мы назовем ошибкой.

Алгоритм построен так, что требуется проверять лишь знак этой ошибки. На рис. 1 это иллюстрируется для отрезка в первом октанте, т. е. для отрезка с угловым коэффициентом, лежащим в диапазоне от нуля до единицы. Из рисунка можно заметить, что если угловой коэффициент отрезка из точки (0, 0) больше чем 1/2, то его пересечение с прямой х = 1 будет расположено ближе к прямой y = 1, чем к прямой у = 0. Следовательно, точка растра (1, 1) лучше аппроксимирует ход отрезка, чем точка (0, 0). Если угловой коэффициент меньше 1/2, то верно обратное. Для углового коэффициента, равного 1/2, нет какого-либо предпочтительного выбора. В данном случае алгоритм выбирает точку (1, 1).

Рис. 1. Основная идея алгоритма Брезенхема

Не все отрезки проходят через точки растра. Подобная ситуация иллюстрируется рис. 2, где отрезок с тангенсом угла наклона 3/8 сначала проходит через точку растра (0, 0) и последовательно пересекает три пиксела.

Рис. 2. График ошибки в алгоритме Брезенхема

Также иллюстрируется вычисление ошибки при представлении отрезка дискретными пикселями. Так как желательно проверять только знак ошибки, то она первоначально устанавливается равной -1/2.

Таким образом, если угловой коэффициент отрезка больше или равен 1/2, то величина ошибки в следующей точке растра с координатами (1, 0) может быть вычислена как

е = е + m

где m — угловой коэффициент. В нашем случае при начальном значении ошибки -1/2

е = -1/2 + 3/8 = - 1/8

Так как е отрицательно, отрезок пройдет ниже середины пиксела. Следовательно, пиксел на том же самом горизонтальном уровне лучше аппроксимирует положение отрезка, поэтому у не увеличивается. Аналогично вычисляем ошибку

е = -1/8 + 3/8 = 1/4

в следующей точке растра (2, 0). Теперь е положительно, а значит, отрезок пройдет выше средней точки. Растровый элемент (2, 1) со следующей по величине координатой у лучше аппроксимирует положение отрезка. Следовательно, у увеличивается на единицу. Прежде чем рассматривать следующий пиксел, необходимо откорректировать ошибку вычитанием из нее единицы. Имеем

е = 1/4 - 1 = -3/4

Заметим, что пересечение вертикальной прямой х = 2 с заданным отрезком лежит на 1/4 ниже прямой y = 1. Если же перенести отрезок 1/2 вниз, мы получим как раз величину -3/4. Продолжение вычислений для следующего пиксела дает

е = -3/4 + 3/8 = -3/8

Так как е отрицательно, то у не увеличивается. Из всего сказанного следует, что ошибка — это интервал, отсекаемый по оси у рассматриваемым отрезком в каждом растровом элементе (относительно -1/2).

 

 

private void button3_Click(object sender, EventArgs e)

{

Int32 x1 = (Convert.ToInt32(this.textBox1.Text) + this.pictureBox1.Width / 2);

Int32 y1 = (Convert.ToInt32(this.textBox2.Text) * (-1) + this.pictureBox1.Height / 2);

Int32 x2 = (Convert.ToInt32(this.textBox3.Text) + this.pictureBox1.Width / 2);

Int32 y2 = (Convert.ToInt32(this.textBox4.Text) * (-1) + this.pictureBox1.Height / 2);

Int32 x= x1;

Int32 y = y1;

Int32 dx = Math.Abs(x2-x1);

Int32 dy = Math.Abs(y2 - y1);

 

Int32 s1 = sign(x2 - x1);

Int32 s2 = sign(y2 - y1);

 

Int32 obm=0;

if (dy>dx)

{

Int32 temp = dx;

dx = dy;

dy = temp;

obm=1;

}

Int32 ee=2*dy-dx;

 

for (Int32 i=0;i<dx;i++)

{

plot(x,y);

while (ee>=0)

{

if (obm==1) {x=s1+x;}

else {y=y+s2;}

ee=ee-2*dx;

}

 

if (obm==1) {y=y+s2;}

else {x=x+s1;}

ee = ee + 2 * dy;

}

 

this.pictureBox1.Image = bmp;

}