Приложение 6. Процедуры заливки области В данном приложении приведены три процедуры заливки гранично-определенной области с затравкой. Первая процедура - V_FAB4R реализует рекурсивный алгоритм заполнения для 4-х связной области. Вторая процедура - V_FAB4 реализует итеративный алгоритм заполнения для 4-х связной области. Характерная особенность таких алгоритмов - очень большие затраты памяти под рабочий стек и многократное дублирование занесения пикселов. Характерные значения для размера стека (см. ниже определение константы MAX_STK) около десяти тысяч байт при размере порядка 70×70 пикселов и очень сильно зависят от размеров заливаемой области, ее конфигурации и выбора начальной точки. Так, например, для заливки квадрата со стороной, равной 65 дискретам, и старте заливки из точки (20,20) относительно угла квадрата требуется 7938 байт для стека. Третья процедура - V_FAST реализует алгоритм построчного заполнения с затравкой гранично-определенной области, близкий к соответствующему алгоритму из [3]. Отличительная черта таких алгоритмов - большие объемы программного кода, небольшие затраты памяти под рабочий стек и практически отсутствующее дублирование занесения пикселов. Характерные значения для размера стека (см. ниже определение константы MAX_STK) около сотни байт. 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 */ Тест процедуры 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(); } V_FAB4 - итеративная заливка 4-x связной области /*----------------------------------------------------- V_FAB4 * Подпрограммы для заливки с затравкой гранично-определенной * области 4-х связным алгоритмом: * * Pop_Stk - Локальная подпрограмма. Извлекает координаты * пиксела из стека в глобальные скаляры xtek, ytek * * Push_Stk - Локальная подпрограмма. Заносит координаты * пиксела в стек * * V_FAB4 - собственно заливка гранично-определенной * области 4-х связным алгоритмом * * V_FA_SET - устанавливает количественные ограничения * для заливки */ #include #include #include #define MAX_GOR 2048 /* Разрешение дисплея по X */ #define MAX_VER 2048 /* Разрешение дисплея по Y */ #define MAX_STK 8192 /* Размер стека координат заливки */ static int gor_max= MAX_GOR; static int ver_max= MAX_VER; static int stk_max= MAX_STK; static int *pi_stk, *pn_stk; /* Указ стека заливки */ static int xtek, ytek; /* Координаты из стека */ static int stklen; /* Достигнутая глубина стека*/ /* только для отладочных */ /* измерений программы */ /*---------------------------------------------------- Pop_Stk * Извлекает координаты пиксела из стека в xtek, ytek * Возвращает 0/1 - нет/есть ошибки */ static int Pop_Stk () { register int otw; otw= 0; if (pi_stk <= pn_stk) ++otw; else { ytek= *--pi_stk; xtek= *--pi_stk; } return (otw); } /* Pop_Stk */ /*--------------------------------------------------- Push_Stk * Заносит координаты пиксела в стек * Возвращает -1/0 - нет места под стек/норма */ static int Push_Stk (x, y) register int x, y; { register int glu; if ((glu= pi_stk - pn_stk) >= stk_max) x= -1; else { *pi_stk++= x; *pi_stk++= y; x= 0; if (glu > stklen) stklen= glu; } return (x); } /* Push_Stk */ /*----------------------------------------------------- V_FAB4 * Заливка гранично-определенной области * 4-х связным алгоритмом * Возвращает: * -1 - нет места под стек * 0 - норма */ int V_FAB4 (grn_pix, new_pix, x_isx, y_isx) int grn_pix, new_pix, x_isx, y_isx; { register int pix, x, y, otw; otw= 0; /* Инициализация стека */ if ((pn_stk= (int *)malloc (stk_max)) == NULL) { --otw; goto all; } pi_stk= pn_stk; Push_Stk (x_isx, y_isx); /* Затравку в стек */ while (pn_stk < pi_stk) { /* Пока не исчерпан стек */ /* Выбираем пиксел из стека и красим его */ Pop_Stk (); if (getpixel (x= xtek, y= ytek) != new_pix) putpixel (x, y, new_pix); /* Проверяем соседние пикселы на необходимость закраски */ if ((pix= getpixel (++x, y)) != new_pix && pix != grn_pix) otw= Push_Stk (x, y); if ((pix= getpixel (--x, ++y)) != new_pix && pix != grn_pix) otw= Push_Stk (x, y); if ((pix= getpixel (--x, --y)) != new_pix && pix != grn_pix) otw= Push_Stk (x, y); if ((pix= getpixel (++x, --y)) != new_pix && pix != grn_pix) otw= Push_Stk (x, y); if (otw) break; } all: free (pn_stk); return (otw); } /* V_FAB4 */ /*--------------------------------------------------- V_FA_SET * Устанавливает количественные ограничения для заливки */ void V_FA_SET (x_resolution, y_resolution, stack_length) int x_resolution, y_resolution, stack_length; { if (x_resolution > 0 && x_resolution <= MAX_GOR) gor_max= x_resolution; if (y_resolution > 0 && y_resolution <= MAX_VER) ver_max= y_resolution; /* Кол байт координат, заносимых в стек м.б. только четным */ if (stack_length > 0) stk_max= stack_length & 0177776; } /* V_FA_SET */ Тест процедуры V_FAB4 /*-------------------------------------------------- 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_FA_SET (getmaxx()+1, getmaxy()+1, MAX_STK); stklen= 0; /* Занятое кол-во байт в стеке */ /* Заливка */ ii= V_FAB4 (grn, new, x_isx, y_isx); printf ("Answer= %d MaxStack=%d\n", ii, stklen); goto m1; all: closegraph(); } V_FAST - построчная заливка области /*----------------------------------------------------- V_FAST * Подпрограммы заливки области с затравкой * построчным алгоритмом: * * Pop_Stk - Локальная подпрограмма. Извлекает координаты * пиксела из стека в глобальные скаляры xtek,ytek * * Push_Stk - Локальная подпрограмма. Заносит координаты * пиксела в стек * * Get_Video - Локальная подпрограмма. Читает строку из * видеопамяти в глобальный буфер строки. * * Put_Video - Локальная подпрограмма. Копирует байты из * глобального буфера строки в видеопамять. * * Search - Локальная подпрограмма. Ищет затравочные * пикселы в строке видеопамяти, находящейся * в глобальном массиве. * * V_FAST - Собственно подпрограмма построчной заливки * гранично-определенной области * * V_FA_SET - Устанавливает количественные ограничения * для заливки */ #include #include #include #define MAX_GOR 2048 /* Разрешение дисплея по X */ #define MAX_VER 2048 /* Разрешение дисплея по Y */ #define MAX_STK 8192 /* Размер стека координат заливки */ static int gor_max= MAX_GOR; static int ver_max= MAX_VER; static int stk_max= MAX_STK; static int *pi_stk, *pn_stk; /* Указ стека заливки */ static int xtek, ytek; /* Координаты из стека */ static char *pc_video; /* Указ на буфер строки */ static int stklen; /* Достигнутая глубина стека*/ /* только для отладочных */ /* измерений программы */ /*---------------------------------------------------- Pop_Stk * Извлекает координаты пиксела из стека в xtek, ytek * Возвращает 0/1 - нет/есть ошибки */ static int Pop_Stk () { register int otw; otw= 0; if (pi_stk <= pn_stk) ++otw; else { ytek= *--pi_stk; xtek= *--pi_stk; } return (otw); } /* Pop_Stk */ /*--------------------------------------------------- Push_Stk * Заносит координаты пиксела в стек * Возвращает -1/0 - нет места под стек/норма */ static int Push_Stk (x, y) register int x, y; { register int glu; if ((glu= pi_stk - pn_stk) >= stk_max) x= -1; else { *pi_stk++= x; *pi_stk++= y; x= 0; if (glu > stklen) stklen= glu; } return (x); } /* Push_Stk */ /*-------------------------------------------------- Get_Video * В байтовый буфер строки, заданный глобальным * указателем pc_video, * читает из видеопамяти пикселы y-строки от xbg до xen * Возвращает 0/1 - нет/есть ошибки */ static int Get_Video (y, pcxbg, pcxen) int y; register char *pcxbg, *pcxen; { register int x; if (y>=0 && y x= pcxbg - pc_video; do *pcxbg++= getpixel (x++, y); while (pcxbg <= pcxen); y= 0; } else y= 1; return (y); } /* Get_Video */ /*-------------------------------------------------- Put_Video * Пикселы из буфера строки, начиная от указателя pxbg, * до указателя pxen пишет в y-строку видеопамяти * Возвращает 0/1 - нет/есть ошибки */ static int Put_Video (y, pxbg, pxen) int y; register char *pxbg, *pxen; { register int x; if (y>=0 && y x= pxbg - pc_video; do putpixel (x++, y, *pxbg++); while (pxbg <= pxen); y= 0; } else y= 1; return (y); } /* Put_Video */ /*----------------------------------------------------- Search * Ищет затравочные пикселы в yt-строке видеопамяти, * находящейся по указателю pc_video, начиная от * указателя pcl до указателя pcr * grn - код граничного пиксела * new - код, которым перекрашивается область * Возвращает: 0/1 - не найден/найден затравочный */ static int Search (yt, pcl, pcr, grn, new) int yt; char *pcl, *pcr; int grn, new; { register int pix; register char *pc; int x, otw; otw= 0; while (pcl <= pcr) { pc= pcl; /* Указ тек пиксела */ /* Поиск крайнего правого не закрашенного пиксела в строке */ while ((pix= *pc & 255) != grn && pix != new && pc ++pc; if (pc != pcl) { /* Найден закрашиваемый */ ++otw; x= pc - pc_video; /* Его координата в строке */ if (pc != pcr || pix == grn || pix == new) --x; Push_Stk (x, yt); } /* Продолжение анализа строки пока не достигнут прав пиксел */ pcl= pc; while (((pix= *pc & 255) == grn || pix==new) && pc ++pc; if (pc == pcl) ++pc; pcl= pc; } return (otw); } /* Search */ /*----------------------------------------------------- V_FAST * Построчная заливка с затравкой гранично-определенной * области * * int V_FAST (int grn_pix, int new_pix, int x_isx, int y_isx) * * Вход: * grn_pix - код граничного пиксела * new_pix - код заполняющего пиксела * x_isx - координаты затравки * y_isx * * Возвращает: * -2 - нет места под растровую строку * -1 - нет места под стек * 0 - норма * 1 - при чтении пикселов из видеопамяти в буферную * строки выход за пределы буферной строки * 2 - исчерпан стек при запросе координат пикселов * */ int V_FAST (grn_pix, new_pix, x_isx, y_isx) int grn_pix, new_pix, x_isx, y_isx; { register char *pcl; /* Указ левого пиксела в строке */ register char *pcr; /* Указ правого пиксела в строке */ int otw; otw= 0; /* Инициализация стека */ if ((pn_stk= (int *)malloc (stk_max)) == NULL) { --otw; goto all; } pi_stk= pn_stk; /* Заказ массива под растровую строку */ if ((pc_video= malloc (gor_max)) == NULL) { otw= -2; goto fre_stk; } Push_Stk (x_isx, y_isx); /* Затравку в стек */ /* Цикл заливки строк до исчерпания стека */ while (pi_stk > pn_stk) { /* Запрос координат затравки из стека */ if (Pop_Stk ()) {otw=2; break; } pcl= pcr= pc_video + xtek; /* Указ затравки */ /* Запрос полной строки из видеопамяти */ if (Get_Video (ytek, pc_video, pc_video+gor_max-1)) {otw= 1; break; } /* Закраска затравки и вправо от нее */ do *pcr++= new_pix; while ((*pcr & 255) != grn_pix); --pcr; /* Указ крайнего правого */ /* Закраска влево */ while ((*--pcl & 255) != grn_pix) *pcl= new_pix; ++pcl; /* Указ крайнего левого */ /* Занесение подправленной строки в видеопамять */ Put_Video (ytek, pcl, pcr); /* Поиск затравок в строках ytek+1 и ytek-1, * начиная с левого подинтервала, заданного pcl, до * правого подинтервала, заданного pcr */ if (!Get_Video (++ytek, pcl, pcr)) Search (ytek, pcl, pcr, grn_pix, new_pix); if (!Get_Video (ytek-= 2, pcl, pcr)) Search (ytek, pcl, pcr, grn_pix, new_pix); } free (pc_video); fre_stk: free (pn_stk); all: return (otw); } /* V_FAST */ /*--------------------------------------------------- V_FA_SET * Устанавливает количественные ограничения для заливки */ void V_FA_SET (x_resolution, y_resolution, stack_length) int x_resolution, y_resolution, stack_length; { if (x_resolution > 0 && x_resolution <= MAX_GOR) gor_max= x_resolution; if (y_resolution > 0 && y_resolution <= MAX_VER) ver_max= y_resolution; /* Кол байт координат, заносимых в стек м.б. только четным */ if (stack_length > 0) stk_max= stack_length & 0177776; } /* V_FA_SET */ Тест процедуры V_FAST /*-------------------------------------------------- FAST_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_FA_SET (getmaxx()+1, getmaxy()+1, MAX_STK); stklen= 0; /* Занятое кол-во байт в стеке */ /* Заливка */ ii= V_FAST (grn, new, x_isx, y_isx); printf ("Answer= %d MaxStack=%d\n", ii, stklen); goto m1; all: closegraph(); } <<<  Назад Вперед  >>>  1  2  3  4   8  Комментарии к статье  8 8  Обсудить в чате