Пример. Разберем, как
будет осуществляться закраска этим алгоритмом трапеции, приведенной на рис. 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. В качестве начальной точки (x0,y0)
выбирается точка, принадлежащая кривой. Все точки области, содержащей
достаточно гладкую кривую f(x,y) можно разбить на три множества:
множество точек принадлежащих кривой (для этих точек выполняется условие f(x,y)=0),
множество точек области, для которых выполняется условие f(x,y)>0 и
множество точек, для которых выполняется условие f(x,y)<0 (рис. 10).
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.