putpixel ( xa, ya, color); for (int x = xa + 1; x <= xb; x++ )
{if (( с += k ) > 0.5 )
{
c-=1;о
JM.6. Растровые алгоритмы
у++;
}putpixel ( х, у, color ); }
}Замечание. Выбор точки можно трактовать и так: рассматривается середина отрезка между возможными кандидатами и проверяется, где (выше или ниже этой середины) лежит точка пересечения отрезка прямой, после чего выбирается соответствующий пиксел. Это метод срединной точки (midpoint algorithm).
Сравнивать с нулем удобнее, чем с 1/2, поэтому введем новую вспомогательную величину dj = 2с, - 1, заметив, что df = 2k- \ (так как с\ - к). Получаем следующую программу:
(21 // File Ijne4.cpp
void line (int xa, int ya, int xb, int yb, int color)double к = ((double)(yb-ya))/(xb-xa); double d = 2*k -1; int у = ya;
putpixel ( xa, ya, color);
for (int x = xa + 1; x <= xb; x++ )
{
if (d > 0 ) {d += 2*k - 2; У++;
}
else
d += 2*k; putpixel (x, y, color);
}
}Несмотря на то, что и входные данные являются целочисленными величинами и все операции ведутся на целочисленной решетке, алгоритм использует операции с вещественными числами. Чтобы избавиться от необходимости их использования, заметим, что все вещественные числа, присутствующие в алгоритме, являются числами вида -~ip е Z. Поэтому если домножить величины dj и к на Ах = х^ - ха , Ах
то в результате останутся только целые числа. Тем самым мы приходим к алгоритму Врезенхейма Е) // File Iine5.cpp
// simplest Bresenham's alg. 0 <= y2 - y1 <= x2 - x1 void line (int xa, int ya, int xb, int yb, int color) {
int dx = xb - xa; int dy = yb - ya;Компьютерная графика. Полигональные модели
int d = ( dy « 1 ) - dx; int d1 = dy « 1; int d2 = (dy-dx)«1; putpixel ( xa, ya, color); for (int x = xa + 1, у = y1; x <= xb; x++ )
{
if ( d > 0 ) {
d += d2;у += 1;
}
else
d +=d1;
putpixel ( x, y, color);
}
}Известно, что этот алгоритм дает наилучшее растровое приближение отрезка. Из предложенного примера несложно написать функцию для построения 4-связной развертки отрезка.
2] // File line_4.cpp
void line_4 (int x1, int y1, int x2, int y2, int color) {