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) {

⇐ Предыдущая| |Следующая ⇒