Новосибирский Государственный Технический Университет. Факультет автоматики и вычислительной техники Кафедра вычислительной техники (специальность 220100). учебное пособие
| Вид материала | Учебное пособие |
| 0.16.4 Тестовая процедуры V_FP1 0.17 Приложение 6. Процедуры заливки области 0.17.1 V_FAB4R - рекурсивная заливка 4-x связной области 0.17.2 Тест процедуры V_FAB4R |
- Новосибирский Государственный Технический Университет. Факультет автоматики и вычислительной, 1650.9kb.
- Рабочая программа для специальности: 220400 Программное обеспечение вычислительной, 133.96kb.
- Государственный Технический Университет. Факультет: Автоматики и Вычислительной Техники., 32.46kb.
- Образования Республики Молдова Колледж Микроэлектроники и Вычислительной Техники Кафедра, 113.64kb.
- Постоянное развитие и углубление профессиональных навыков в области информационных, 54.56kb.
- «Программное обеспечение вычислительной техники и автоматизированных систем», 1790.14kb.
- Задачи дисциплины: -изучение основ вычислительной техники; -изучение принципов построения, 37.44kb.
- Лекция №2 «История развития вычислительной техники», 78.1kb.
- Система контроля и анализа технических свойств интегральных элементов и устройств вычислительной, 582.84kb.
- Московский государственный инженерно-физический институт (технический университет), 947.05kb.
0.16.4 Тестовая процедуры V_FP1
/*---------------------------------------------- main V_FP1 */
float Px[MAXARR] = {
0.0,200.0,200.0,250.0,270.0,270.0,210.0,210.0,230.0,230.0
};
float Py[MAXARR] = {
0.0,200.0,250.0,250.0,230.0,200.0,210.0,230.0,230.0,210.0
};
void main (void)
{
int ii, kol, grn, new, entry;
int gdriver = DETECT, gmode;
kol= 5; /* Кол-во вершин */
grn= 11; /* Код пикселов границы */
new= 14; /* Код заливки */
entry= 1;
initgraph(&gdriver, &gmode, "c:\tc\bgi");
if ((ii= graphresult()) != grOk) {
printf ("Err=%d\n", ii); goto all;
}
m0:goto m2;
m1:++entry;
printf("Vertexs, boundary_pixel, pixel= (%d %d %d) ? ",
kol, grn, new);
scanf ("%d%d%d", &kol, &grn, &new);
if (kol < 0) goto all;
for (ii=1; ii<=kol; ++ii) {
printf ("Px[%d], Py[%d] = ? ", ii, ii);
scanf ("%d%d", &Px[ii], &Py[ii]);
}
m2:
setbkcolor(0); /* Очистка экрана */
cleardevice();
/* Заливка */
V_FP1 (new, kol, Px, Py);
/* Построение границы */
setcolor (grn);
for (ii= 1; ii
line (Px[ii], Py[ii], Px[ii+1], Py[ii+1]);
line (Px[kol], Py[kol], Px[1], Py[1]);
/* При первом входе строится квадратик дырки */
if (!entry) {
for (ii=kol+1; ii
line (Px[ii], Py[ii], Px[ii+1], Py[ii+1]);
line (Px[kol+4], Py[kol+4], Px[kol+1], Py[kol+1]);
}
goto m1;
all:
closegraph();
}
0.17 Приложение 6. Процедуры заливки области
В данном приложении приведены три процедуры заливки гранично-определенной области с затравкой.
Первая процедура - V_FAB4R реализует рекурсивный алгоритм заполнения для 4-х связной области соответствующий алгоритму, помещенному в [4].
Вторая процедура - V_FAB4 реализует итеративный алгоритм заполнения для 4-х связной области близкий к алгоритму, помещенному в [3].
Характерная особенность таких алгоритмов - очень большие затраты памяти под рабочий стек и многократное дублирование занесения пикселов. Характерные значения для размера стека (см. ниже определение константы MAX_STK) около десяти тысяч байт при размере порядка 70×70 пикселов и очень сильно зависят от размеров заливаемой области, ее конфигурации и выбора начальной точки. Так, например, для заливки квадрата со стороной, равной 65 дискретам, и старте заливки из точки (20,20) относительно угла квадрата требуется 7938 байт для стека.
Третья процедура - V_FAST реализует алгоритм построчного заполнения с затравкой гранично-определенной области, близкий к соответствующему алгоритму из [3]. Отличительная черта таких алгоритмов - большие объемы программного кода, небольшие затраты памяти под рабочий стек и практически отсутствующее дублирование занесения пикселов. Характерные значения для размера стека (см. ниже определение константы MAX_STK) около сотни байт.
0.17.1 V_FAB4R - рекурсивная заливка 4-x связной области
/*---------------------------------------------------- V_FAB4R
* Подпрограммы для заливки с затравкой гранично-определенной
* области 4-х связным алгоритмом:
*
* V_FAB4R - заливка гранично-определенной
* области 4-х связным алгоритмом
*/
#include
#include
#define MAX_GOR 2048 /* Разрешение дисплея по X */
#define MAX_VER 2048 /* Разрешение дисплея по Y */
static int gor_max= MAX_GOR;
static int ver_max= MAX_VER;
/*---------------------------------------------------- V_FAB4R
* Заливка гранично-определенной области
* 4-х связным алгоритмом
*/
void V_FAB4R (grn_pix, new_pix, x_isx, y_isx)
int grn_pix, new_pix, x_isx, y_isx;
{
if (getpixel (x_isx, y_isx) != grn_pix &&
getpixel (x_isx, y_isx) != new_pix)
{
putpixel (x_isx, y_isx, new_pix);
V_FAB4R (grn_pix, new_pix, x_isx+1, y_isx);
V_FAB4R (grn_pix, new_pix, x_isx, y_isx+1);
V_FAB4R (grn_pix, new_pix, x_isx-1, y_isx);
V_FAB4R (grn_pix, new_pix, x_isx, y_isx-1);
}
} /* V_FAB4 */
0.17.2 Тест процедуры V_FAB4R
/*-------------------------------------------------- FAB4_MAIN
*/
void main (void)
{
int ii, kol, grn, new, entry;
int x_isx, y_isx;
int gdriver = DETECT, gmode;
int Px[256] = {200,200,250,270,270,210,210,230,230};
int Py[256] = {200,250,250,230,200,210,230,230,210};
kol= 5; /* Кол-во вершин */
grn= 11; /* Код пикселов границы */
new= 14; /* Код заливки */
x_isx= 240; /* Координаты затравки */
y_isx= 240;
entry= 0;
initgraph(&gdriver, &gmode, "c:\tc\bgi");
if ((ii= graphresult()) != grOk) {
printf ("Err=%d\n", ii); goto all;
}
m0:goto m2;
m1:++entry;
printf("Vertexs, boundary_pixel, new_pixel= (%d %d %d) ? ",
kol, grn, new);
scanf ("%d%d%d", &kol, &grn, &new);
if (kol < 0) goto all;
for (ii=0; ii
printf ("Px[%d], Py[%d] = ? ", ii, ii);
scanf ("%d%d", &Px[ii], &Py[ii]);
}
printf ("X,Y isx= (%d %d) ? ", x_isx, y_isx);
scanf ("%d%d", &x_isx, &y_isx);
m2:
setbkcolor(0);
cleardevice();
/* Построение границы */
setcolor (grn);
for (ii= 0; ii
line (Px[ii], Py[ii], Px[ii+1], Py[ii+1]);
line (Px[kol-1], Py[kol-1], Px[0], Py[0]);
/* При первом входе строится квадратик дырки */
if (!entry) {
for (ii= kol; ii
line (Px[ii], Py[ii], Px[ii+1], Py[ii+1]);
line (Px[kol+3], Py[kol+3], Px[kol], Py[kol]);
}
/* Заливка */
V_FAB4R (grn, new, x_isx, y_isx);
goto m1;
all:
closegraph();
}