Плоская машинная графика, страница 10

Пример. Разберем, как будет осуществляться закраска этим алгоритмом трапеции, приведенной на рис. 9. Обозначим 1 заданную затравку. Заносим точку 1 в стек, а затем в цикле извлекаем из стека. Тогда абсцисса точки 2 – это X_лев, а абсцисса точки 3 – это X_прав. После закраски горизонтального отрезка, содержащего точку 1, просматривается нижний отрезок для X_лев ≤ X ≤ X_прави точка 4 заносится в стек. Просматривается верхний отрезок для X_лев ≤ X ≤ X_прави точка 5 заносится в стек. Таким образом, закрашен один горизонтальный отрезок и две точки (сначала точка 4, а потом точка 5) занесены в стек. Так как стек не пуст, то извлекаем точку 5 (она была занесена в стек последней) и закрашиваем горизонтальный отрезок, содержащий эту точку. В этом случае абсцисса точки 6 – это X_лев, а абсцисса точки 5 – это X_прав. Просматриваем нижний отрезок для X_лев ≤ X ≤ X_прав, он весь закрашен. Просматриваем верхний отрезок для X_лев ≤ X ≤ X_прави заносим точку 7 в стек. Закрашены два горизонтальных отрезка, и две точки находятся в стеке – точка 4 и точка 7. Извлекаем точку 7 из стека (она была занесена в стек последней) и закрашиваем горизонтальный отрезок, содержащий эту точку. В этом случае абсцисса точки 8 – это X_лев, а абсцисса точки 7 – это X_прав. Отрезок, расположенный ниже, уже закрашен, а выше расположена граница области. В стеке осталась только одна точка – точка 4. Извлекаем ее из стека и закрашиваем горизонтальный отрезок, содержащий эту точку, от точки 9 (X_лев) до точки 10 (X_прав). Просматриваем нижний отрезок для  X_лев ≤ X ≤ X_прав, но он является границей области. Просматриваем для X_лев ≤ X ≤ X_правверхний отрезок, но он уже закрашен. В стек ничего не заносится. Стек пуст. Область закрашена.

Построчный алгоритм с затравкой с использованием рекурсии. Опишем теперь реализацию построчного алгоритма с затравкой с использованием рекурсии. Функция void flrec(int color, int X, int Y) использует следующий алгоритм.

Если точка (X, Y) закрашена, то производится возврат из функции. В противном случае в функции производятся такие действия: закрашивается максимальный горизонтальный связный отрезок, содержащий точку (X,Y). Пусть X_лев и X_прав – абсциссы концов этого отрезка. Просматриваются точки (x,Y-1) в пределах X_лев £ x £ X_прав и, в каждом незакрашенном максимальном подинтервале, лежащем в этих пределах, выбирается крайняя правая точка (x,Y-1) и производится вызов функции flrec(x,Y-1). Затем то же самое проделывается для точек (x,Y+1).

Для закраски достаточно вызвать в главной программе функцию flrec(color,x,y), если известна хотя бы одна незакрашенная точка заданной области.

Программа

#include <conio.h>

#include <graphics.h>

int xmax, xmin=0, ymax, ymin=0;

void flrec( int color, int x, int y)

{

int xleft=x, xright=x, yy;

if (getpixel(x,y)==color) return;

if (y>ymax||y<ymin) return;

if (x>xmax||x<xmin) return;

while (getpixel(xleft,y)!=color&& xleft>=xmin)

putpixel(xleft--, y, color);

xright++;

while (getpixel(xright,y)!=color&& xright<=xmax)

putpixel (xright++,y,color);

for (yy=y-1;yy<=y+1;yy+=2)

{

x=xleft+1;

while (x<xright&&x<xmax)

{

if (getpixel(x,yy)!=color) flrec(color,x,yy);

x++;

}

}

}

void main()

{

int gd=DETECT, gm;

initgraph (&gd, &gm, "");

moveto (280, 110);

lineto (250, 180);

lineto (50, 20);

lineto (280, 110);

xmax=getmaxx();ymax=getmaxy();

flrec(WHITE, 280, 110);

getch();

closegraph();

}

2.3. ПОСТРОЕНИЕ КРИВЫХ С ПОМОЩЬЮ МЕТОДА ПРИРАЩЕНИЙ

Метод приращений – это метод генерации точек на экране компьютера, близких к кривой, заданной уравнением f(x,y)=0. Этот метод был предложен в 60-е годы двадцатого века, для генерации точек окружности, а затем был обобщен на кривые второго порядка. В пп. 2.2 мы рассматривали частный случай этого метода, применяемый для генерации точек отрезка прямой. В дальнейшем полагаем, что нам задано уравнение кривой f(x,y)=0. В качестве начальной точки (x₀,y₀) выбирается точка, принадлежащая кривой. Все точки области, содержащей достаточно гладкую кривую f(x,y) можно разбить на три множества: множество точек принадлежащих кривой (для этих точек выполняется условие f(x,y)=0), множество точек области, для которых выполняется условие f(x,y)>0 и множество точек, для которых выполняется условие f(x,y)<0 (рис. 10).