Основные алгоритмы компьютерной графики

Процедуры заливки области

    0.17.1 V_FAB4R - рекурсивная заливка 4-x связной области
    0.17.2 Тест процедуры V_FAB4R
    0.17.3 V_FAB4 - итеративная заливка 4-x связной области
    0.17.4 Тест процедуры V_FAB4
    0.17.5 V_FAST - построчная заливка области
    0.17.6 Тест процедуры V_FAST

В данном приложении приведены три процедуры заливки гранично-определенной области с затравкой.

Первая процедура - 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 <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 */

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<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();
}

0.17.3 V_FAB4 - итеративная заливка 4-x связной области

/*----------------------------------------------------- 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 */

0.17.4 Тест процедуры 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_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();
}

0.17.5 V_FAST - построчная заливка области

/*----------------------------------------------------- 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 */

0.17.6 Тест процедуры 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<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();
}

к оглавлению

Знаете ли Вы, что любой разумный человек скажет, что не может быть улыбки без кота и дыма без огня, что-то там, в космосе, должно быть, теплое, излучающее ЭМ-волны, соответствующее температуре 2.7ºК. Действительно, наблюдаемое космическое микроволновое излучение (CMB) есть тепловое излучение частиц эфира, имеющих температуру 2.7ºK. Еще в начале ХХ века великие химики и физики Д. И. Менделеев и Вальтер Нернст предсказали, что такое излучение (температура) должно обнаруживаться в космосе. В 1933 году проф. Эрих Регенер из Штуттгарта с помощью стратосферных зондов измерил эту температуру. Его измерения дали 2.8ºK - практически точное современное значение. Подробнее читайте в FAQ по эфирной физике.

НОВОСТИ ФОРУМА

Рыцари теории эфира