В данном приложении приведены три процедуры заливки гранично-определенной области с затравкой.
Первая процедура - V_FAB4R реализует рекурсивный алгоритм заполнения для 4-х связной области соответствующий алгоритму, помещенному в [4].
Вторая процедура - V_FAB4 реализует итеративный алгоритм заполнения для 4-х связной области близкий к алгоритму, помещенному в [3].
Характерная особенность таких алгоритмов - очень большие затраты памяти под рабочий стек и многократное дублирование занесения пикселов. Характерные значения для размера стека (см. ниже определение константы MAX_STK) около десяти тысяч байт при размере порядка 70×70 пикселов и очень сильно зависят от размеров заливаемой области, ее конфигурации и выбора начальной точки. Так, например, для заливки квадрата со стороной, равной 65 дискретам, и старте заливки из точки (20,20) относительно угла квадрата требуется 7938 байт для стека.
Третья процедура - V_FAST реализует алгоритм построчного заполнения с затравкой гранично-определенной области, близкий к соответствующему алгоритму из [3]. Отличительная черта таких алгоритмов - большие объемы программного кода, небольшие затраты памяти под рабочий стек и практически отсутствующее дублирование занесения пикселов. Характерные значения для размера стека (см. ниже определение константы MAX_STK) около сотни байт.
/*---------------------------------------------------- V_FAB4R * Подпрограммы для заливки с затравкой гранично-определенной * области 4-х связным алгоритмом: * * V_FAB4R - заливка гранично-определенной * области 4-х связным алгоритмом */ #include <graphics.h> #include <stdio.h> #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 */
/*-------------------------------------------------- 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<kol; ++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<kol-1; ++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<kol+3; ++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-х связным алгоритмом: * * Pop_Stk - Локальная подпрограмма. Извлекает координаты * пиксела из стека в глобальные скаляры xtek, ytek * * Push_Stk - Локальная подпрограмма. Заносит координаты * пиксела в стек * * V_FAB4 - собственно заливка гранично-определенной * области 4-х связным алгоритмом * * V_FA_SET - устанавливает количественные ограничения * для заливки */ #include <alloc.h> #include <graphics.h> #include <stdio.h> #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 */
/*-------------------------------------------------- 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<kol; ++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<kol-1; ++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<kol+3; ++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 * Подпрограммы заливки области с затравкой * построчным алгоритмом: * * Pop_Stk - Локальная подпрограмма. Извлекает координаты * пиксела из стека в глобальные скаляры xtek,ytek * * Push_Stk - Локальная подпрограмма. Заносит координаты * пиксела в стек * * Get_Video - Локальная подпрограмма. Читает строку из * видеопамяти в глобальный буфер строки. * * Put_Video - Локальная подпрограмма. Копирует байты из * глобального буфера строки в видеопамять. * * Search - Локальная подпрограмма. Ищет затравочные * пикселы в строке видеопамяти, находящейся * в глобальном массиве. * * V_FAST - Собственно подпрограмма построчной заливки * гранично-определенной области * * V_FA_SET - Устанавливает количественные ограничения * для заливки */ #include <alloc.h> #include <graphics.h> #include <stdio.h> #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<ver_max && pcxbg<=pcxen) { 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<ver_max && pxbg<=pxen) { 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<pcr) ++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<pcr) ++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 */
/*-------------------------------------------------- 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<kol; ++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<kol-1; ++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<kol+3; ++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(); }
Релятивисты и позитивисты утверждают, что "мысленный эксперимент" весьма полезный интрумент для проверки теорий (также возникающих в нашем уме) на непротиворечивость. В этом они обманывают людей, так как любая проверка может осуществляться только независимым от объекта проверки источником. Сам заявитель гипотезы не может быть проверкой своего же заявления, так как причина самого этого заявления есть отсутствие видимых для заявителя противоречий в заявлении.
Это мы видим на примере СТО и ОТО, превратившихся в своеобразный вид религии, управляющей наукой и общественным мнением. Никакое количество фактов, противоречащих им, не может преодолеть формулу Эйнштейна: "Если факт не соответствует теории - измените факт" (В другом варианте " - Факт не соответствует теории? - Тем хуже для факта").
Максимально, на что может претендовать "мысленный эксперимент" - это только на внутреннюю непротиворечивость гипотезы в рамках собственной, часто отнюдь не истинной логики заявителя. Соответсвие практике это не проверяет. Настоящая проверка может состояться только в действительном физическом эксперименте.
Эксперимент на то и эксперимент, что он есть не изощрение мысли, а проверка мысли. Непротиворечивая внутри себя мысль не может сама себя проверить. Это доказано Куртом Гёделем.
Понятие "мысленный эксперимент" придумано специально спекулянтами - релятивистами для шулерской подмены реальной проверки мысли на практике (эксперимента) своим "честным словом". Подробнее читайте в FAQ по эфирной физике.