Алгоритм с запоминанием точек границы в стек. Этот алгоритм предназначен генерации точек выпуклого многоугольника. Определим отношение "<" (лексикографического) порядка на множестве точек плоскости следующим образом: (x,y)<(x’,y’), если y<y’ или y=y’ и x>x’. Будем обходить против часовой стрелки точки границы многоугольника, начиная с вершины многоугольника, наименьшей среди всех его вершин относительно введенного отношения порядка. При увеличении значения ординаты точки, координаты предыдущей точки запоминаются в стек. Если же ордината Y уменьшилась, то извлекается точка из стека и соединяется с текущей точкой. Поскольку величина Y изменяется на ±1, достаточно хранить в стеке только координату X. Ниже мы рассмотрим реализацию, при которой стек представляется в виде массива (пример 2.1).
Опишем этот алгоритм подробнее. Для его реализации нужно знать или уметь вычислять координаты всех точек границы многоугольника. Это является существенным недостатком алгоритма. Многоугольник будем обходить против часовой стрелки. В качестве начальной точки (x0,y0) выбирается вершина многоугольника, имеющая наименьшую координату по Y. Если таких вершин несколько, то из них выбирается вершина с наибольшей координатой по X.
Зная начальную точку (x0,y0) и направление обхода границы многоугольника, вычисляем координаты следующей точки (x1,y1).Точку (x1,y1) назовем текущей точкой (xтек,yтек). Сравним текущую точку (xтек,yтек) и предыдущую точку (xпред,yпред). Возможны три случая:
· yтек > yпред, в этом случае xпред заносим в стек и переходим к следующей точке границы многоугольника;
· yтек = yпред, в этом случае переходим к следующей точке границы многоугольника;
· yтек < yпред, в этом случае извлекаем одно число из стека xстек и проводим горизонтальный отрезок прямой, соединяющий точки (xстек,yтек) и (xтек,yтек), затем переходим к следующей точке границы.
Заполнение закончено, когда просмотрены все стороны многоугольника.
Замечание. Алгоритм можно модифицировать таким образом, чтобы заполнение прекращалось, когда стек исчерпан (заполнение происходит до тех пор, пока стек не пуст). Отметим, что границу многоугольника можно обходить и по часовой стрелке.
Пример 2.1. Построение границы многоугольника с использованием алгоритма Брезенхема и закраски многоугольника с использованием алгоритма с запоминанием точек границы в стек.
Программа
#include <stdio.h>
#include <math.h>
#include <conio.h>
#include <graphics.h>
#define pop() stx[—deep]
#define push(x) stx[deep++]=x
void horline (int y, int x0, int x1)
{
int i;
if (x0>x1) {i=x1; x1=x0; x0=i;}
for (i=x0; i<=x1; i++) putpixel(i, y,15 );
}
void fl(int *arx, int *ary, int dimar)
{
int deep=0;
int stx[1000];
int i0, iglob, ix0, iy0, ix1, iy1;
int ymin;
int ix, iy, deltax , deltay, esh, sx, sy;
int temp, swab, i;
//Находим наименьший ary[i]
i0=0; ymin=ary[0];
for (i=0;i<dimar;i++)
if (ary[i]<ymin) {i0=i; ymin=ary[i];}
//на отрезке (i, i+1) проводим прямую линию от
//arx[i], ary[i] до arx[i+1], ary[i+1]
iglob=i0;
do
{
ix0=arx[iglob]; iy0=ary[iglob];
iglob++; if (iglob==dimar) iglob=0;
ix1=arx[iglob]; iy1=ary[iglob];
//Основной цикл — вывод отрезка по алгоритму Брезенхема
ix=ix0; iy=iy0;
deltax=abs(ix1-ix0);
deltay=abs(iy1-iy0);
if (ix1-ix0>=0) sx=1;
else sx=-1;
if (iy1-iy0>=0) sy=1;
else sy = -1;
if (deltay>deltax)
{
temp=deltax;
deltax=deltay;
deltay=temp;
swab=1;
}
else
swab = 0;
esh=2*deltay-deltax;
for (i=1;i<=deltax;i++)
{
while (esh>=0)
{
if (swab==1) ix = ix + sx;
else
{
iy=iy+sy;
if (sy==1) push (ix);
if (sy==-1)
{
temp=pop();
horline(iy,ix,temp);
}
}
esh=esh-2*deltax;
}
if (swab==1)
{
iy=iy+sy;
if (sy==1) push(ix);
if (sy==-1)
{
temp=pop();
horline(iy,ix,temp);
}
}
else ix=ix+sx;
esh=esh+2*deltay;
}
}
while (i0!=iglob);
}
main()
{
int gd=0, gm;
int arx[3]={600,300,100};
int ary[3]={390,450,120};
initgraph (&gd, &gm, "C:\BC\BGI");
fl(arx,ary,3);
getch();
closegraph() ;
}
Алгоритм, использующий режим вывода прямых XOR_PUT. Этот алгоритм является одним из самых эффектных алгоритмов заполнения. Сначала закрашивается область, большая чем нужно, а затем «лишнее» аккуратно «стирается» (рис. 7).
Рис. 7. Алгоритм заполнения с установкой режима XOR_PUT
Осуществляется это с помощью режима XOR_PUT. После вызова функции setwritemode(XOR_PUT) для каждой генерируемой точки отрезка цвет отрезка складывается побитно по модулю 2 с цветом соответствующего пиксела экрана, и результат служит новым цветом этого пиксела. Таким образом, если после установки режима XOR_PUT на экран вывести два раза один и тот же отрезок любого цвета, то в результате сначала отрезок выведется на экран, а потом «сотрется».
Для реализации этого алгоритма нужно знать или уметь вычислять координаты всех точек границы области. Это является существенным недостатком алгоритма. Например, для заполнения многоугольника с установкой режима XOR_PUT нужно знать координаты всех вершин многоугольника и алгоритм генерации точек сторон многоугольника. В этом алгоритме просматриваются все точки границы области.
Так как в этом алгоритме сначала закрашивается область большая, чем нужно, а затем «лишнее» убирается, то время работы программы существенно зависит от
размеров дополнительной области, которая фактически закрашивается два раза. Для уменьшения размеров этой дополнительной области вводится перегородка – вертикальная линия на экране компьютера, расположенная справа (слева) от области (рис. 7). В самом простом случае перегородка – это правая граница экрана. Чем ближе перегородка к области, тем эффективнее алгоритм.
В качестве начальной точки можно взять любую точку области, но в случае многоугольника, удобнее начинать с какой-либо вершины многоугольника, а сам многоугольник рассматривать как набор вершин и сторон. В этом случае работа алгоритма прекращается, когда рассмотрены все стороны многоугольника.
Сформируем алгоритм для заполнения многоугольника.
1. Выбираем начальную точку (x0,y0) – одну из вершин многоугольника.
2. Выбирается направление обхода границы (например, по часовой стрелке).
3. Устанавливается режим XOR_PUT.
4. Рассматриваем следующую точку границы многоугольника в выбранном направлении обхода, и называем ее текущей (xтек,yтек). Сравниваем текущую точку (xтек,yтек) и предыдущую точку (xпред,yпред). Возможны три случая:
· а) yтек>yпред, в этом случае проводим горизонтальный отрезок от точки (xтек,yтек) до перегородки с помощью функции line и переходим к следующей точке границы многоугольника;
· б) yтек=yпред, в этом случае переходим к следующей точке границы многоугольника;
· в) yтек<yпред, в этом случае проводим горизонтальный отрезок от точки (xпред,yпред) до перегородки с помощью функции line и переходим к следующей точке границы многоугольника.
5. Заполнение закончено, когда просмотрены все стороны многоугольника.
Отметим, что режим XOR_PUT действует только на кусочно-линейном примитиве (line, lineto, linerel) и не действует на putpixel и bar. Поэтому горизонтальные отрезки нужно выводить с помощью функции line, а не функции putpixel. Если же в качестве элемента изображения рассматривается не пиксел, а закрашенный квадрат со стороной в K (K>1) пикселов, то предварительно нужно подготовить функцию, в которой строится такой закрашенный квадрат с помощью функции line.
Рис. 8. Алгоритм заполнения с установкой режима XOR_PUT
Пример 2.2. Закрасить квадрат со стороной 40 пикселов, используя алгоритм заполнения с установкой режима XOR_PUT. Левой верхней вершиной квадрата является точка с координатами (20,20). В качестве перегородки использовать вертикальную линию x=80.
Программа
#include<conio.h>
#include<graphics.h>
#include<math.h>
#include<dos.h>
//xпред, yпред
int oldx,oldy;
//Функция сравнивает текущею точку обхода периметра
//с предыдущей и выполняет соответствующие действия
//в качестве параметров передаются координаты текущей точки
XorLine(int x, int y)
{
if (y>oldy) line(x,y,80,y);
if (y<oldy) line(oldx,oldy,80,oldy);
oldx=x; oldy=y; //текущая точка становится предыдущей
}
main()
{
int i, gdriver=DETECT, gmode;
//иницализация графического режима
initgraph (&gdriver, &gmode, "D:\BC\BGI");
setcolor(12); //установка красного цвета
rectangle(19,20,60,61); //рисование периметра квадрата (необязательно)
line(80,20,80,60); //рисование перегородки (необязательно)
setcolor(15); //установка белого цвета
setwritemode(XOR_PUT); //установка режима вывода XOR_PUT
oldx=20; oldy=20; //инициализируем предыдущие координаты
//проход по левой стороне квадрата с задержкой
for(i=20;i<=60;i++) {XorLine(20,i); delay(200);}
//проход по нижней стороне квадрата
for(i=20;i<=60;i++) XorLine(i,60);
//проход по правой стороне квадрата с задержкой
for(i=60;i>=20;i—) {XorLine(60,i); delay(200);}
//проход по верхней стороне квадрата с задержкой
for(i=60;i>=20;i—) XorLine(i,20);
getch(); //Ожидание нажатия клавиши
closegraph(); //Выключение графического режима
}
Результат работы программы приведен на рис. 8.
Затравочное заполнение области. Будем называть область экрана связной, если любые ее две точки можно соединить путем, состоящим из вертикальных и горизонтальных единичных отрезков, с концами, лежащими в этой области. Затравкой, или затравочной точкой, называется произвольная незакрашенная точка области, не принадлежащая границе. В методах затравочного заполнения вначале известна некоторая затравка, принадлежащая области. Далее изучаются точки, соседние с затравкой. Если соседняя точка не закрашена и не лежит на границе, то она становится новой затравкой и поиск продолжается.
Достоинством всех затравочных алгоритмов заполнения области является то, что для закраски области с произвольной границей достаточно знать цвет границы и координаты одной незакрашенной точки области, не принадлежащей границе. Но затравочные алгоритмы различны по эффективности. Вначале рассмотрим самый простой, но и наименее эффективный алгоритм закраски – простой алгоритм заполнения. В силу своей неэффективности, этот алгоритм не используется на практике, но именно на примере этого алгоритма проще всего объяснить суть затравочных алгоритмов.
Простой алгоритм заполнения. Задана область и произвольная затравка (X,Y). Вначале точка (X,Y) помещается в стек. Затем, пока стек не пуст, последовательно вынимается точка из стека и заносится в (X,Y), и если эта точка не закрашена (что может случиться, если точка попала в стек второй раз), то производятся такие действия:
закрашивается точка (X,Y),
если (X+1,Y) — затравка, то (X+1,Y) запоминается в стек,
если (X,Y+1) — затравка, то (X,Y+1) запоминается в стек,
если (X-1,Y) — затравка, то (X-1,Y) запоминается в стек,
если (X,Y-1) — затравка, то (X,Y-1) запоминается в стек.
Алгоритм неэффективен, т.к. предполагает неоднократную обработку одних и тех же точек области. Отметим, что, если область достаточно велика, то возможно переполнение стека.
Простой алгоритм заполнения с затравкой с использованием рекурсии. Используя рекурсию, алгоритм заполнения с затравкой можно реализовать следующим образом:
void fl ( int x, int y )
{
if (getpixel(x,y) return;
putpixel(x,y,WHITE);
fl(x-1,y); fl(x,y+1); fl(x+1,y); fl(x,y-1);
}
Замечания. Поскольку точки области являются вершинами графа, ребрами которого служат горизонтальные и вертикальные единичные отрезки, лежащие в области, простой алгоритм с затравкой допускает такое обобщение. Пусть задан произвольный граф. Запоминаем в стек произвольную вершину графа. Затем в цикле, пока стек не пуст, извлекается точка из стека, эта точка закрашивается и все смежные незакрашенные вершины запоминаются в стек.
Построчный алгоритм с затравкой. На практике для закраски области чаще всего используются построчные алгоритмы с затравкой. Они являются модификациями простого алгоритма с затравкой, в которых закраска области осуществляется горизонтальными отрезками.
Координаты точек области — целые числа, стало быть, область можно разбить на максимальные горизонтальные связные отрезки. Рассмотрим множество всех таких отрезков. Соединяя всякие два элемента этого множества, соответствующие отрезкам, содержащим примыкающие друг к другу части ненулевой длины, получим некоторый граф. К этому графу можно применить описанный выше алгоритм с затравкой. Вместо максимального связного отрезка в стеке запоминаются координаты произвольной точки этого отрезка.
Вначале затравка (X, Y) запоминается в стек. Затем в цикле, пока стек не пуст, производятся следующие действия. Извлекается точка из стека и закрашивается весь максимальный горизонтальный связный отрезок области, содержащий эту точку. Во время закраски вычисляются наименьшая Xлев и наибольшая Xправ абсциссы точек этого отрезка. Просматриваются слева направо точки (X,Y-1) в пределах Xлев£X£Xправ. Определяется, есть ли среди этих точек незакрашенные. Если такие точки есть, то в каждом связном подинтервале множества таких точек выбирается крайний правый пиксел и запоминается в стек. Аналогичные действия производятся с точками (X,Y+1). Заметим, что после каждого извлечения из стека, действия внутри цикла целесообразно производить только в тех случаях, когда извлеченная точка снова является затравкой (то есть, не закрашена).
Ниже приведена программа, реализующая этот алгоритм.
Программа
#include <stdio.h>
#include <conio.h>
#include <graphics.h>
#define pop() x=stx[—deep];y=sty[deep]
#define push(a,b) stx[deep]=a;sty[deep++]=b
int deep=0, stx[1000], sty[1000] ;
int xmax=640, xmin=0, ymax=480, ymin=0 ;
void flstr(int color, int x, int y)
{
int tempx;
int xleft, xright;
int xenter;
int flag, i ;
push(x,y) ;
while(deep>0)
{
pop() ;
if(getpixel(x,y)!=color)
{
putpixel(x,y,color) ;
tempx=x; //сохранение текущей коорд. x
x++; //перемещение вправо
while(getpixel(x,y)!=color && x<=xmax)
putpixel(x++, y, color);
xright=x-1;
x=tempx; x—; //перемещение влево
while(getpixel(x,y)!=color && x>=xmin)
putpixel(x—, y, color);
xleft=x+1;
x=tempx;
for(i=0;i<2;i++)
{
//при i=0 проверяем нижнюю,
//а при i=1 — верхнюю строку
if(y<ymax && y>ymin)
{
x=xleft; y+=1-i*2;
while(x<=xright)
{
flag=0;
while(getpixel(x,y)!=color && x<xright)
{
if(flag==0) flag=1;
x++;
}
if (flag==1)
{
if(x==xright &&
getpixel(x,y)!=color)
{
push(x,y);
}
else
{push(x-1,y);}
flag=0;
}
xenter=x;
while(getpixel(x,y)==color && x<xright)
x++;
if(x==xenter) x++;
}
}
y— ;
}
}
}
}
main()
{
int gd=0 , gm;
initgraph (&gd, &gm, "C:\BC\BGI") ;
moveto (630, 390);
lineto (600, 460);
lineto (400, 200);
lineto (630, 390);
xmin=320;ymin=150;
flstr (15, 440, 240);
getch();
closegraph();
}
Опишем этот алгоритм для более простого случая, а именно для выпуклого многоугольника. Известна затравка (X,Y) и цвет границы. Вначале затравка (X,Y) запоминается в стек. Затем, в цикле, пока стек не пуст, извлекается одна точка из стека и заносится в (X,Y). Если (X,Y) не закрашена, то закрашивается максимальный горизонтальный отрезок области, содержащий точку (X,Y). Во время закраски вычисляются Xлев – наименьшая абсцисса этого отрезка (левая граница) и Xправ – наибольшая абсцисса этого отрезка (правая граница). Затем просматриваются слева направо точки (X, Y-1) в пределах Xлев≤ X≤Xправ. Среди этих точек могут оказаться точки границы или закрашенные точки. Определяем, есть ли среди этих точек незакрашенные. Если такие точки есть, то среди незакрашенных точек выбирается крайняя правая точка и заносится в стек. Если незакрашенная точка единственная, то она и заносится в стек. Аналогичные действия производятся с точками (X, Y+1).
Пример. Разберем, как будет осуществляться закраска этим алгоритмом трапеции, приведенной на рис. 9. Обозначим 1 заданную затравку. Заносим точку 1 в стек, а затем в цикле извлекаем из стека. Тогда абсцисса точки 2 – это Xлев, а абсцисса точки 3 – это Xправ. После закраски горизонтального отрезка, содержащего точку 1, просматривается нижний отрезок для Xлев≤ X≤Xправ и точка 4 заносится в стек.
Рис. 9. Построчная закраска с затравкой
Просматривается верхний отрезок для 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(X,Y), если известна хотя бы одна незакрашенная точка заданной области.
Программа
#include <stdio.h>
#include <conio.h>
#include <graphics.h>
int xmax=640, xmin=0, ymax=480, 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++;
}
}
}
main()
{
int gd=0, gm;
initgraph (&gd, &gm, "D:\BC\BGI");
moveto(630, 390);
lineto(600, 460);
lineto(400, 200);
lineto(630, 390);
xmin=300;ymin=150;
flrec(15, 435, 240);
getch();
closegraph();
}