Алгоритм вывода прямой линии

Пусть на растре заданы две точкии с целочисленными координатами (рис. 4.1).

Запишем уравнение прямой, проходящей через эти точки

или

(4.1)

где

, , ,

Рис. 4.1

Будем рассматривать случай для и

Пусть точка уже поставлена. Необходимо принять решение о том, какие координаты должна иметь точка: или

Запишем выражение для - координаты математической прямой для :

Вычислим разности

Тогда

Выполним замену в

или

Полагая

получим

, (4.2)

где

(4.3)

(4.4)

Так как , то

Вычитая (2) из (4), получим

но , тогда

При этом

Поэтому

Вычислим начальное значение .

Из (4.2) получаем

(4.5)

Значение соответствует точке .

Точка по условию удовлетворяет уравнению прямой (4.1)

Отсюда

Подставляя полученное значение в выражение (4.3) для , получим

Подставляя полученное выражение для в выражение (4.5) для , получим

Ниже приведен возможный вариант функции для рисования линии между точками и для цветом color для работы с использованием библиотеки классов MFC.

void Line(CDC& dc,int x1,int y1,int x2,int y2,COLORREF color)

// Алгоритм Брезенхема для прямой y=kx+b, при k<1!!!

// dc – ссылка на контекст устройства

// (x1,y1) – координаты начальной точки

// (x2,y2) – координаты конечной точки

// color – цвет линии

{

int dx=x2-x1;

int dy=y2-y1;

int d=2*dy-dx;

int d1=2*dy;

int d2=2*(dy-dx);

int y=y1;

dc.SetPixel(x1,y1,color);

for(int x=x1+1;x<=x2;x++)

{

if(d<0)d+=d1;

else

{

y++;

d+=d2;

}

dc.SetPixel(x,y,color);

}

}

Приведенная ниже функция реализует алгоритм Брезенхема для любых .

void MyLine(CDC& dc,int x1,int y1,int x2,int y2,COLORREF color)

// Алгоритм Брезенхема для прямой y=kx+b при любых k

{

int dx=abs(x2-x1);

int dy=abs(y2-y1);

int incX=x2>=x1?1:-1;

int incY=y2>=y1?1:-1;

if(dy<=dx) ///

{

int d=2*dy-dx;

int d1=2*dy;

int d2=2*(dy-dx);

dc.SetPixel(x1,y1,color);

int x=x1;

int y=y1;

for(int i=1;i<=dx;i++)

{

x+=incX;

if(d<0)d+=d1;

else

{

y+=incY;

d+=d2;

}

dc.SetPixel(x,y,color);

}

}///

else

{///

int d=2*dx-dy;

int d1=2*dx;

int d2=2*(dx-dy);

dc.SetPixel(x1,y1,color);

int x=x1;

int y=y1;

for(int i=1;i<=dy;i++)

{

y+=incY;

if(d<0)d+=d1;

else

{

x+=incX;

d+=d2;

}

dc.SetPixel(x,y,color);

}

}///

}