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

Процедуры генерации отрезков

Здесь приведены тексты соответствующих процедур с пояснениями и тестовая программа. Процедуры позволяют генерировать вектора в любом квадранте с использованием алгоритмов несимметричного цифрового дифференциального анализатора и Брезенхема, а также построения ребра, ограничивающего заполненный многоугольник, модифицированным алгоритмом Брезенхема, уменьшающим лестничный эффект.

Предусмотрена возможность задания атрибутов формируемых отрезков - номер цвета и размер пиксела, используемого при формировании отрезков.

В тестовой программе предусмотрено, что при наличии SVGA-адаптера он может использоваться как в обычном режиме, так и в режиме до 1024x768 точек с 256 цветами.

/*------------------------------------------------- V_VECTOR.C
 * Подпрограммы генерации векторов
 */

#include <graphics.h>
#include <stdio.h>

#define PutMay putpixel

static int Pix_X= 3,    /* Размер пиксела по X  */
           Pix_Y= 3,    /* Размер пиксела по Y  */
           Pix_C= 64,   /* Нач. индекс цвета пиксела */
           Pix_V= 64;   /* Количество оттенков  */

/*--------------------------------------------------- PutPixLn
 * Подпрограмма заносит "кpупный" пиксел в позицию X,Y
 * Точка (0, 0) - левый верхний угол экрана.
 * Размеры пиксела задается фактическими паpаметpами x и y.
 * Hомер оттенка пиксела задается фактическим паpаметpом c.
 */

void PutPixLn (int x, int y, int c)
{  int  ii, jj, kk;
   x *= Pix_X;  y *= Pix_Y;
   ii= Pix_Y;
   while (--ii >= 0) {
      jj= Pix_X;  kk= x;
      while (--jj >= 0) PutMay (kk++, y, c);
      y++;
   }
}  /* PutPixLn */


/*--------------------------------------------------- V_setlin
 * Устанавливает атрибуты построения линий:
 * размер элементарного пиксела, индекс цвета, кол-во оттенков
 * Если размер <= 0, то он не меняется
 * Если атрибут цвета < 0, то он не меняется
 */
void V_setlin (sizex, sizey, colorindex, colorvalue)
int  sizex, sizey, colorindex;
{
   if (sizex > 0) Pix_X= sizex;
   if (sizey > 0) Pix_Y= sizey;
   if (colorindex >= 0) Pix_C= colorindex;
   if (colorvalue >= 0) Pix_V= colorvalue;
}  /* V_setlin */

/*-----------------------------------------------------  V_DDA
 * void V_DDA (int xn, int yn, int xk, int yk)
 *
 * Подпрограмма построения вектора из точки (xn,yn)
 * в точку (xk, yk) в первом квадранте методом
 * несимметричного цифрового дифференциального анализатора
 * с использованием только целочисленной арифметики.
 *
 * Обобщение на другие квадранты труда не составляет.
 *
 * Построение ведется от точки с меньшими  координатами
 * к точке с большими координатами с единичным шагом по
 * координате с большим приращением.
 *
 * Отдельно выделяется случай вектора с dx == dy
 *
 * Всего надо выдать пикселы в dx= xk - xn + 1 позиции
 * по оси X и в dy= yk - yn + 1 позиции по оси Y.
 *
 * Для определенности рассмотрим случай dx > dy
 *
 * При приращении X-координаты на 1 Y-координата должна
 * увеличиться на величину меньшую единицы и равную dy/dx.
 *
 * После того как Y-приращение станет больше или равно 1.0,
 * то Y-координату пиксела надо увеличить на 1, а из
 * накопленного приращения вычесть 1.0 и продолжить построения
 * Т.е. приращение Y на 1 выполняется при условии:
 * dy/dx + dy/dx + ... + dy/dx >= 1.0
 * Т.к. вычисления в целочисленной арифметике быстрее, то
 * умножим на dx обе части и получим эквивалентное условие:
 * dy + dy + ... + dy >= dx
 *
 * Эта схема и реализована в подпрограмме.
 *
 * При реализации на ассемблере можно избавиться от
 * большинства операторов внутри цикла while.
 * Для этого перед циклом надо домножить dy на величину,
 * равную 65536/dx.
 * Тогда надо увеличивать Y на 1 при признаке переноса
 * после вычисления s, т.е. операторы
 *       s= s + dy;
 *       if (s >= dx) { s= s - dx;  yn= yn + 1; }
 * заменяются командами ADD и ADC
 *
 */

void V_DDA (xn, yn, xk, yk)
int  xn, yn, xk, yk;
{  int  dx, dy, s;

/* Упорядочивание координат и вычисление приращений */
   if (xn > xk) {
      s= xn;  xn= xk;  xk= s;
      s= yn;  yn= yk;  yk= s;
   }
   dx= xk - xn;  dy= yk - yn;

/* Занесение начальной точки вектора */
   PutPixLn (xn, yn, Pix_C);

   if (dx==0 && dy==0) return;

/* Вычисление количества позиций по X и Y */
   dx= dx + 1;  dy= dy + 1;

/* Собственно генерация вектора */
   if (dy == dx) {                 /* Наклон == 45 градусов */
      while (xn < xk) {
         xn= xn + 1;
         PutPixLn (xn, xn, Pix_C);
      }
   } else if (dx > dy) {           /* Наклон <  45 градусов */
      s= 0;
      while (xn < xk) {
         xn= xn + 1;
         s= s + dy;
         if (s >= dx) { s= s - dx;  yn= yn + 1; }
         PutPixLn (xn, yn, Pix_C);
      }
   } else {                        /* Наклон >  45 градусов */
      s= 0;
      while (yn < yk) {
         yn= yn + 1;
         s= s + dx;
         if (s >= dy) { s= s - dy;  xn= xn + 1; }
         PutPixLn (xn, yn, Pix_C);
      }
   }
}  /* V_DDA */

/*-----------------------------------------------------  V_Bre
 * void V_Bre (int xn, int yn, int xk, int yk)
 *
 * Подпрограмма иллюстрирующая построение вектора из точки
 * (xn,yn) в точку (xk, yk) методом Брезенхема.
 *
 * Построение ведется от точки с меньшими  координатами
 * к точке с большими координатами с единичным шагом по
 * координате с большим приращением.
 *
 * В общем случае исходный вектор проходит не через вершины
 * растровой сетки, а пересекает ее стороны.
 * Пусть приращение по X больше приращения по Y и оба они > 0.
 * Для очередного значения X нужно выбрать одну двух ближайших
 * координат сетки по Y.
 * Для этого проверяется как проходит  исходный  вектор - выше
 * или ниже середины расстояния между ближайшими значениями Y.
 * Если выше середины,  то Y-координату  надо  увеличить на 1,
 * иначе оставить прежней.
 * Для этой проверки анализируется знак переменной s,
 * соответствующей разности между истинным положением и
 * серединой расстояния между ближайшими Y-узлами сетки.
 */

void V_Bre (xn, yn, xk, yk)
int  xn, yn, xk, yk;
{  int  dx, dy, s, sx, sy, kl, swap, incr1, incr2;

/* Вычисление приращений и шагов */
   sx= 0;
   if ((dx= xk-xn) < 0) {dx= -dx; --sx;} else if (dx>0) ++sx;
   sy= 0;
   if ((dy= yk-yn) < 0) {dy= -dy; --sy;} else if (dy>0) ++sy;
/* Учет наклона */
   swap= 0;
   if ((kl= dx) < (s= dy)) {
      dx= s;  dy= kl;  kl= s; ++swap;
   }
   s= (incr1= 2*dy)-dx; /* incr1 - констан. перевычисления */
                        /* разности если текущее s < 0  и  */
                        /* s - начальное значение разности */
   incr2= 2*dx;         /* Константа для перевычисления    */
                        /* разности если текущее s >= 0    */
   PutPixLn (xn,yn,Pix_C); /* Первый  пиксел вектора       */
   while (--kl >= 0) {
      if (s >= 0) {
         if (swap) xn+= sx; else yn+= sy;
         s-= incr2;
      }
      if (swap) yn+= sy; else xn+= sx;
      s+=  incr1;
      PutPixLn (xn,yn,Pix_C); /* Текущая  точка  вектора   */
   }
}  /* V_Bre */

/*----------------------------------------------------- V_BreM
 * void V_BreM (int xn, int yn, int xk, int yk)
 *
 * Подпрограмма иллюстрирующая построение ребра залитого
 * многоугольника из точки (xn,yn) в точку (xk,yk)
 * модифициpованным методом Брезенхема.
 *
 * Строки многоугольника от занесенного пиксела границы до xk
 * заполняются оттенком с максимальным номером.
 */

void V_BreM (xn, yn, xk, yk)
int  xn, yn, xk, yk;
{  int  dx, dy, sx, sy, kl, swap;
   long incr1, incr2;
   long s;              /* Текущее значение ошибки  */
   long s_max;          /* Макс значение ошибки     */
   int  color_tek;      /* Текущий номеp оттенка    */
   int  xt;

/* Вычисление приращений и шагов */
   sx= 0;
   if ((dx= xk-xn) < 0) {dx= -dx; --sx;} else if (dx>0) ++sx;
   sy= 0;
   if ((dy= yk-yn) < 0) {dy= -dy; --sy;} else if (dy>0) ++sy;
/* Учет наклона */
   swap= 0;
   if ((kl= dx) < (s= dy)) {dx= s;  dy= kl;  kl= s; ++swap;}
   s= (long)dx*(long)Pix_V; /* Hачальное значение ошибки    */
   incr1= 2l*(long)dy       /* Конст. перевычисления ошибки */
            *(long)Pix_V;   /* если текущее s < s_max       */
   incr2= 2l*s;             /* Конст. перевычисления ошибки */
                            /* если текущее s >= s_max      */
   s_max= incr2 - incr1;    /* Максимальное значение ошибки */
   color_tek= Pix_V;        /* Яpкость стаpтового пиксела   */
   if (dx)color_tek=(int)((((long)Pix_V*(long)dy)/(long)dx)/2l);
   PutPixLn (xn, yn, Pix_C+color_tek);      /* 1-й пиксел */
   while (--kl >= 0) {
      if (s >= s_max) {
         if (swap) xn+= sx; else yn+= sy;
         s-= incr2;
      }
      if (swap) yn+= sy; else xn+= sx;
      s+=  incr1;
      color_tek= Pix_V;
      if (dx) color_tek= s / dx /2;
      PutPixLn (xn,yn,Pix_C+color_tek);     /* Тек.пиксел */
/* Однотонная закраска строки многоугольника макс цветом  */
      xt= xn;
      while (++xt <= xk) PutPixLn (xt,yn,Pix_C+Pix_V-1);
   }
}  /* V_BreM */

/*================================================= T_VECTOR.C
 * ТЕСТ ГЕНЕРАЦИИ ВЕКТОРОВ
 *
 * Строит вектора из точки Xn,Yn в заданную
 * Программа запрашивает ввод четыpех чисел:
 * mode  = -2 - прекращение работы
 *         -1 - очистка экрана
 *          0 - вывод сетки
 *          1-7 построение вектоpа:
 *            1рр == 1 - по алгоритму ЦДА
 *            2рр == 1 - по алгоритму Брезенхема
 *            3рр == 1 - по модифиц. алгоритму Брезенхема
 *         иное значение - замена Xn,Yn на введенные Xk,Yk
 * atrib - атpибуты постpоения в виде десятичного числа
 *         из 8 цифр - PPСCCVVV:
 *         PP  - pазмеp элементаpного пиксела
 *         ССС - начальный номер оттенка
 *         VVV - количество оттенков
 * Xk    - конечная координата вектора
 * Yk
 */

#include "V_VECTOR.C"

#define MODE_256 1 /* 0/1 - обычный VGA/SVGA режим */

#if MODE_256
#   include "V_SVGA.C"
#endif

#include <conio.h>
#include <graphics.h>
#include <stdio.h>
#include <stdlib.h>

/*------------------------------------------------------- Grid
 * Строит сетку 10*10
 */

void Grid (int col)
{  int Xn,Yn,Xk,Yk;
   setcolor (col);
   Xn= 0;  Xk= getmaxx();
   Yn= 0;  Yk= getmaxy();
   while (Xn <= Xk) {line (Xn,Yn,Xn,Yk); Xn+= 10; }
   Xn= 0;
   while (Yn <= Yk) {line (Xn,Yn,Xk,Yn); Yn+= 10; }
}  /* Grid */

/*----------------------------------------- MAIN T_VECTOR.C */

void main (void)
{
   int  ii, jj,
        mode=1,           /* Режим pаботы              */
        Xn=0,Yn=0,        /* Координаты начала отрезка */
        Xk,Yk,            /* Координаты конца отрезка  */
        fon,              /* Индекс цвета фона         */
        col_beg, col_val, /* Атpибуты пикселов         */
        xpix, ypix,
        colgrid,          /* Цвет сетки                */
        col_lin= 200,     /* Цвет "точного" отрезка    */
        col_Bre= 201,     /* Цвет построения для ЦДА   */
        col_DDA= 202;     /* Цвет построения для Брезенхема */
   int  gdriver= DETECT, gmode;
   long atrib=5064064l,la;/* Размеp пиксела*100+цвета  */

#if MODE_256
   V_ini256 (&gdriver, &gmode, "");
   jj= getmaxcolor();
   for (ii=0; ii<=jj; ++ii)     /* Ч/б палитра    */
      setrgbpalette (ii, ii, ii, ii);
   atrib=5064064l;              /* Пиксел 5х5, нач цвет=64*/
   colgrid= 170;                /* Цвет сетки */
   fon= 140;
   setrgbpalette(7,255,255,255);/* Цвет для printf */
#else
   initgraph (&gdriver, &gmode, "");
   atrib= 5000016l;             /* Пиксел 5х5, нач цвет=0*/
   colgrid= 9;
   fon= 8;
#endif

   setbkcolor(fon);                     /* Очистка экрана */
   cleardevice();
   Xk= getmaxx(); Yk= getmaxy();

   Grid (colgrid);

/* Цвет для построения алгоритмом ЦДА */
   setrgbpalette(col_lin,63, 0,0);  /* Цвет точного отрезка  */
   setrgbpalette(col_DDA,63,63,0);  /* Цвет для ЦДА          */
   setrgbpalette(col_Bre,00,63,0);  /* Цвет для Брезенхема   */

   for (;;) {
      gotoxy (1, 1);
      printf("                                            ");
      printf("              \r");
      printf("mode atrib Xk Yk= (%d %ld %d %d) ? ",
              mode, atrib, Xk, Yk);
      scanf ("%d%ld%d%d", &mode, &atrib, &Xk, &Yk);
      xpix= ypix= atrib / 1000000l;
      la= atrib % 1000000l;
      col_beg= la / 1000l;
      col_val= la % 1000l;
      if (mode == -2) goto konec; else
      if (mode == -1) cleardevice(); else
      if (!mode) Grid (colgrid); else
      if (mode & 7) {
        if (mode & 1) {
           V_setlin (xpix, ypix, col_DDA, 1);
           V_DDA (Xn, Yn, Xk, Yk);
/* Постpоение "точного" отpезка */
           setcolor (col_lin);
           line (Xn, Yn, Xk*xpix, Yk*ypix);
        }
        if (mode & 2) {
           V_setlin (xpix, ypix, col_Bre, 1);
           V_Bre (Xn, Yn+3, Xk, Yk+3);
/* Постpоение "точного" отpезка */
           setcolor (col_lin);
           line (Xn, (Yn+3)*ypix, Xk*xpix, (Yk+3)*ypix);
        }
        if (mode & 4) {
           V_setlin (xpix, ypix, col_beg, col_val);
           V_BreM (Xn, Yn+6, Xk, Yk+6);
/* Постpоение "точного" отpезка */
           setcolor (col_lin);
           line (Xn, (Yn+6)*ypix, Xk*xpix, (Yk+6)*ypix);
        }
      } else {
         Xn= Xk;  Yn= Yk;
      }
   }
konec:
   closegraph();
}  /* main */

В данном приложении содержатся процедуры поддержки низкочастотной фильтрации растровых изображений и процедуры усреднения растровых изображений с понижением разрешения, а также тестовая программа демонстрирующая их работу.

Всего представлены две процедуры низкочастотной фильтрации V_fltr0 и V_fltr1, предназначенные для обработки изображений прямо в видеопамяти и с построчной буферизацией в оперативной памяти, соответственно. Последняя при модификации вспомогательных процедур доступа к изображению может обрабатывать картины, находящиеся в файле на внешнем носителе или просто в оперативной памяти.

Аналогично, представлены две процедуры усреднения изображения с понижением разрешения - V_fltr2 и V_fltr3.

При фильтрации и усреднении может использоваться одна из пяти предусмотренных масок фильтрации.

/*================================================== V_FILTR.C
 * В файле V_FILTR.C содержатся процедуры
 * поддержки фильтрации изображений:
 *
 * GetStr, PutStr - служебные
 *
 * V_fltr0 - фильтрует изображение в прямоугольной области,
 *           работая прямо с видеопамятью
 * V_fltr1 - фильтрует изображение в прямоугольной области,
 *           работая с буферами строк
 * V_fltr2 - усредняет картину по маске с понижением
 *           разрешения, работая прямо с видеопамятью
 * V_fltr3 - усредняет картину по маске с понижением
 *           разрешения, работая с буферами строк
 */

#include <alloc.h>

#define GetMay getpixel
#define PutMay putpixel

static int
   Mask0[]= {1,1, 1,1 },
   Mask1[]= {1,1,1, 1,1,1, 1,1,1 },
   Mask2[]= {1,1,1, 1,2,1, 1,1,1 },
   Mask3[]= {1,2,1, 2,4,2, 1,2,1 },
   Mask4[]= {1,1,1,1,
             1,1,1,1,
             1,1,1,1,
             1,1,1,1 },
   Mask5[]= {1,2, 3, 4, 3,2,1,
             2,4, 6, 8, 6,4,2,
             3,6, 9,12, 9,6,5,
             4,8,12,16,12,8,4,
             3,6, 9,12, 9,6,5,
             2,4, 6, 8, 6,4,2,
             1,2, 3, 4, 3,2,1 },
   Mask_ln[]= {2, 3, 3, 3, 4, 7},   /* Размер маски    */
   Mask_st[]= {2, 2, 2, 2, 4, 4},   /* Шаг усреднения  */
   Mask_vl[]= {4, 9,10,16,16,256},  /* Сумма элементов */
   *Mask_bg[]={                    /* Адреса начал    */
      Mask0,Mask1,Mask2,Mask3,Mask4,Mask5
   };

/*----------------------------------------------------- GetStr
 * Запрашивает фрагмент растровой строки из видеопамяти
 */
static void GetStr (st, Yst, Xn, Xk)
char *st;  int Yst, Xn, Xk;
{ while (Xn <= Xk) *st++= GetMay (Xn++, Yst); }


/*----------------------------------------------------- PutStr
 * Записывает фрагмент растровой строки в видеопамять
 */
static void PutStr (st, Yst, Xn, Xk)
char *st;  int Yst, Xn, Xk;
{while (Xn <= Xk) PutMay (Xn++, Yst, *st++); }

/*---------------------------------------------------- V_fltr0
 * Фильтрует изображение в прямоугольной области,
 * работая прямо с видеопамятью
 * msknum              = 0-5 - номер маски фильтра
 * Xn_source,Yn_source - окно исходного изображения
 * Xk_source,Xk_source
 * Xn_target,Yn_target - верхний левый угол результата
 */
void V_fltr0 (msknum,Xn_source,Yn_source,Xk_source,Yk_source,
              Xn_target,Yn_target)
int  msknum,Xn_source,Yn_source,Xk_source,Yk_source,
     Xn_target,Yn_target;
{
   char *plut;          /* Указатель палитры */
   int  *pi;            /* Тек указат маски  */
   int  pixel;          /* Пиксел исх изображения */
   int  *Maska,         /* Указатель маски */
        Mask_Y,Mask_X,  /* Размеры маски   */
        X_centr,Y_centr,/* Центр маски     */
        Mask_sum,       /* Сумма элементов */
        Xk,             /* Предельные положения маски */
        Yk,             /* в исходной области */
        s, sr, sg, sb,  /* Скаляры для суммир в маской   */
        ii, jj,
        Xt, Yt;

/* Запрос параметров маски */
   Maska=  Mask_bg[msknum];             /* Указатель маски */
   Mask_Y= Mask_X= Mask_ln[msknum];     /* Размеры маски   */
   X_centr= Mask_X / 2;                 /* Центр маски     */
   Y_centr= Mask_Y / 2;
   Mask_sum= Mask_vl[msknum];           /* Сумма элементов */

/* Предельные положения маски в исходной области */
   Xk= Xk_source+1-Mask_X;
   Yk= Yk_source+1-Mask_Y;

/*------- Фильтрация с прямой работой с видеопамятью -------*/

   for (Yt= Yn_source; Yt<=Yk; ++Yt) {
      for (Xt=Xn_source; Xt<=Xk; ++Xt) {
         pi= Maska; sr=0; sg=0; sb=0;   /* Суммированные RGB*/
         for (ii=0; ii<Mask_Y; ++ii)
            for (jj=0; jj<Mask_X; ++jj) {
               pixel= GetMay (Xt+jj, Yt+ii);
               plut= &V_pal256[pixel][0];
               s= *pi++;                /* Элемент маски */
               sr+= (s * *plut++);      /* Суммирование  */
               sg+= (s * *plut++);      /* по цветам с   */
               sb+= (s * *plut++);      /* весами маски  */
            }
         sr /= Mask_sum; sg /= Mask_sum;  sb /= Mask_sum;
/* Поиск элемента ТЦ, наиболее подходящего для данных R,G,B */
         ii= V_clrint (sr, sg, sb);
         PutMay (Xn_target+(Xt-Xn_source)+X_centr,
                 Yn_target+(Yt-Yn_source)+Y_centr, ii);
      }
   }
}  /* V_fltr0 */

/*---------------------------------------------------- V_fltr1
 * Фильтрует изображение в прямоугольной области,
 * работая с буферами строк
 * msknum              = 0-5 - номер маски фильтра
 * Xn_source,Yn_source - окно исходного изображения
 * Xk_source,Xk_source
 * Xn_target,Yn_target - верхний левый угол результата
 */
void V_fltr1 (msknum,Xn_source,Yn_source,Xk_source,Yk_source,
              Xn_target,Yn_target)
int  msknum,Xn_source,Yn_source,Xk_source,Yk_source,
     Xn_target,Yn_target;
{
   char *plut;          /* Указатель палитры */
   int  *pi;            /* Тек указат маски  */
   int  pixel;          /* Пиксел исх изображения */
   int  *Maska,         /* Указатель маски */
        Mask_Y,Mask_X,  /* Размеры маски   */
        X_centr,Y_centr,/* Центр маски     */
        Mask_sum,       /* Сумма элементов */
        Xk,             /* Предельные положения маски */
        Yk,             /* в исходной области */
        Dx_source,      /* Размер строки исх изображения */
        Ystr,           /* Y тек читаемой строки изображ */
        s, sr, sg, sb,  /* Скаляры для суммир в маской   */
        ii, jj,
        Xt, Yt;
   char *ps, *sbuf, *pt, *tbuf, *ptstr[8];

   Dx_source= Xk_source-Xn_source+1;

/* Запрос параметров маски */
   Maska=  Mask_bg[msknum];             /* Указатель маски */
   Mask_Y= Mask_X= Mask_ln[msknum];     /* Размеры маски   */
   X_centr= Mask_X / 2;                 /* Центр маски     */
   Y_centr= Mask_Y / 2;
   Mask_sum= Mask_vl[msknum];           /* Сумма элементов */

/* Предельные положения маски в исходной области */
   Xk= Xk_source+1-Mask_X;
   Yk= Yk_source+1-Mask_Y;

/* Заказ буферов */
   if ((sbuf= malloc (Dx_source * Mask_Y)) == NULL) goto all;
   if ((tbuf= malloc (Dx_source)) == NULL)
      goto fr_sbuf;

/*------- Фильтрация с использованием буферов строк --------*/

/* Подготовка массива указателей на строки
 *  ptstr[0] --> последняя строка
 *  ptstr[1] --> строка 0
 *  ptstr[2] --> строка 1
 *  и т.д.
 */
   ps= sbuf;  ii= Mask_Y;  jj= 1;
   do {
      ptstr[jj]= ps;  ps+= Dx_source;
      if (++jj == Mask_Y) jj= 0;
   } while (--ii > 0);

/* Начальное чтение Mask_Y - 1 строк */
   Ystr= Yn_source;
   for (ii=1; ii<Mask_Y; ++ii)
      GetStr (ptstr[ii], Ystr++, Xn_source, Xk_source);

   for (Yt= Yn_source; Yt<=Yk; ++Yt) {

/* Запрос следующей строки и циклический сдвиг указателей */
      GetStr (ps= ptstr[0], Ystr++, Xn_source, Xk_source);
      jj= Mask_Y-1;
      for (ii=0; ii<jj; ++ii) ptstr[ii]= ptstr[ii+1];
      ptstr[jj]= ps;

      pt= tbuf;
      for (Xt=Xn_source; Xt<=Xk; ++Xt) {
         pi= Maska; sr=0; sg=0; sb=0;   /* Суммированные RGB*/
         for (ii=0; ii<Mask_Y; ++ii) {
            ps= ptstr[ii] + (Xt-Xn_source);
            for (jj=0; jj<Mask_X; ++jj) {
               plut= &V_pal256[*ps++ & 255][0];
               s= *pi++;                /* Элемент маски */
               sr+= (s * *plut++);      /* Суммирование  */
               sg+= (s * *plut++);      /* по цветам с   */
               sb+= (s * *plut++);      /* весами маски  */
            }
         }
         sr /= Mask_sum; sg /= Mask_sum;  sb /= Mask_sum;
/* Поиск элемента ТЦ, наиболее подходящего для данных R,G,B */
         *pt++= V_clrint (sr, sg, sb);
      }
      PutStr (tbuf,                     /* Запись строки */
              Yn_target + Y_centr + (Yt-Yn_source) ,
              Xn_target + X_centr,
              Xn_target + X_centr + (--pt - tbuf));
   }
   free (tbuf);
fr_sbuf:
   free (sbuf);
all:;
}  /* V_fltr1 */

/*---------------------------------------------------- V_fltr2
 * Усредняет картину по маске с понижением разрешения,
 * работая прямо с видеопамятью
 * msknum              = 0-5 - номер маски фильтра
 * Xn_source,Yn_source - окно исходного изображения
 * Xk_source,Xk_source
 * Xn_target,Yn_target - верхний левый угол результата
 */
void V_fltr2 (msknum,Xn_source,Yn_source,Xk_source,Yk_source,
              Xn_target,Yn_target)
int  msknum,Xn_source,Yn_source,Xk_source,Yk_source,
     Xn_target,Yn_target;
{
   char *plut;          /* Указатель палитры */
   int  *pi;            /* Тек указат маски  */
   int  pixel;          /* Пиксел исх изображения */
   int  *Maska,         /* Указатель маски */
        Mask_Y,Mask_X,  /* Размеры маски   */
        X_centr,Y_centr,/* Центр маски     */
        Mask_sum,       /* Сумма элементов */
        Xk,             /* Предельные положения маски */
        Yk,             /* в исходной области */
        s, sr, sg, sb,  /* Скаляры для суммир в маской   */
        Xr,Yr,          /* Координаты пиксела результата */
        Sm,             /* Сдвиг маски для обраб след точки */
        ii, jj,
        Xt, Yt;

/* Запрос параметров маски */
   Maska=  Mask_bg[msknum];             /* Указатель маски */
   Mask_Y= Mask_X= Mask_ln[msknum];     /* Размеры маски   */
   X_centr= Mask_X / 2;                 /* Центр маски     */
   Y_centr= Mask_Y / 2;
   Mask_sum= Mask_vl[msknum];           /* Сумма элементов */

/* Предельные положения маски в исходной области */
   Xk= Xk_source+1-Mask_X;
   Yk= Yk_source+1-Mask_Y;

   Yt= Yn_source;
   Yr= Yn_target+Y_centr;
   Sm= Mask_st[msknum];                 /* Шаг усреднения*/
   while (Yt <= Yk) {
      Xt=Xn_source;  Xr= Xn_target+X_centr;
      while (Xt <= Xk) {
         pi= Maska; sr=0; sg=0; sb=0;   /* Суммированные RGB*/
         for (ii=0; ii<Mask_Y; ++ii)
            for (jj=0; jj<Mask_X; ++jj) {
               pixel= GetMay (Xt+jj, Yt+ii);
               plut= &V_pal256[pixel][0];
               s= *pi++;                /* Элемент маски */
               sr+= (s * *plut++);      /* Суммирование  */
               sg+= (s * *plut++);      /* по цветам с   */
               sb+= (s * *plut++);      /* весами маски  */
            }
         sr /= Mask_sum; sg /= Mask_sum;  sb /= Mask_sum;
/* Поиск элемента ТЦ, наиболее подходящего для данных R,G,B */
         ii= V_clrint (sr, sg, sb);
         PutMay (Xr++, Yr, ii);
         Xt+= Sm;
      }
      Yt+= Sm;  ++Yr;
   }
}  /* V_fltr2 */

/*---------------------------------------------------- V_fltr3
 * Усредняет картину по маске с понижением разрешения,
 * работая с буферами строк
 * msknum              = 0-5 - номер маски фильтра
 * Xn_source,Yn_source - окно исходного изображения
 * Xk_source,Xk_source
 * Xn_target,Yn_target - верхний левый угол результата
 */
void V_fltr3 (msknum,Xn_source,Yn_source,Xk_source,Yk_source,
              Xn_target,Yn_target)
int  msknum,Xn_source,Yn_source,Xk_source,Yk_source,
     Xn_target,Yn_target;
{
   char *plut;          /* Указатель палитры */
   int  *pi;            /* Тек указат маски  */
   int  pixel;          /* Пиксел исх изображения */
   int  *Maska,         /* Указатель маски */
        Mask_Y,Mask_X,  /* Размеры маски   */
        X_centr,Y_centr,/* Центр маски     */
        Mask_sum,       /* Сумма элементов */
        Xk,             /* Предельные положения маски */
        Yk,             /* в исходной области */
        Dx_source,      /* Размер строки исх изображения */
        s, sr, sg, sb,  /* Скаляры для суммир в маской   */
        Xr,Yr,          /* Координаты пиксела результата */
        Sm,             /* Сдвиг маски для обраб след точки */
        ii, jj,
        Xt, Yt;
   char *ps, *sbuf, *pt, *tbuf, *ptstr[8];


   Dx_source= Xk_source-Xn_source+1;

/* Запрос параметров маски */
   Maska=  Mask_bg[msknum];             /* Указатель маски */
   Mask_Y= Mask_X= Mask_ln[msknum];     /* Размеры маски   */
   X_centr= Mask_X / 2;                 /* Центр маски     */
   Y_centr= Mask_Y / 2;
   Mask_sum= Mask_vl[msknum];           /* Сумма элементов */

/* Предельные положения маски в исходной области */
   Xk= Xk_source+1-Mask_X;
   Yk= Yk_source+1-Mask_Y;

/* Заказ буферов */
   if ((sbuf= malloc (Dx_source * Mask_Y)) == NULL) goto all;
   if ((tbuf= malloc (Dx_source/Mask_st[msknum]+16)) == NULL)
      goto fr_sbuf;

/* Подготовка массива указателей на строки
 *  ptstr[0] --> строка 0
 *  ptstr[1] --> строка 1
 *  ptstr[2] --> строка 2
 *  и т.д.
 */
   ps= sbuf;
   for (ii=0; ii<Mask_Y; ++ii) {
      ptstr[ii]= ps;  ps+= Dx_source;
   }

   Yt= Yn_source;
   Yr= Yn_target+Y_centr;
   Sm= Mask_st[msknum];                 /* Шаг усреднения*/
   while (Yt <= Yk) {
      for (ii=0; ii<Mask_Y; ++ii)       /* Чтен исх строк */
         GetStr (ptstr[ii], Yt+ii, Xn_source, Xk_source);
      Xt=Xn_source;  pt= tbuf;
      while (Xt <= Xk) {
         pi= Maska; sr=0; sg=0; sb=0;   /* Суммированные RGB*/
         for (ii=0; ii<Mask_Y; ++ii) {
            ps= ptstr[ii] + (Xt-Xn_source);
            for (jj=0; jj<Mask_X; ++jj) {
               plut= &V_pal256[*ps++ & 255][0];
               s= *pi++;                /* Элемент маски */
               sr+= (s * *plut++);      /* Суммирование  */
               sg+= (s * *plut++);      /* по цветам с   */
               sb+= (s * *plut++);      /* весами маски  */
            }
         }
         sr /= Mask_sum; sg /= Mask_sum;  sb /= Mask_sum;
/* Поиск элемента ТЦ, наиболее подходящего для данных R,G,B */
         *pt++= V_clrint (sr, sg, sb);
         Xt+= Sm;
      }
      PutStr (tbuf,Yr++,                /* Запись строки */
              Xn_target+X_centr,
              Xn_target+X_centr + (--pt - tbuf));
      Yt+= Sm;
   }
   free (tbuf);
fr_sbuf:
   free (sbuf);
all:;
}  /* V_fltr3 */

/*================================================== T_FILTR.C
 *
 * ТЕСТ ФИЛЬТРАЦИИ
 *
 * Программа вначале строит два смещенных вектора
 * большими пикселами, затем последовательно для каждой
 * из пяти масок:
 * - фильтрует с непосредственным доступом к видеопамяти
 * - фильтрует с буферизацией растровых строк
 * - формирует усредненную картинку меньшего разрешения
 *   с непосредственным доступом к видеопамяти
 * - формирует усредненную картинку меньшего разрешения
 *   с буферизацией растровых строк
 *
 * После вывода очередной картинки ждет нажатия любой клавиши
 *
 * Виды масок:
 *   0: 1 1   1: 1 1 1   2: 1 1 1   3: 1 2 1
 *      1 1      1 1 1      1 2 1      2 4 2
 *               1 1 1      1 1 1      1 2 1
 *
 *  4: 1 1 1 1   5: 1 2  3  4  3 2 1
 *     1 1 1 1      2 4  6  8  6 4 2
 *     1 1 1 1      3 6  9 12  9 6 5
 *     1 1 1 1      4 8 12 16 12 8 4
 *                  3 6  9 12  9 6 5
 *                  2 4  6  8  6 4 2
 *                  1 2  3  4  3 2 1
 */

#include "V_VECTOR.C"
#include "VGA_256.C"
#include "V_FILTR.C"

#include <conio.h>
#include <graphics.h>
#include <stdio.h>

#define VECTOR 0  /* 0/1 - фикс вектор/ввод координат */

/*------------------------------------------------------- Grid
 * Строит сетку 10*10
 */

void Grid (void)
{  int Xn,Yn,Xk,Yk;
   setcolor (170);
   Xn= 0;  Xk= getmaxx();
   Yn= 0;  Yk= getmaxy();
   while (Xn <= Xk) {line (Xn,Yn,Xn,Yk); Xn+= 10; }
   Xn= 0;
   while (Yn <= Yk) {line (Xn,Yn,Xk,Yn); Yn+= 10; }
}  /* Grid */

/*---------------------------------------------- main Filtr */

void main (void)
{
   int  ii, jj,
        mov_lin,                /* 0/1 - позиционир/отрезок */
        Xn,Yn,Xk,Yk,            /* Координаты отрезка       */
        fon=   140;             /* Индекс фона              */
   int  gdriver= DETECT, gmode;
   int  Xn_source, Yn_source,   /* Фильтруемая область      */
        Xk_source, Yk_source,
        Dx_source;
   int  Xn_target, Yn_target,   /* Результаты фильтрации    */
        Xk_target, Yk_target;
   int  msknum;                 /* Номер текущей маски  */
   char *ps;

   V_ini256 (&gdriver, &gmode, "");

   ps= (char *)V_pal256;
   for (ii=0; ii<=255; ++ii) {          /* Ч/б палитра    */
      jj= ii / 4;
      *ps++= jj; *ps++= jj; *ps++= jj;
      setrgbpalette (ii, jj, jj, jj);
   }
   setbkcolor(fon);                     /* Очистка экрана */
   cleardevice();
   Xk= getmaxx(); Yk= getmaxy();

/* Начальные установки для фильтрации */
   Xn_source= 0;                        /* Исходная область */
   Yn_source= 0;
   Xk_source= (Xk + 1)/2 - 1;
   Yk_source= Yk;
   Xn_target= Xk_source + 1;            /* Результ. область */
   Yn_target= 0;
   Xk_target= Xk;
   Yk_target= Yk_source;

   Dx_source= Xk_source-Xn_source+1;    /* X-размер исходной*/

#if VECTOR
   Grid ();
   mov_lin= 1;  Xn= 0;  Yn= 0;  Xk= 0;  Yk= 0;
   for (;;) {
      gotoxy (1, 1);
      printf("                                       \r");
      printf("mov_lin Xk Yk= (%d %d %d) ? ", mov_lin, Xk, Yk);
      scanf ("%d%d%d", &mov_lin, &Xk, &Yk);
      if (mov_lin < 0) cleardevice(); else
      if (!mov_lin) Grid (); else {
         if (mov_lin & 1) V_DDA (0, 0, Xk, Yk);
         if (mov_lin & 2) V_Bre (0, 0, Xk, Yk);
      }
   }
#else
   Xk= Dx_source / Pix_X - 1;
   Yk= (Yk_source-Yn_source+1) / Pix_Y - 1;
   V_DDA (Xn_source, Yn_source,    Xk, Yk-17);
   V_Bre (Xn_source, Yn_source+17, Xk, Yk);
   getch();
#endif

   ii= 0xF;     /* Обе фильтрации и оба сжатия */

   setfillstyle (SOLID_FILL, fon);

   for (msknum=0; msknum<6; ++msknum) {
      if (ii & 1) {     /* Фильтрация из видеоозу */
         bar (Xn_target, Yn_target, Xk_target, Yk_target);
         V_fltr0 (msknum,Xn_source,Yn_source,
                  Xk_source,Yk_source,Xn_target,Yn_target);
        getch ();
      }
      if (ii & 2) {     /* Фильтрация из буферов */
         bar (Xn_target, Yn_target, Xk_target, Yk_target);
         V_fltr1 (msknum,Xn_source,Yn_source,
                  Xk_source,Yk_source,Xn_target,Yn_target);
         getch ();
      }
      if (ii & 4) {     /* Сжатие из из видеоозу */
         bar (Xn_target, Yn_target, Xk_target, Yk_target);
         V_fltr2 (msknum,Xn_source,Yn_source,
                  Xk_source,Yk_source,Xn_target,Yn_target);
        getch ();
      }
      if (ii & 8) {     /* Сжатие из буферов */
         bar (Xn_target, Yn_target, Xk_target, Yk_target);
         V_fltr3 (msknum,Xn_source,Yn_source,
                  Xk_source,Yk_source,Xn_target,Yn_target);
         getch ();
      }
   }
   closegraph();
}  /* main */

В данном приложении помещены процедуры генерации окружностей по алгоритму Брезенхема и Мичнера, а также программа T_Circle для тестирования данных процедур.

/*--------------------------------------------------- V_Circle
 * Подпрограммы для генерации окружности
 * Pixel_circle - занесение пикселов с учетом симметрии
 * V_BRcirc     - генерирует окружность по алгоритму
 *                Брезенхема.
 * V_MIcirc     - генерирует окружность по алгоритму
 *                Мичнера.
 */

#include <graphics.h>

/*----------------------------------------------- Pixel_circle
 * Заносит пикселы окружности по часовой стрелке
 */

static void Pixel_circle (xc, yc, x, y, pixel)
int  xc, yc, x, y, pixel;
{
   putpixel(xc+x, yc+y, pixel);
   putpixel(xc+y, yc+x, pixel);
   putpixel(xc+y, yc-x, pixel);
   putpixel(xc+x, yc-y, pixel);
   putpixel(xc-x, yc-y, pixel);
   putpixel(xc-y, yc-x, pixel);
   putpixel(xc-y, yc+x, pixel);
   putpixel(xc-x, yc+y, pixel);
}  /* Pixel_circle */


/*--------------------------------------------------- V_BRcirc
 * Генерирует 1/8 окружности по алгоритму Брезенхема
 *
 * Процедура может строить 1/4 окружности.
 * Для этого надо цикл while заменить на for (;;)
 * и после Pixel_circle проверять достижение конца по условию
 * if (y <= end) break;
 * Где end устанавливается равным 0
 * В этом случае не нужен и последний оператор
 * if (x == y) Pixel_circle (xc, yc, x, y, pixel);
 * Генерацию 1/8 можно обеспечить задав end = r / sqrt (2)
 */

void V_BRcirc (xc, yc, r, pixel)
int  xc, yc, r, pixel;
{  int  x, y, z, Dd;
   x= 0;  y= r;  Dd= 2*(1-r);
   while (x < y) {
      Pixel_circle (xc, yc, x, y, pixel);
      if (!Dd) goto Pd;
      z= 2*Dd - 1;
      if (Dd > 0) {
         if (z + 2*x <= 0) goto Pd; else goto Pv;
      }
      if (z + 2*y > 0) goto Pd;
Pg:   ++x;      Dd= Dd + 2*x + 1;   continue; /* Горизонт */
Pd:   ++x; --y; Dd= Dd + 2*(x-y+1); continue; /* Диагонал */
Pv:   --y;      Dd= Dd - 2*y + 1;             /* Вертикал */
   }
   if (x == y) Pixel_circle (xc, yc, x, y, pixel);
}  /* V_BRcirc */


/*--------------------------------------------------- V_MIcirc
 * Генерирует 1/8 окружности по алгоритму Мичнера
 */

void V_MIcirc (xc, yc, r, pixel)
int  xc, yc, r, pixel;
{  int  x, y, d;
   x= 0;  y= r;  d= 3 - 2*r;
   while (x < y) {
      Pixel_circle (xc, yc, x, y, pixel);
      if (d < 0) d= d + 4*x + 6; else {
         d= d + 4*(x-y) + 10;  --y;
      }
      ++x;
   }
   if (x == y) Pixel_circle (xc, yc, x, y, pixel);
}  /* V_MIcirc */




/*=============================================== T_CIRCLE.C
 *
 * ТЕСТ ГЕНЕРАЦИИ ОКРУЖНОСТЕЙ
 *
 * Запрашивает ввод четырех чисел - координат центра,
 * радиуса и цвета построения: Xc Yc R Pix
 *
 * Затем строит заданную окружность по алгоритму Брезенхема
 * и концентрично с ней с радиусом, уменьшенным на 2, и
 * номером цвета, уменьшенным на 1, выдает окружность по
 * алгоритму Мичнера.
 *
 * При вводе Xc < 0 программа прекращает работу
 */

#include <graphics.h>
#include <stdio.h>
#include "V_CIRCLE.C"


/*-------------------------------------------- MAIN T_CIRCLE.C
 */
void main (void)
{
   int   ii, Xc=300, Yc=240, R=238, Pix=14;
   int   gdriver = DETECT, gmode;

   initgraph(&gdriver, &gmode, "c:\tc\bgi");
   if ((ii= graphresult()) != grOk) {
      printf ("Err=%d\n", ii); goto all;
   }
   setbkcolor(0);
   cleardevice();

for (;;) {
gotoxy (1,1);
printf("                                                 \r");
printf("Xc, Yc, R, Pix= (%d %d %d %d) ? ", Xc,Yc,R,Pix);
scanf ("%d%d%d%d", &Xc, &Yc, &R, &Pix);
if (Xc < 0) break;
V_BRcirc (Xc, Yc, R, Pix);
V_MIcirc (Xc, Yc, R-2, Pix-1);
}
all:
   closegraph();
}

В данном приложении приведены две процедуры заливки многоугольника: V_FP0 и V_FP1. Обе они реализуют алгоритм построчного заполнения, описанный в разделе 5.

В данных процедурах все массивы используются, начиная с элемента с индексом 1, а не 0, как это принято в языке C.

/*=====================================================  V_FP0
 * Простая (и не слишком эффективная) подпрограмма
 * однотонной заливки многоугольника методом построчного
 * сканирования. Имеет место дублирование закраски
 * строк.
 * Более эффективная программа, практически не дублирующая
 * занесение пикселов, - V_FP1 приведена далее в этом
 * приложении.
 */

#include <stdio.h>
#include <graphics.h>

#define MAXARR 300  /* Макс кол-во вершин многоугольника  */
#define MAXLST 300  /* Макс размер списка активных ребер  */


/*---------------------------------------------------- FILSTR
 * Заливает строку iy от ixn до ixk
 *
 * void FILSTR (int kod, int iy, int ixn, int ixk)
 */
void FILSTR (kod, iy, ixn, ixk)
int kod, iy, ixn, ixk;
{
   while (ixn <= ixk) putpixel (ixn++, iy, kod);
}  /* FILSTR */


/*----------------------------------------------------   SORT
 * Сортирует n элементов iarr по возрастанию
 */
void SORT (n, iarr)
int  n, *iarr;
{  int  ii, jj, kk, ll, min;
   for (ii=0; ii<n; ++ii) {
      min= iarr[ll= ii];
      for (jj=ii+1; jj<n; ++jj)
         if ((kk= iarr[jj]) < min) {ll= jj; min= kk; }
      if (ll != ii) {iarr[ll]= iarr[ii]; iarr[ii]= min; }
   }
}  /* SORT */


/*--------------- Глобалы процедуры закраски ---------------*/

static int   KOD, NWER; /* Код заливки и количество вершин  */
static float *pt_X;     /* Массивы входных координат вершин */
static float *pt_Y;

static int   ntek;          /* Номер текущей вершины */

/* Список активных ребер */
static int   idlspi;        /* Длина списка активных ребер */
static int   IYREB[MAXLST]; /* Макс Y-коорд активных ребер */
static float RXREB[MAXLST]; /* Тек  X-коорд активных ребер */
static float RPRIR[MAXLST]; /* X-приращение на 1 шаг по Y  */


/*---------------------------------------------------- OBRREB
 * По данным :
 *     NWER - количество вершин,
 *     ntek - номер текущей вершины,
 *     isd = -1/+1 - сдвиг для вычисления номера
 *           соседней вершины - слева/справа
 *     вычисляет DY,
 *     Если DY <  0 то вершина уже обработана,
 *     Если DY == 0 то вершины на одном Y, т.е.
 *                     строится горизонтальный отрезок,
 *     Если DY >  0 то формируется новый элемент списка
 *                     активных ребер
 */
static void OBRREB (isd)
int   isd;
{
   int   inext,iyt,ixt;
   float xt, xnext, dy;

   inext= ntek + isd;
   if (inext < 1) inext= NWER;
   if (inext > NWER) inext= 1;

   dy= pt_Y[inext] - pt_Y[ntek];
   if (dy < 0) goto RETOBR;
   xnext= pt_X[inext];
   xt= pt_X[ntek];
   if (dy != 0) goto DYNE0;
      iyt= pt_Y[ntek];
      inext= xnext;
      ixt= xt;
      FILSTR (KOD, iyt, inext, ixt);
      goto RETOBR;
DYNE0:
   idlspi++;
   IYREB[idlspi]= pt_Y[inext];
   RXREB[idlspi]= xt;
   RPRIR[idlspi]= (xnext - xt) / dy;
RETOBR:;
}  /* OBRREB */

/*----------------------------------------------------  V_FP0
 * Однотонно заливает многоугольник,
 * заданный координатами вершин
 *
 * void V_FP0 (int pixel, int kol, float *Px, float *Py)
 *
 */
void V_FP0 (pixel, kol, Px, Py)
int  pixel, kol;  float *Px, *Py;
{
int  ii, jj, kk;
int  iymin;         /* Мин  Y-координата многоугольн   */
int  iymax;         /* Макс Y-координата многоугольн   */
int  iysled;        /* Y-коорд появления новых вершин  */
int  iytek;
int  ikledg;        /* Кол-во вершин с данным iytek    */
int  ibgind;        /* Нач индекс таких вершин         */
int  iedg[MAXARR];  /* Y-коорд вершин по возрастанию   */
int  inom[MAXARR];  /* Их номера в исходном массиве Py */
int  irabx[MAXLST]; /* X-коорд пересечений в строке сканир */

   KOD= pixel;      /* Параметры в глобалы */
   NWER= kol;
   pt_X= Px;
   pt_Y= Py;

/* Построение массивов Y и их номеров */
   for (ii=1; ii<=kol; ++ii) {
      iedg[ii]= Py[ii]; inom[ii]= ii;
   }

/* Cовместная сортировка Y-коорд вершин и их номеров */
   for (ii=1;  ii <= kol;  ++ii) {
      iymin= iedg[ii];
      ntek= ii;
      for (jj=ii+1;  jj <= kol;  ++jj)
         if (iedg[jj] < iymin) {iymin= iedg[jj]; ntek= jj; }
      if (ntek != ii) {
         iedg[ntek]= iedg[ii]; iedg[ii]= iymin;
         iymin= inom[ntek];
         inom[ntek]= inom[ii]; inom[ii]= iymin;
      }
   }

   idlspi= 0;                   /* Начальные присвоения */
   ibgind= 1;
   iytek= iedg[1];
   iymax= iedg[kol];

/* Цикл раскраски */

/* ikledg = кол-во вершин с данным iytek
 * ibgind = индексы таковых в массиве inom
 */
FORM_EDGES:
   ikledg= 0;
   for (ii=ibgind; ii<=kol; ++ii)
      if (iedg[ii] != iytek) break; else ikledg++;

/* Цикл построения списка активных ребер
 * и закрашивание горизонтальных ребер
 */

/* Построение списка активных ребер (САР) */

   for (ii=1; ii<=ikledg; ++ii) {
      ntek= inom[ ibgind+ii-1];     /* Исх ном тек вершины */
      OBRREB (-1);                  /* DY с соседями затем */
      OBRREB (+1);                  /* либо отказ,  либо   */
                                    /* горизонталь, либо   */
   }                                /* измен списка активных*/

   if (!idlspi) goto KOHGFA;

   ii= ibgind + ikledg;         /* Y ближайшей вершины */
   iysled= iymax;
   if (ii < kol) iysled= iedg[ii];

/* Горизонтальная раскраска по списку */

   for (ii=iytek; ii<=iysled; ++ii) {
/* Выборка X-ов из списка активных ребер (САР) */
      for (jj=1; jj <= idlspi; ++jj)
         irabx[jj]= RXREB[jj];
      SORT (idlspi, irabx+1);           /* Сортировка X-ов */
      for (jj=1; jj<=idlspi-1; jj+= 2)  /* Заливка */
         FILSTR (pixel, ii, irabx[jj], irabx[jj+1]);
      if (ii == iysled) continue;
      for (jj=1; jj <= idlspi; ++jj)    /* Перестройка САР */
         RXREB[jj]= RXREB[jj] + RPRIR[jj];
   }

   if (iysled == iymax) goto KOHGFA;

/* Выбрасывание из списка всех ребер с YMAK ребра = YSLED */

   ii= 0;
M1:ii++;
M2:if (ii > idlspi) goto WYBROSILI;
      if (IYREB[ii] != iysled) goto M1;
         --idlspi;
         for (jj=ii;  jj <= idlspi;  ++jj) {
            IYREB[jj]= IYREB[kk= jj+1];
            RXREB[jj]= RXREB[kk];
            RPRIR[jj]= RPRIR[kk];
         }
         goto M2;
WYBROSILI:
   ibgind+= ikledg;
   iytek= iysled;

   goto FORM_EDGES;

KOHGFA:;
}  /* V_FP0 */

/*---------------------------------------------- main V_FP0 */

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_FP0 (new, kol, Px, Py);

/* Построение границы */
   setcolor (grn);
   for (ii= 1; ii<kol; ++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<kol+4; ++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();
}

/*=====================================================  V_FP1
 * Более эффективная по сравнению с V_FP0 подпрограмма
 * однотонной заливки многоугольника методом построчного
 * сканирования.
 *
 * Дублирувание занесения пикселов практически отсутствует
 *
 */

#include <stdio.h>
#include <graphics.h>

#define MAXARR 300  /* Макс кол-во вершин многоугольника  */
#define MAXLST 300  /* Макс размер списка активных ребер  */


/*---------------------------------------------------- FILSTR
 * Заливает строку iy от ixn до ixk
 *
 * void FILSTR (int kod, int iy, int ixn, int ixk)
 */
void FILSTR (kod, iy, ixn, ixk)
int kod, iy, ixn, ixk;
{
   while (ixn <= ixk) putpixel (ixn++, iy, kod);
}  /* FILSTR */



/*--------------- Глобалы процедуры закраски ---------------*/

static int   KOD, NWER; /* Код заливки и кол-во вершин      */
static float *pt_X;     /* Массивы входных координат вершин */
static float *pt_Y;

static int   IBGIND;        /* Номер след вершины в списке */
static int   IEDG[MAXARR];  /* Y-коорд вершин по возрастан */
static int   INOM[MAXARR];  /* и их номера в исх масс Py   */

/* Список активных ребер */
static int   IDLSPI;        /* Длина списка активных ребер */
static int   IYREB[MAXLST]; /* Макс Y-коорд активных ребер */
static float RXREB[MAXLST]; /* Тек  X-коорд активных ребер */
static float RPRIR[MAXLST]; /* Х-приращение на 1 шаг по Y  */
static float RYSL[MAXLST];  /* Dy между тек и соседн верш  */
                            /* Dy <= 0.0 - обычная вершина */
                            /*     > 0.0 - локал экстремум */


/*---------------------------------------------------- FORSPI
 * int  FORSPI (int IYBEG)
 *
 *  1) Формирует элементы списка для ребер,
 *     начинающихся в IYBEG;
 *  2) Вычиcляeт IBGIND - индeкc нaчaлa следующей
 *     вepшины в cпиcкe вepшин;
 *  3) Возвращает IYSLED - Y кoopдинaтy ближaйшeй
 *     вepшины, дo кoтopoй мoжнo зaливaть бeз
 *     пepecтpoйки cпиcкa.
 *
 *  Глoбaльныe вeличины :
 *
 *  KOD    - код заливки
 *  NWER   - кoл-вo вepшин в иcxoднoм мнoгoyгoльникe,
 *  *pt_X  - X-кoopдинaты иcxoднoгo мнoгoyгoльника,
 *  *pt_Y  - Y-кoopдинaты иcxoднoгo мнoгoyгoльника,
 *  IEDG   - yпopядoчeнный пo вoзpacтaнию мaccив
 *           Y кoopдинaт вepшин иcxoднoгo мнoгoyгoльн
 *  INOM   - INOM[i] зaдaeт нoмep вepшины в иcxoднoм
 *           мнoгoyгoльникe для IEDG[i],
 *  IBGIND - индeкc мaccивoв IEDG, INOM
 *           oпpeдeляeт гдe мoжeт нaчaтьcя ребpo,
 *  IDLSPI - длинa пocтpoeннoгo cпиcкa aктивныx ребep,
 *           cocтoящeгo из :
 *           IYREB  - мaкc кoopдинaты ребep,
 *           RXREB  - внaчaлe мин, зaтeм тeкyщaя X-кoopдинaтa,
 *           RPRIR  - пpиpaщeниe к X-кoopдинaтe нa 1 шaг пo Y,
 *           RYSL   - пpизнaк тoгo чтo зa вepшинa :
 *                    <= 0 - oбычнaя,
 *                     > 0 - лoкaльный экcтpeмyм
 *                     пepeceчeниe cтpoки зaкpacки
 *                     c экcтpeмyмoм cчитaeтcя зa 2 тoчки,
 *                     c oбычнoй - зa 1;
 */

static int  FORSPI (IYBEG)
int  IYBEG;
{

   int   i,ikledg,intek,intabs,isd;
   int   iyt,ixt,nrebra,inc,inpred,inposl;
   float xt, xc, yt, yc, dy;

/* ikledg = кoл-вo вepшин c дaнным IYBEG */

   ikledg= 0;
   for (i=IBGIND; i<=NWER; ++i)
      if (IEDG[i] != IYBEG) break; else ++ikledg;

/* Цикл пocтpoeния cпиcкa aктивныx ребep
   и зaкpaшивaниe гopизонтальных ребep
 */

   for (i=1; i<=ikledg; ++i) {
/* Bычисл номера текущей вершины */
      intek= INOM[IBGIND+i-1];
      intabs= abs (intek);
      xt= pt_X[intabs];
      yt= pt_Y[intabs];

/*  Bычисл номеров предыд и послед вершин */
      if ((inpred= intabs - 1) < 1) inpred= NWER;
      if ((inposl= intabs + 1) > NWER) inposl= 1;

/*
 * По заданным :
 *    NWER   - кол-во вершин,
 *    intek  - номер текущей вершины,
 *    isd = 0/1 - правилу выбора соседней вершины -
 *                предыдущая/последующая
 *    вычиcляeт dy,
 *    Еcли dy <  0 тo вepшинa yжe oбpaбoтaнa,
 *    Еcли dy == 0 тo вepшины нa oдном Y
 *                 Пpи этoм cтpoитcя гopизoнтaльный oтpeзoк.
 *                 Фaкт зaкpacки гopизoнтaльнoгo ребpa
 *                 oтмeчaeтcя oтpицaтeльным знaчeниeм
 *                 cooтвeтcтвyющeгo знaчeния INOM.
 *    Еcли dy >  0 тo фopмиpyeтcя нoвый элeмент cпиcкa
 *                 aктивныx ребep
 */

      for (isd=0;  isd<=1; ++isd) {
         if (!isd) nrebra= inc= inpred; else {
            inc= inposl;  nrebra= intabs;
         }
         yc= pt_Y[inc];
         dy= yc - yt;
         if (dy < 0.0) continue;
         xc= pt_X[inc];
         if (dy != 0.0) goto DYNE0;
            if ((inc= INOM[nrebra]) < 0) continue;
            INOM[nrebra]= -inc;
            iyt= yt;
            inc= xc;
            ixt= xt;
            FILSTR (KOD, iyt, inc, ixt);
            continue;
DYNE0:   ++IDLSPI;
         IYREB[IDLSPI]= yc;
         RXREB[IDLSPI]= xt;
         RPRIR[IDLSPI]= (xc - xt) / dy;
         inc= (!isd) ? inposl : inpred;
         RYSL[IDLSPI]=  pt_Y[inc] - yt;
      }   /* цикла по isd */
   }  /* построения списка активных ребер */

/*  Bычисление Y ближайшей вершины */
   if ((i= (IBGIND += ikledg)) > NWER) i= NWER;
   return (IEDG[i]);
} /* Процедуры FORSPI */

/*-----------------------------------------------------  V_FP1
 * Однотонно заливает многоугольник,
 * заданный координатами вершин
 *
 * void V_FP1 (int pixel, int kol, float *Px, float *Py)
 *
 */
void V_FP1 (pixel, kol, Px, Py)
int  pixel, kol;  float *Px, *Py;
{
int  i,j,k,l;
int  iytek;    /* Y текущей строки сканирования        */
int  iymin;    /* Y-мин при сортировке массива Y-коорд */
int  iybeg;    /* Мин Y-координата заливки  */
int  iymak;    /* Max Y-координата заливки  */
int  iysled;   /* Y кoopд ближaйшeй вepшины, дo кoтopoй */
               /* можно зaливaть бeз пepecтpoйки cпиcкa */
int  newysl;
int  ixmin;    /* X-мин при сортировке для тек строки */
int  ixtek;    /* X-тек при сортировке для тек строки */
int  irabx[MAXLST]; /* X-коорд пересечений в строке сканир */

   KOD= pixel;    /* Параметры в глобалы */
   NWER= kol;
   pt_X= Px;
   pt_Y= Py;

/*  Построение массивов Y и их номеров */
   for (i= 1; i<=NWER; ++i) {IEDG[i]= Py[i];  INOM[i]= i; }

/*  Cовместная сортировка массивов IEDG, IHOM */
   for (i= 1; i<=NWER; ++i) {
      iymin= IEDG[i];
      k= 0;
      for (j=i+1; j<=NWER; ++j)
         if ((l= IEDG[j]) < iymin) {iymin= l; k= j; }
      if (k) {
         IEDG[k]= IEDG[i]; IEDG[i]= iymin;
         iymin= INOM[k];
         INOM[k]= INOM[i]; INOM[i]= iymin;
      }
   }

/* Hачальные присвоения */
   IDLSPI= 0;
   IBGIND= 1;
   iybeg= IEDG[1];
   iymak= IEDG[NWER];

/* Формирование начального списка акт ребер */

   iysled= FORSPI (iybeg);
   if (!IDLSPI) goto KOHGFA;

/* Горизонтальная раскраска по списку */

ZALIWKA:

   for (iytek=iybeg; iytek<=iysled; ++iytek) {
      if (iytek == iysled) {    /* Y-координата перестройки */
         newysl= FORSPI (iytek);
         if (!IDLSPI) goto KOHGFA;
      }

/* Bыборка и сортировка X-ов из списка ребер */
      l= 0;
      for (i=1; i<=IDLSPI; ++i)
         if (RYSL[i] > 0.0) irabx[++l]= RXREB[i];
         else RYSL[i]= 1.0;

      for (i=1;  i<=l; ++i) {
         ixmin= irabx[i];
         k= 0;
         for (j=i+1;  j<=l; ++j) {
            ixtek= irabx[j];
            if (ixtek < ixmin) {k= j; ixmin= ixtek; }
         }
         if (k) {irabx[k]= irabx[i];  irabx[i]= ixmin; }
      }  /* цикла сортировки */

/*  Cобственно заливка */

      for (j=1;  j<=l-1;  j+= 2)
         FILSTR (KOD,iytek,irabx[j],irabx[j+1]);

      for (j=1;  j<=IDLSPI; ++j)        /*  Приращения X-ов */
         RXREB[j]= RXREB[j] + RPRIR[j];
   }  /* цикла горизонтальной раскраски */

   if (iysled == iymak) goto KOHGFA;

/*  Bыбрасывание из списка всех ребер с YMAK ребра == YSLED */

   i= 0;
M1:++i;
M2:if (i > IDLSPI) goto WYBROSILI;
      if (IYREB[i] != iysled) goto M1;
         --IDLSPI;
         for (j=i;  j<=IDLSPI; ++j) {
            IYREB[j]= IYREB[k= j+1];
            RXREB[j]= RXREB[k];
            RPRIR[j]= RPRIR[k];
         }
         goto M2;
WYBROSILI:
   iybeg= iysled + 1;
   iysled= newysl;
   goto ZALIWKA;

KOHGFA:;
}  /* 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<kol; ++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<kol+4; ++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();
}

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

Первая процедура - 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();
}

В данном приложении приведены процедуры, обеспечивающие выполнение отсечения по прямоугольному и многоугольному выпуклому окну и тестовая программа проверки работы процедур отсечения.

/*=================================================== V_CLIP.C
 *
 * Подрограммы, связанные с отсечением:
 *
 * V_SetPclip - установить размеры многоугольного окна
 *              отсечения
 * V_SetRclip - установить размеры прямоугольного окна
 *              отсечения
 * V_GetRclip - опросить   размеры прямоугольного окна
 *              отсечения
 * V_CSclip   - отсечение по алгоритму Коэна-Сазерленда
 *              прямоугольное окно, кодирование
 *              концов отсекаемого отрезка
 * V_FCclip   - отсечение по алгоритму быстрого отсечения
 *              Алгоритм Собкова-Поспишила-Янга -
 *              прямоугольное окно, кодирование
 *              отсекаемого отрезка
 * V_LBclip   - отсечение по алгоритму Лианга-Барски
 *              прямоугольное окно, параметрическое
 *              представление линий
 * V_CBclip   - отсечение по алгоритму Кируса-Бека
 *              окно - выпуклый многоугольник,
 *              параметрическое представление линий
 */


/* Глобальные скаляры для алгоритмов отсечения по
 * прямоугольному окну - Коэна-Сазерленда, Fc-алгоритм,
 * Лианга-Барски
 */
static float Wxlef= 0.0,   /* Координаты левого нижнего и */
             Wybot= 0.0,   /* правого верхнего углов окна */
             Wxrig= 7.0,   /* отсечения                   */
             Wytop= 5.0;

/* Глобальные скаляры для алгоритма Кируса-Бека
 * отсечения по многоугольному окну
 */

/* Координаты прямоугольного окна */
static float Wxrect[4]= {0.0, 0.0, 7.0, 7.0 };
static float Wyrect[4]= {0.0, 5.0, 5.0, 0.0 };

/* Перепендикуляры к сторонам прямоугольного окна */
static float WxNrec[4]= {1.0,  0.0, -1.0, 0.0 };
static float WyNrec[4]= {0.0, -1.0,  0.0, 1.0 };

/* Данные для многоугольного окна */
static int   Windn=4;          /* Кол-во вершин у окна   */
static float *Windx=  Wxrect,  /* Координаты вершин окна */
             *Windy=  Wyrect;
static float *Wnormx= WxNrec,  /* Координаты нормалей    */
             *Wnormy= WyNrec;

/*------------------------------------------------- V_SetPclip
 * Устанавливает многоугольное окно отсечения
 * kv - количество вершин в окне
 * wx - X-координаты вершин
 * wy - Y-координаты вершин
 * nx - X-координаты нормалей к ребрам
 * ny - Y-координаты нормалей к ребрам
 *
 * Проверяет окно на выпуклость и невырожденность
 *
 * Если окно правильное, то
 * 1. Обновляет глобалы описания многоугольного окна:
 *    Windn=  kv;
 *    Windx=  wx;  Windy=  wy;  --Координаты вершин окна
 *    Wnormx= nx;  Wnormy= ny;  --Координаты перпендикуляров
 *
 * 2. Вычисляет координаты перепендикуляров к сторонам окна
 *
 * Возвращает:
 * 0 - норма
 * 1 - вершин менее трех
 * 2 - многоугольник вырожден в отрезок
 * 3 - многоугольник невыпуклый
 */

int  V_SetPclip (kv, wx, wy, nx, ny)
int  kv;  float *wx, *wy, *nx, *ny;
{  int   ii, jj, sminus, splus, szero, otw;
   float r,
         vox, voy,      /* Координаты (i-1)-й вершины */
         vix, viy,      /* Координаты i-й     вершины */
         vnx, vny;      /* Координаты (i+1)-й вершины */

/* Проверка на выпуклость
 * для этого вычисляются векторные произведения
 * смежных сторон и определяется знак
 * если все знаки == 0 то многоугольник вырожден
 * если все знаки >= 0 то многоугольник выпуклый
 * если все знаки <= 0 то многоугольник невыпуклый
 */
   otw= 0;
   if (--kv < 2) {++otw; goto all; }
   sminus= 0;
   splus=  0;
   szero=  0;
   vox= wx[kv];  voy= wy[kv];
   vix= *wx;     viy= *wy;
   ii= 0;
   do {
      if (++ii > kv) ii= 0;           /* Следующая  вершина */
      vnx= wx[ii];  vny= wy[ii];      /* Координаты (i+1)-й */
      r= (vix-vox)*(vny-viy) -        /* Вект произв ребер  */
         (viy-voy)*(vnx-vix);         /* смежных с i-й верш */
      if (r < 0) ++sminus; else
      if (r > 0) ++splus;  else ++szero;
      vox= vix;  voy= viy;            /* Обновлен координат */
      vix= vnx;  viy= vny;
   }  while (ii);

   if (!splus && !sminus)       /* Все векторные равны нулю */
      {otw= 2; goto all; }      /* Многоугольник вырожден   */
   if (splus && sminus)         /* Знакопеременн. векторные */
      {otw= 3; goto all; }      /* Многоугольник невыпуклый */

/* Установление глобалов для правильного окна */
   Windn= kv+1;                 /* Количество вершин у окна */
   Windx=  wx;  Windy=  wy;     /* Координаты вершин окна   */
   Wnormx= nx;  Wnormy= ny;     /* Координ. перпендикуляров */

/* Вычисление координат перпендикуляров к сторонам */

   vox= *wx; voy= *wy;
   ii= 0;
   do {
      if (++ii > kv) ii= 0;
      vix= wx[ii];  viy= wy[ii];     /* Текущая вершина */
      vnx= viy-voy; vny= vox-vix;    /* Поворот по часовой  */
      if (splus) {                   /* Внутр нормали влево */
         vnx= -vnx; vny= -vny;
      }
      *nx++= vnx;  *ny++= vny;
      vox= vix;  voy= viy;          /* Обновление координат */
   } while (ii);

all:
   return (otw);
}  /* V_SetPclip */

/*------------------------------------------------- V_SetRclip
 * Устанавливает прямоугольное окно отсечения
 * Возвращает 0/1 - нет/есть ошибки в задании окна
 */
int  V_SetRclip (xleft, ybottom, xright, ytop)
float xleft, ybottom, xright, ytop;
{  int  otw;
   otw= 0;
   if (xleft >= xright || ybottom >= ytop) ++otw; else {
      Windn= 4;
      Windx= Wxrect;  Windy= Wyrect;         /* Вершины */
      Wxlef= Wxrect[0]= Wxrect[1]= xleft;
      Wybot= Wyrect[0]= Wyrect[3]= ybottom;
      Wxrig= Wxrect[2]= Wxrect[3]= xright;
      Wytop= Wyrect[1]= Wyrect[2]= ytop;
      Wnormx= WxNrec; Wnormy= WyNrec;        /* Нормали */
      WxNrec[0]=  1;  WyNrec[0]=  0;
      WxNrec[1]=  0;  WyNrec[1]= -1;
      WxNrec[2]= -1;  WyNrec[2]=  0;
      WxNrec[3]=  0;  WyNrec[3]=  1;
   }
   return (otw);
}  /* V_SetRclip */

/*------------------------------------------------- V_GetRclip
 * Возвращает текущее прямоугольное окно отсечения
 */
void V_GetRclip (xleft, ybottom, xright, ytop)
float *xleft, *ybottom, *xright, *ytop;
{
   *xleft=  Wxlef;  *ybottom= Wybot;
   *xright= Wxrig;  *ytop= Wytop;
}  /* V_GetRclip */

/*--------------------------------------------------- V_CSclip
 * Реализует алгоритм отсечения Коэна-Сазерленда с
 * кодированием концов отсекаемого отрезка
 *
 * int  V_CSclip (float *x0, float *y0, float *x1, float *y1)
 *
 * Отсекает отрезок, заданный значениями координат его
 * точек (x0,y0), (x1,y1), по окну отсечения, заданному
 * глобальными скалярами Wxlef, Wybot, Wxrig, Wytop
 *
 * Конечным точкам отрезка приписываются коды,
 * характеризующие его положение относительно окна отсечения
 * по правилу:
 *
 *  1001 | 1000 | 1010
 *  -----|------|-----
 *       | Окно |
 *  0001 | 0000 | 0010
 *  -----|------|-----
 *  0101 | 0100 | 0110
 *
 *  Отрезок целиком видим если оба его конца имеют коды 0000
 *  Если логическое И кодов концов не равно 0, то отрезок
 *  целиком вне окна и он просто отбрасывается.
 *  Если же результат этой операции = 0, то отрезок
 *  подозрительный. Он может быть и вне и пересекать окно.
 *  Для подозрительных отрезков определяются координаты их
 *  пересечений с теми сторонами, с которыми они могли бы
 *  пересечься в соответствии с кодами концов.
 *  При этом используется горизонтальность и вертикальность
 *  сторон окна, что позволяет определить одну из координат
 *  без вычислений.
 *  Часть отрезка, оставшаяся за окном отбрасывается.
 *  Оставшаяся часть отрезка проверяется на возможность его
 *  принятия или отбрасывания целиком. Если это невозможно,
 *  то процесс повторяется для другой стороны окна.
 *  На каждом цикле вычислений конечная точка отрезка,
 *  выходившая за окно, заменяется на точку, лежащую или на
 *  стороне окна или его продолжении.
 *
 *  Вспомогательная процедура Code вычисляет код положения
 *  для конца отрезка.
 *
 */

static float  CSxn, CSyn;   /* Координаты начала отрезка */

static int  CScode (void)  /* Определяет код точки xn, yn */
{  register int  i;
   i= 0;
   if (CSxn < Wxlef) ++i; else
   if (CSxn > Wxrig) i+= 2;
   if (CSyn < Wybot) i+= 4; else
   if (CSyn > Wytop) i+= 8;
   return (i);
}  /* CScode */

int   V_CSclip (x0, y0, x1, y1)
float *x0, *y0, *x1, *y1;
{
   float  CSxk, CSyk;   /* Координаты конца отрезка  */
   int    cn, ck,       /* Коды концов отрезка */
          visible,      /* 0/1 - не видим/видим*/
          ii, s;        /* Рабочие переменные  */
   float  dx, dy,       /* Приращения координат*/
          dxdy,dydx,    /* Наклоны отрезка к сторонам */
          r;            /* Рабочая переменная  */

   CSxk= *x1; CSyk= *y1;
   CSxn= *x1; CSyn= *y1; ck= CScode ();
   CSxn= *x0; CSyn= *y0; cn= CScode ();

/* Определение приращений координат и наклонов отрезка
 * к осям. Заодно сразу на построение передается отрезок,
 * состоящий из единственной точки, попавшей в окно
 */
   dx= CSxk - CSxn;
   dy= CSyk - CSyn;
   if (dx != 0) dydx= dy / dx; else {
      if (dy == 0) {
         if (cn==0 && ck==0) goto out; else goto all;
      }
   }
   if (dy != 0) dxdy= dx / dy;

/* Основной цикл отсечения */
   visible= 0;  ii= 4;
   do {
      if (cn & ck) break;       /* Целиком вне окна    */
      if (cn == 0 && ck == 0) { /* Целиком внутри окна */
         ++visible;  break;
      }
      if (!cn) {                /* Если Pn внутри окна, то */
         s= cn; cn= ck; ck= s;  /* перестить точки Pn,Pk и */
         r=CSxn; CSxn=CSxk; CSxk=r;  /* их коды, чтобы Pn  */
         r=CSyn; CSyn=CSyk; CSyk=r;  /* оказалась вне окна */
      }
      /* Теперь отрезок разделяется. Pn помещается в точку
       * пересечения отрезка со стороной окна.
       */
      if (cn & 1) {         /* Пересечение с левой стороной */
         CSyn= CSyn + dydx * (Wxlef-CSxn);
         CSxn= Wxlef;
      } else if (cn & 2) {  /* Пересечение с правой стороной*/
         CSyn= CSyn + dydx * (Wxrig-CSxn);
         CSxn= Wxrig;
      } else if (cn & 4) {  /* Пересечение в нижней стороной*/
         CSxn= CSxn + dxdy * (Wybot-CSyn);
         CSyn= Wybot;
      } else if (cn & 8) {  /*Пересечение с верхней стороной*/
         CSxn= CSxn + dxdy * (Wytop-CSyn);
         CSyn= Wytop;
      }
      cn= CScode ();        /* Перевычисление кода точки Pn */
   } while (--ii >= 0);
   if (visible) {
out:  *x0= CSxn;  *y0= CSyn;
      *x1= CSxk;  *y1= CSyk;
   }
all:
   return (visible);
}  /* V_CSclip */

/*--------------------------------------------------- V_FCclip
 *  Реализует алгоритм отсечения FC (Fast Clipping)
 *  Собкова-Поспишила-Янга, с кодированием линий
 *
 * int  V_FCclip (float *x0, float *y0, float *x1, float *y1)
 *
 * Отсекает отрезок, заданный значениями координат его
 * точек (x0,y0), (x1,y1), по окну отсечения, заданному
 * глобальными скалярами Wxlef, Wybot, Wxrig, Wytop
 *
 * Возвращает:
 * -1 - ошибка в задании окна
 *  0 - отрезок не видим
 *  1 - отрезок видим
 */

static float FC_xn, FC_yn, FC_xk, FC_yk;

static void Clip0_Top(void)
{FC_xn= FC_xn + (FC_xk-FC_xn)*(Wytop-FC_yn)/(FC_yk-FC_yn);
 FC_yn= Wytop; }

static void Clip0_Bottom(void)
{FC_xn= FC_xn + (FC_xk-FC_xn)*(Wybot-FC_yn)/(FC_yk-FC_yn);
 FC_yn= Wybot; }

static void Clip0_Right(void)
{FC_yn= FC_yn + (FC_yk-FC_yn)*(Wxrig-FC_xn)/(FC_xk-FC_xn);
 FC_xn= Wxrig; }

static void Clip0_Left(void)
{FC_yn= FC_yn + (FC_yk-FC_yn)*(Wxlef-FC_xn)/(FC_xk-FC_xn);
 FC_xn= Wxlef; }

static void Clip1_Top(void)
{FC_xk= FC_xk + (FC_xn-FC_xk)*(Wytop-FC_yk)/(FC_yn-FC_yk);
 FC_yk= Wytop; }

static void Clip1_Bottom(void)
{FC_xk= FC_xk + (FC_xn-FC_xk)*(Wybot-FC_yk)/(FC_yn-FC_yk);
 FC_yk= Wybot; }

static void Clip1_Right(void)
{FC_yk= FC_yk + (FC_yn-FC_yk)*(Wxrig-FC_xk)/(FC_xn-FC_xk);
 FC_xk= Wxrig; }

static void Clip1_Left(void)
{FC_yk= FC_yk + (FC_yn-FC_yk)*(Wxlef-FC_xk)/(FC_xn-FC_xk);
 FC_xk= Wxlef; }

int  V_FCclip (x0, y0, x1, y1)
float *x0, *y0, *x1, *y1;
{  int  Code= 0;
   int  visible= 0;             /* Отрезок невидим */

   FC_xn= *x0;  FC_yn= *y0;
   FC_xk= *x1;  FC_yk= *y1;

/*
 * Вычисление значения Code - кода отрезка
 * Биты 0-3 - для конечной точки, 4-7 - для начальной
 *
 */
   if (FC_yk > Wytop) Code+= 8; else
   if (FC_yk < Wybot) Code+= 4;

   if (FC_xk > Wxrig) Code+= 2; else
   if (FC_xk < Wxlef) Code+= 1;

   if (FC_yn > Wytop) Code+= 128; else
   if (FC_yn < Wybot) Code+= 64;

   if (FC_xn > Wxrig) Code+= 32; else
   if (FC_xn < Wxlef) Code+= 16;

/* Отсечение для каждого из 81-го случаев */

   switch (Code) {

     /* Из центра */

     case 0x00: ++visible;  break;
     case 0x01: Clip1_Left() ;   ++visible;  break;
     case 0x02: Clip1_Right();  ++visible;  break;
     case 0x04: Clip1_Bottom(); ++visible;  break;
     case 0x05: Clip1_Left() ;
                if (FC_yk < Wybot) Clip1_Bottom();
                ++visible;  break;
     case 0x06: Clip1_Right();
                if (FC_yk < Wybot) Clip1_Bottom();
                ++visible;  break;
     case 0x08: Clip1_Top();    ++visible;  break;
     case 0x09: Clip1_Left() ;
                if (FC_yk > Wytop) Clip1_Top();
                ++visible;  break;
     case 0x0A: Clip1_Right();
                if (FC_yk > Wytop) Clip1_Top();
                ++visible;  break;

     /* Слева */

     case 0x10: Clip0_Left();   ++visible;
     case 0x11: break;                          /* Отброшен */
     case 0x12: Clip0_Left();   Clip1_Right();
                ++visible;  break;
     case 0x14: Clip0_Left();
                if (FC_yn < Wybot) break;       /* Отброшен */
                Clip1_Bottom();
                ++visible;
     case 0x15: break;                          /* Отброшен */
     case 0x16: Clip0_Left();
                if (FC_yn < Wybot) break;       /* Отброшен */
                Clip1_Bottom();
                if (FC_xk > Wxrig) Clip1_Right();
                ++visible;
                break;
     case 0x18: Clip0_Left();
                if (FC_yn > Wytop) break;       /* Отброшен */
                Clip1_Top();
                ++visible;
     case 0x19: break;                          /* Отброшен */
     case 0x1A: Clip0_Left();
                if (FC_yn > Wytop) break;       /* Отброшен */
                Clip1_Top();
                if (FC_xk > Wxrig) Clip1_Right();
                ++visible;
                break;

     /* Справа */

     case 0x20: Clip0_Right(); ++visible;  break;
     case 0x21: Clip0_Right(); Clip1_Left(); ++visible;
     case 0x22: break;                          /* Отброшен */
     case 0x24: Clip0_Right();
                if (FC_yn < Wybot) break;       /* Отброшен */
                Clip1_Bottom();
                ++visible;
                break;
     case 0x25: Clip0_Right();
                if (FC_yn < Wybot) break;       /* Отброшен */
                Clip1_Bottom();
                if (FC_xk < Wxlef) Clip1_Left();
                ++visible;
     case 0x26: break;                          /* Отброшен */
     case 0x28: Clip0_Right();
                if (FC_yn > Wytop) break;       /* Отброшен */
                Clip1_Top();
                ++visible;
                break;
     case 0x29: Clip0_Right();
                if (FC_yn > Wytop) break;       /* Отброшен */
                Clip1_Top();
                if (FC_xk < Wxlef) Clip1_Left();
                ++visible;
     case 0x2A: break;                          /* Отброшен */

     /* Снизу */

     case 0x40: Clip0_Bottom(); ++visible;  break;
     case 0x41: Clip0_Bottom();
                if (FC_xn < Wxlef) break;       /* Отброшен */
                Clip1_Left() ;
                if (FC_yk < Wybot) Clip1_Bottom();
                ++visible;
                break;
     case 0x42: Clip0_Bottom();
                if (FC_xn > Wxrig) break;       /* Отброшен */
                Clip1_Right();
                ++visible;
     case 0x44:
     case 0x45:
     case 0x46: break;                          /* Отброшен */
     case 0x48: Clip0_Bottom();
                Clip1_Top();
                ++visible;
                break;
     case 0x49: Clip0_Bottom();
                if (FC_xn < Wxlef) break;       /* Отброшен */
                Clip1_Left() ;
                if (FC_yk > Wytop) Clip1_Top();
                ++visible;
                break;
     case 0x4A: Clip0_Bottom();
                if (FC_xn > Wxrig) break;       /* Отброшен */
                Clip1_Right();
                if (FC_yk > Wytop) Clip1_Top();
                ++visible;
                break;

     /* Снизу слева */

     case 0x50: Clip0_Left();
                if (FC_yn < Wybot) Clip0_Bottom();
                ++visible;
     case 0x51: break;                          /* Отброшен */
     case 0x52: Clip1_Right();
                if (FC_yk < Wybot) break;       /* Отброшен */
                Clip0_Bottom();
                if (FC_xn < Wxlef) Clip0_Left();
                ++visible;
     case 0x54:
     case 0x55:
     case 0x56: break;                          /* Отброшен */
     case 0x58: Clip1_Top();
                if (FC_xk < Wxlef) break;       /* Отброшен */
                Clip0_Bottom();
                if (FC_xn < Wxlef) Clip0_Left();
                ++visible;
     case 0x59: break;                          /* Отброшен */
     case 0x5A: Clip0_Left();
                if (FC_yn > Wytop) break;       /* Отброшен */
                Clip1_Right();
                if (FC_yk < Wybot) break;       /* Отброшен */
                if (FC_yn < Wybot) Clip0_Bottom();
                if (FC_yk > Wytop) Clip1_Top();
                ++visible;
                break;

     /* Снизу-справа */

     case 0x60: Clip0_Right();
                if (FC_yn < Wybot) Clip0_Bottom();
                ++visible;
                break;
     case 0x61: Clip1_Left() ;
                if (FC_yk < Wybot) break;       /* Отброшен */
                Clip0_Bottom();
                if (FC_xn > Wxrig) Clip0_Right();
                ++visible;
     case 0x62:
     case 0x64:
     case 0x65:
     case 0x66: break;                          /* Отброшен */
     case 0x68: Clip1_Top();
                if (FC_xk > Wxrig) break;       /* Отброшен */
                Clip0_Right();
                if (FC_yn < Wybot) Clip0_Bottom();
                ++visible;
                break;
     case 0x69: Clip1_Left() ;
                if (FC_yk < Wybot) break;       /* Отброшен */
                Clip0_Right();
                if (FC_yn > Wytop) break;       /* Отброшен */
                if (FC_yk > Wytop) Clip1_Top();
                if (FC_yn < Wybot) Clip0_Bottom();
                ++visible;
     case 0x6A: break;                          /* Отброшен */

     /* Сверху */

     case 0x80: Clip0_Top();
                ++visible;
                break;
     case 0x81: Clip0_Top();
                if (FC_xn < Wxlef) break;       /* Отброшен */
                Clip1_Left() ;
                ++visible;
                break;
     case 0x82: Clip0_Top();
                if (FC_xn > Wxrig) break;       /* Отброшен */
                Clip1_Right();
                ++visible;
                break;
     case 0x84: Clip0_Top();
                Clip1_Bottom();
                ++visible;
                break;
     case 0x85: Clip0_Top();
                if (FC_xn < Wxlef) break;       /* Отброшен */
                Clip1_Left() ;
                if (FC_yk < Wybot) Clip1_Bottom();
                ++visible;
                break;
     case 0x86: Clip0_Top();
                if (FC_xn > Wxrig) break;       /* Отброшен */
                Clip1_Right();
                if (FC_yk < Wybot) Clip1_Bottom();
                ++visible;
     case 0x88:
     case 0x89:
     case 0x8A: break;                          /* Отброшен */

     /* Сверху-слева */

     case 0x90: Clip0_Left();
                if (FC_yn > Wytop) Clip0_Top();
                ++visible;
     case 0x91: break;                          /* Отброшен */
     case 0x92: Clip1_Right();
                if (FC_yk > Wytop) break;       /* Отброшен */
                Clip0_Top();
                if (FC_xn < Wxlef) Clip0_Left();
                ++visible;
                break;
     case 0x94: Clip1_Bottom();
                if (FC_xk < Wxlef) break;       /* Отброшен */
                Clip0_Left();
                if (FC_yn > Wytop) Clip0_Top();
                ++visible;
     case 0x95: break;                          /* Отброшен */
     case 0x96: Clip0_Left();
                if (FC_yn < Wybot) break;       /* Отброшен */
                Clip1_Right();
                if (FC_yk > Wytop) break;       /* Отброшен */
                if (FC_yn > Wytop) Clip0_Top();
                if (FC_yk < Wybot) Clip1_Bottom();
                ++visible;
     case 0x98:
     case 0x99:
     case 0x9A: break;                          /* Отброшен */

     /* Сверху-справа */

     case 0xA0: Clip0_Right();
                if (FC_yn > Wytop) Clip0_Top();
                ++visible;
                break;
     case 0xA1: Clip1_Left() ;
                if (FC_yk > Wytop) break;       /* Отброшен */
                Clip0_Top();
                if (FC_xn > Wxrig) Clip0_Right();
                ++visible;
     case 0xA2: break;                          /* Отброшен */
     case 0xA4: Clip1_Bottom();
                if (FC_xk > Wxrig) break;       /* Отброшен */
                Clip0_Right();
                if (FC_yn > Wytop) Clip0_Top();
                ++visible;
                break;
     case 0xA5: Clip1_Left() ;
                if (FC_yk > Wytop) break;       /* Отброшен */
                Clip0_Right();
                if (FC_yn < Wybot) break;       /* Отброшен */
                if (FC_yk < Wybot) Clip1_Bottom();
                if (FC_yn > Wytop) Clip0_Top();
                ++visible;
     case 0xA6:                                 /* Отброшен */
     case 0xA8:
     case 0xA9:
     case 0xAA: break;

     /* Ошибка */

     default:   visible= -1;
                break;
   }  /* switch */

   if (visible > 0) {
      *x0= FC_xn;  *y0= FC_yn;
      *x1= FC_xk;  *y1= FC_yk;
   }
   return (visible);
}  /* V_FCclip */

/*--------------------------------------------------- V_LBclip
 *  Реализует алгоритм отсечения Лианга-Барски
 *  с параметрическим заданием линий
 *
 * int  V_LBclip (float *x0, float *y0, float *x1, float *y1)
 *
 * Отсекает отрезок, заданный значениями координат его
 * точек (x0,y0), (x1,y1), по окну отсечения, заданному
 * глобальными скалярами Wxlef, Wybot, Wxrig, Wytop
 *
 * Возвращает:
 *  0 - отрезок не видим
 *  1 - отрезок видим
 */

static float LB_t0, LB_t1;

static int  LB_tclip (p, q)
float p, q;
{
   int   accept;
   float r;

   accept= 1;                           /* Отрезок принят */
   if (p == 0) {
      if (q < 0) accept= 0;             /* Отбрасывание */
   } else {
      r= q/p;
      if (p < 0) {
         if (r > LB_t1) accept= 0;      /* Отбрасывание */
         else if (r > LB_t0) LB_t0= r;
      } else {
         if (r < LB_t0) accept= 0;      /* Отбрасывание */
         else if (r < LB_t1) LB_t1= r;
      }
   }
   return (accept);
}  /* LB_tclip */

int  V_LBclip (x0, y0, x1, y1)
float *x0, *y0, *x1, *y1;
{  int   visible;
   float dx, dy;

   visible= 0;
   LB_t0= 0;  LB_t1= 1;
   dx= *x1 - *x0;
   if (LB_tclip (-dx, *x0-Wxlef)) {
      if (LB_tclip (dx, Wxrig-*x0)) {
         dy= *y1 - *y0;
         if (LB_tclip (-dy, *y0-Wybot)) {
            if (LB_tclip (dy, Wytop-*y0)) {
               if (LB_t1 < 1) {
                  *x1= *x0 + LB_t1*dx;
                  *y1= *y0 + LB_t1*dy;
               }
               if (LB_t0 > 0) {
                  *x0= *x0 + LB_t0*dx;
                  *y0= *y0 + LB_t0*dy;
               }
               ++visible;
            }
         }
      }
   }
   return (visible);
}  /* V_LBclip */

/*--------------------------------------------------- V_CBclip
 *  Реализует алгоритм отсечения Кируса-Бека
 *  по произвольному выпуклому многоугольнику
 *  с параметрическим заданием линий
 *
 * int  V_CBclip (float *x0, float *y0, float *x1, float *y1)
 *
 * Отсекает отрезок, заданный значениями координат его
 * точек (x0,y0), (x1,y1), по окну отсечения, заданному
 * глобальными скалярами:
 * int   Windn - количество вершин в окне отсечения
 * float *Windx, *Windy   - массивы X,Y координат вершин
 * float *Wnormx, *Wnormy - массивы координат нормалей
 *                          к ребрам
 *
 * Возвращает:
 *  0 - отрезок не видим
 *  1 - отрезок видим
 */

int  V_CBclip (x0, y0, x1, y1)
float *x0, *y0, *x1, *y1;
{  int   ii, jj, visible, kw;
   float xn, yn, dx, dy, r;
   float CB_t0, CB_t1;          /* Параметры концов отрезка */
   float Qx, Qy;                /* Положение относ ребра */
   float Nx, Ny;                /* Перпендикуляр к ребру */
   float Pn, Qn;                /**/

   kw= Windn - 1;               /* Ребер в окне */
   visible= 1;
   CB_t0= 0;  CB_t1= 1;
   dx= *x1 - (xn= *x0);
   dy= *y1 - (yn= *y0);

   for (ii=0; ii<=kw; ++ii) {   /* Цикл по ребрам окна */
      Qx= xn - Windx[ii];       /* Положения относ ребра */
      Qy= yn - Windy[ii];
      Nx= Wnormx[ii];           /* Перепендикуляр к ребру */
      Ny= Wnormy[ii];
      Pn= dx*Nx + dy*Ny;        /* Скалярные произведения */
      Qn= Qx*Nx + Qy*Ny;

/* Анализ расположения */
      if (Pn == 0) {            /* Паралл ребру или точка */
         if (Qn < 0) {visible= 0;  break; }
      } else {
         r= -Qn/Pn;
         if (Pn < 0) {          /* Поиск верхнего предела t */
            if (r < CB_t0) {visible= 0;  break; }
            if (r < CB_t1) CB_t1= r;
         } else {               /* Поиск нижнего предела t */
            if (r > CB_t1) {visible= 0;  break; }
            if (r > CB_t0) CB_t0= r;
         }
      }
   }
   if (visible) {
      if (CB_t0 > CB_t1) visible= 0; else {
         if (CB_t0 > 0) {
            *x0= xn + CB_t0*dx;
            *y0= yn + CB_t0*dy;
         }
         if (CB_t1 < 1) {
            *x1= xn + CB_t1*dx;
            *y1= yn + CB_t1*dy;
         }
      }
   }
   return (visible);
}  /* V_CBclip */

/*=================================================== T_CLIP.C
 *
 * ТЕСТ ПРОЦЕДУР ОТСЕЧЕНИЯ
 */

#include <time.h>
#include <stdio.h>

/*--------------------------------------------------- V_DMclip
 *  Пустышка для процедур отсечения
 */

int  V_DMclip (x0, y0, x1, y1)
float *x0, *y0, *x1, *y1;
{  int   visible;
   visible= 1;
   return (visible);
}  /* V_DMclip */

/*---------------------------------------------------- ClipMsg
 * Печатает сообщение о результатах отсечения
 */
void ClipMsg (proc, visible, x0, y0, x1, y1, dt)
char *proc; int visible; float x0, y0, x1, y1, dt;
{
   if (visible < 0) {
      printf("*** ERROR (%s LineClip) - ", proc);
      printf("ошибка в координатах окна. ");
      printf("Прерывание с кодом ошибки 1.");
      exit (1);
   } else if (visible == 0)
      printf ("%s: Line is no visible dt=%f\n", proc, dt);
   else
      printf ("%s: ClipLine: x0=%f y0=%f x1=%f y1=%f dt=%f\n",
               proc, x0, y0, x1, y1, dt);
}  /* ClipMsg */

/*---------------------------------------------- MAIN T_CLIP.C
 */
void main (void)
{
   float Wxn, Wyn, Wxk, Wyk;
   float Xn, Yn, Xk, Yk, x0, y0, x1, y1;
   int   ii, numb= 1;
   float X_wind[100], Y_wind[100];
   float X_norm[100], Y_norm[100];
   int  visible;
   float dt;
   time_t t1, t2;
   long  ll, powt=10l;

   if (numb) goto set_win;

m0:printf ("----Вершин= %d ? ", numb);
   scanf  ("%d", &numb);
   for (ii=0; ii<numb; ++ii) {
      printf ("X_wind[%d], Y_wind[%d] ? ", ii, ii);
      scanf  ("%f%f", &X_wind[ii], &Y_wind[ii]);
   }
   ii= V_SetPclip (numb, X_wind, Y_wind, X_norm, Y_norm);
   printf ("V_SetPclip= %d\n", ii);
   if (ii) goto m0;
   for (ii=0; ii<numb; ++ii)
      printf ("ind=%d X_norm=%f, Y_norm=%f\n",
               ii, X_norm[ii], Y_norm[ii]);
   if (ii) goto m0;


/* Задание окна отсечения */
set_win:
   powt= 1l;
   V_GetRclip (&Wxn, &Wyn, &Wxk, &Wyk);
   for (;;) {
      printf ("Window: (Xn=%f Yn=%f Xk=%f Yk=%f) ? ",
               Wxn, Wyn, Wxk, Wyk);
      scanf  ("%f%f%f%f", &Wxn, &Wyn, &Wxk, &Wyk);
      if (!V_SetRclip (Wxn, Wyn, Wxk, Wyk)) break;
      printf ("Error in a window boundarys\n");
   }

/* Ввод координат отрезка */
   Xn= Wxn-1.0;  Yn= Wyn-1.0;  Xk= Wxk+1.0;  Yk= Wyk+1.0;

   for (;;) {
      printf ("------------- ");
      printf ("ClipWindow: Xn=%f Yn=%f Xk=%f Yk=%f\n",
               Wxlef, Wybot, Wxrig, Wytop);
      printf ("New Line: (Xn=%f Yn=%f Xk=%f Yk=%f) ? ",
               Xn, Yn, Xk, Yk);
      scanf  ("%f%f%f%f", &Xn, &Yn, &Xk, &Yk);

      ll= powt;
      t1= time(NULL);
      do {
         x0= Xn; y0= Yn; x1= Xk; y1= Yk;
         visible= V_DMclip (&x0, &y0, &x1, &y1);
      } while (--ll > 0l);
      t2= time (NULL);
      dt= ((float)(t2 - t1));
      ClipMsg ("DM", visible, x0, y0, x1, y1, dt);

      ll= powt;
      t1= time(NULL);
      do {
         x0= Xn; y0= Yn; x1= Xk; y1= Yk;
         visible= V_CSclip (&x0, &y0, &x1, &y1);
      } while (--ll > 0l);
      t2= time (NULL);
      dt= ((float)(t2 - t1));
      ClipMsg ("CS", visible, x0, y0, x1, y1, dt);

      ll= powt;
      t1= time(NULL);
      do {
         x0= Xn; y0= Yn; x1= Xk; y1= Yk;
         visible= V_FCclip (&x0, &y0, &x1, &y1);
      } while (--ll > 0l);
      t2= time (NULL);
      dt= ((float)(t2 - t1));
      ClipMsg ("FC", visible, x0, y0, x1, y1, dt);

      ll= powt;
      t1= time(NULL);
      do {
         x0= Xn; y0= Yn; x1= Xk; y1= Yk;
         visible= V_LBclip (&x0, &y0, &x1, &y1);
      } while (--ll > 0l);
      t2= time (NULL);
      dt= ((float)(t2 - t1));
      ClipMsg ("LB", visible, x0, y0, x1, y1, dt);

      ll= powt;
      t1= time(NULL);
      do {
         x0= Xn; y0= Yn; x1= Xk; y1= Yk;
         visible= V_CBclip (&x0, &y0, &x1, &y1);
      } while (--ll > 0l);
      t2= time (NULL);
      dt= ((float)(t2 - t1));
      ClipMsg ("CB", visible, x0, y0, x1, y1, dt);
   }
}

В данном приложении содержатся процедуры V_Plclip, реализующие простой алгоритм отсечения произвольного многоугольника по выпуклому многоугольному окну отсечения и тестовая программа проверки их работы.

Процедуры реализуют алгоритм, который, как и алгоритм Сазерленда-Ходгмана, последовательно отсекает весь многоугольник по каждому из ребер окна отсечения.

/*=================================================== V_PLCLIP
 * Файл V_PLCLIP.C - процедуры простого алгоритма отсечния
 *                   многоугольника
 * Последняя редакция:
 * 25.12.93  17:25
 */

#include <graphics.h>
#include "V_WINDOW.C"   /* Глобалы и проц работы с окнами */

/* Включаемый файл V_WINDOW.C содержит
 * подрограммы и глобалы для окон:
 *
 * V_SetPclip - установить размеры многоугольного окна
 *              отсечения
 * V_GetPclip - опросить параметры многоугольного окна
 *              отсечения
 * V_SetRclip - установить размеры прямоугольного окна
 *              отсечения
 * V_GetRclip - опросить   размеры прямоугольного окна
 *              отсечения
 *
 * Глобальные скаляры для алгоритмов отсечения по
 * прямоугольному окну - Коэна-Сазерленда, Fc-алгоритм,
 * Лианга-Барски
 *
 * static float Wxlef= 100.0, -- Координаты левого нижнего и
 *              Wybot= 100.0, -- правого верхнего углов окна
 *              Wxrig= 300.0, -- отсечения
 *              Wytop= 200.0;
 *
 * Глобальные скаляры для алгоритма Кируса-Бека
 * отсечения по многоугольному окну
 *
 * Координаты прямоугольного окна
 * static float Wxrect[4]= {100.0, 100.0, 300.0, 300.0 };
 * static float Wyrect[4]= {100.0, 200.0, 200.0, 100.0 };
 *
 * Перепендикуляры к сторонам прямоугольного окна
 * static float WxNrec[4]= {1.0,  0.0, -1.0, 0.0 };
 * static float WyNrec[4]= {0.0, -1.0,  0.0, 1.0 };
 *
 * Данные для многоугольного окна
 * static int   Windn=4;          -- Кол-во вершин у окна
 * static float *Windx=  Wxrect,  -- Координаты вершин окна
 *              *Windy=  Wyrect;
 * static float *Wnormx= WxNrec,  -- Координаты нормалей
 *              *Wnormy= WyNrec;
 */

/*-------------------------------------------------- Pl_clip0
 * Служебная процедура, отсекает многоугольник
 * относительно одного ребра окна
 *
 * Отсечение выполняется в цикле по сторонам многоугольника
 * При первом входе в цикл только вычисляются величины для
 * начальной точки: координаты, скалярное произведение,
 * определяющее ее расположение относительно ребра окна, и
 * код расположения.
 * При последующих входах в цикл эти значения вычисляются
 * для очередной вершины.
 * По значениям кодов расположения вершин для стороны
 * многоугольника определяется как она расположена
 * относительно ребра и вычисляются координаты результирующего
 * многоугольника.
 */

static int Pl_clip0 (N_reb, N_in, X_in, Y_in, X_ou, Y_ou)
int   N_reb, N_in;
float *X_in, *Y_in, *X_ou, *Y_ou;
{
   int  ii, jj;
   int  pozb,      /* Коды расположения начальной точки  */
        pozn,      /* многоугольника и точек тек стороны */
        pozk;      /* 0/1/2 - пред точка вне/на/внутри   */
   float Rx,Ry;    /* Координаты начала ребра окна */
   float Nx, Ny;   /* Нормаль к  ребру окна */
   float xb, yb;   /* Начальная точка многоугольника  */
   float xn, yn;   /* Начальная точка текущей стороны */
   float xk, yk;   /* Конечная  точка текущей стороны */
   float t;        /* Значение параметра точки пересечения */
   float Qb,Qn,Qk; /* Скалярные произведения */
   float *ptx_ou;

/* Запрос параметров ребра окна */
   Rx= Windx[N_reb];  Ry= Windy[N_reb];
   Nx= Wnormx[N_reb]; Ny= Wnormy[N_reb];

/* Цикл отсчения многоугольника ребром окна */
   ii= 0;  ++N_in;  ptx_ou= X_ou;
   while (--N_in >= 0) {
      if (N_in) {
         xk= *X_in++;  yk= *Y_in++;   /* Кон точка стороны  */
         Qk= (xk-Rx)*Nx + (yk-Ry)*Ny; /* Параметр положения */
         pozk= 1;                     /* 1 - точка на гр. */
         if (Qk < 0) --pozk; else     /* 0 - точка вне    */
         if (Qk > 0) ++pozk;          /* 2 - точка внутри */
      } else {
         xk= xb;  yk= yb;  Qk= Qb;  pozk= pozb;
      }
      if (!ii) {
         xb= xn= xk; yb= yn= yk; Qb= Qn= Qk; pozb= pozn= pozk;
         ++ii; continue;
      }
      jj= 0;
      switch (pozn*3 + pozk) {     /* Стар Нов Выход     */
         case 0: goto no_point;    /*  вне-вне нет       */
         case 1: goto endpoint;    /*  вне-на  конечная  */
         case 2: goto intersec;    /*  вне-вну перес,кон */
         case 3: goto no_point;    /*  на -вне нет       */
         case 4:                   /*  на -на  конечная  */
         case 5: goto endpoint;    /*  на -вну конечная  */
         case 6: goto no_end;      /*  вну-вне пересечен */
         case 7:                   /*  вну-на  конечная  */
         case 8: goto endpoint;    /*  вну-вну конечная  */
      }
no_end: ++jj;
intersec:
      t= Qn/(Qn-Qk);
      *X_ou++= xn + t*(xk-xn);
      *Y_ou++= yn + t*(yk-yn);
      if (!jj) {
endpoint:
         *X_ou++= xk;  *Y_ou++= yk;
      }
no_point:
      xn= xk;  yn= yk;  Qn= Qk;  pozn= pozk;
   }
   return (X_ou - ptx_ou);
}  /* Pl_clip0 */

/*--------------------------------------------------- V_Plclip
 * Простая процедура отсечения многоугольника
 * N_in       - число вершин во входном многоугольнике
 * X_in, Y_in - координаты вершин отсекаемого мног-ка
 *              этот массив будет испорчен
 * Возвращает:
 *  < 0 - ошибки
 * >= 0 - количество вершин в выходном многоугольнике
 * X_ou, Y_ou - координаты вершин отсеченного многоугольника
 */

int  V_Plclip (N_in, X_in, Y_in, X_ou, Y_ou)
int   N_in;
float *X_in, *Y_in, *X_ou, *Y_ou;
{
   int  ii, N_ou; float *ptr;

   if ((N_ou= N_in) < 3) {N_ou= -1;  goto all; }
   if (Windn < 3) {N_ou= -2;  goto all; }
   for (ii=0; ii<Windn; ++ii) {
      N_ou= Pl_clip0 (ii, N_ou, X_in, Y_in, X_ou, Y_ou);
      ptr= X_in;  X_in= X_ou;  X_ou= ptr;
      ptr= Y_in;  Y_in= Y_ou;  Y_ou= ptr;
   }
   if (!(Windn & 1)) {
      ii= N_ou;
      while (--ii >= 0) {*X_ou++= *X_in++; *Y_ou++= *Y_in++; }
   }
all:
   return N_ou;
}  /* V_Plclip */

/*=================================================== T_PLCLIP
 * ТЕСТ процедуры V_Plclip для отсечения многоугольника
 *
 * При первом входе устанавливается восьмиугольное окно
 * отсечения:
 * X: 150, 100, 100, 150, 250, 300, 300, 250
 * Y: 100, 150, 250, 300, 300, 250, 150, 100
 *
 * И на нем отсекается треугольник:
 * (10,160),(90,220),(170,160)
 *
 * Затем выдается запрос на количество вершин в
 * новом отсекаемом многоугольнике:
 * --- Vertexs in polyline= XX ?
 * При вводе числа > 0 будут запрашиваться координаты вершин
 *                     много-ка и выполняться его отсечение
 * При вводе числа = 0 программа затребует ввод координат
 *                     нового прямоугольного окна отсечения
 * При вводе числа < 0 программа запросит переустановку
 *                     многоугольного окна отсечения:
 *
 * ----Vertexs in clip window= XX ?
 * При вводе числа > 0 будут запрашиваться координаты вершин.
 * При вводе числа = 0 программа затребует ввод координат
 *                     прямоугольного окна.
 * При вводе числа < 0 программа закончится.
 */

#include <graphics.h>
#include "V_PLCLIP.C"

/*--------------------------------------------------- DrawPoly
 * Чертит контур многоугольника
 */
void DrawPoly (col, n, x, y)
int col, n; float *x, *y;
{  int  ii, jj;
   setcolor (col);
   for (ii=0; ii<n; ++ii) {
      if ((jj= ii+1) >= n) jj= 0;
      line (x[ii], y[ii], x[jj], y[jj]);
   }
}  /* DrawPoly */

/*---------------------------------------------------- CLR_STR
 * Зачищает строку выводом в нее пробелов
 */
void CLR_STR (void)
{
printf ("                                                \r");
}

/*------------------------------------------------ PLCLIP_MAIN
 */
void main (void)
{  int   ii, jj,
         fon;           /* Индекс фона  */
   float Wxn,Wyn,       /* Прямоугольный отсекатель */
         Wxk,Wyk;
   int   N_wind= 0;     /* Вводимый отсекатель */
   float X_wind[100],
         Y_wind[100];
   float X_norm[100],
         Y_norm[100];
   int   wnum;          /* Запрошенный отсекатель */
   float *wx,*wy,*wnx,*wny;
   int   N_poly= 0;     /* Отсекаемый многугольник */
   float X_poly[100],
         Y_poly[100];
   int   N_clip= 0;     /* Отсеченный многугольник */
   float X_clip[100],
         Y_clip[100];
   int   entry= 0;      /* 0/1 - нет/был вывод по умолчанию */
   int   gdriver= DETECT, gmode;

   initgraph (&gdriver, &gmode, "");
   fon= 0;                      /* Цвет фона */

   setbkcolor(fon);             /* Очистка экрана */
   cleardevice();

/*--------------- Установить окно отсечения ----------------*/
new_window:
   gotoxy (1,1);
   if (!entry) {
      N_wind= 8;  wx= X_wind;  wy= Y_wind;
      *wx++= 150; *wx++= 100;  *wx++= 100; *wx++= 150;
      *wy++= 100; *wy++= 150;  *wy++= 250; *wy++= 300;

      *wx++= 250; *wx++= 300;  *wx++= 300; *wx++= 250;
      *wy++= 300; *wy++= 250;  *wy++= 150; *wy++= 100;
      goto wr_window;
   }
   if (!N_poly) goto set_rect;

/*---------- Задание многоугольного окна отсечения ---------*/
set_window:
   CLR_STR ();
   printf ("----Vertexs in clip window= %d ? ", N_wind);
   scanf  ("%d", &N_wind);
   if (N_wind < 0) goto all;
   if (!N_wind) goto set_rect;
   for (ii=0; ii<N_wind; ++ii) {
      CLR_STR ();
      printf ("X_wind[%d], Y_wind[%d] ? ", ii, ii);
      scanf  ("%f%f", &X_wind[ii], &Y_wind[ii]);
   }
wr_window:
   jj= V_SetPclip (N_wind, X_wind, Y_wind, X_norm, Y_norm);
   if (jj) {
      printf ("Error=%d in polyline window\n", jj);
      goto set_window;
   } else goto ou_win;

/*---------- Задание прямоугольного окна отсечения ---------*/
set_rect:
   V_GetRclip (&Wxn, &Wyn, &Wxk, &Wyk);
get_rect:
   CLR_STR ();
   printf ("Rect window: (Xn=%f Yn=%f Xk=%f Yk=%f) ? ",
            Wxn, Wyn, Wxk, Wyk);
   scanf  ("%f%f%f%f", &Wxn, &Wyn, &Wxk, &Wyk);
wr_rect:
   jj= V_SetRclip (Wxn, Wyn, Wxk, Wyk);
   if (jj) {
      printf ("Error=%d in rectangle window\n", jj);
      goto get_rect;
   }

/*--------------- Прорисовка окна отсечения ----------------*/
ou_win:
   wnum= V_GetPclip (&wx, &wy, &wnx, &wny);
   DrawPoly (LIGHTRED, wnum, wx, wy);

/*------- Ввод координат отсекаемого многоугольника --------*/

set_poly:
   gotoxy (1,1);
   if (!entry) { /* При первом входе отрисовка по умолчанию */
      N_poly= 3;
      X_poly[0]=  10;  X_poly[1]=  90;  X_poly[2]= 170;
      Y_poly[0]= 160;  Y_poly[1]= 220;  Y_poly[2]= 160;
   } else {
      CLR_STR ();
      printf ("--- Vertexs in polyline= %d ? ",N_poly);
      scanf  ("%d", &N_poly);
      if (N_poly <= 0) goto new_window;
      for (ii=0; ii<N_poly; ++ii) {
         printf ("                                   \r");
         printf ("X_poly[%d], Y_poly[%d] ? ", ii, ii);
         scanf  ("%f%f", &X_poly[ii], &Y_poly[ii]);
      }
   }
   ++entry;

/*---------- Прорисовка отсекателя и отсекаемого -----------*/
   wnum= V_GetPclip (&wx, &wy, &wnx, &wny);
   DrawPoly (LIGHTRED, wnum, wx, wy);
   DrawPoly (LIGHTGREEN, N_poly, X_poly, Y_poly);


/*----------------------- Отсечение ------------------------*/
   N_clip= V_Plclip(N_poly, X_poly, Y_poly, X_clip, Y_clip);

/*----------------- Прорисовка отсеченного -----------------*/
   DrawPoly (YELLOW, N_clip, X_clip, Y_clip);
   goto set_poly;

all:
   closegraph();
}  /* PLCLIP_MAIN */

¹ Переход к модели с перечислением занятых точек также возможен из любой другой, но при решении проблем точности аппроксимации.

НОВОСТИ ФОРУМА Рыцари теории эфира

10.11.2021 - 12:37: ПЕРСОНАЛИИ - Personalias -> WHO IS WHO - КТО ЕСТЬ КТО - Карим_Хайдаров. 10.11.2021 - 12:36: СОВЕСТЬ - Conscience -> РАСЧЕЛОВЕЧИВАНИЕ ЧЕЛОВЕКА. КОМУ ЭТО НАДО? - Карим_Хайдаров. 10.11.2021 - 12:36: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от д.м.н. Александра Алексеевича Редько - Карим_Хайдаров. 10.11.2021 - 12:35: ЭКОЛОГИЯ - Ecology -> Биологическая безопасность населения - Карим_Хайдаров. 10.11.2021 - 12:34: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> Проблема государственного терроризма - Карим_Хайдаров. 10.11.2021 - 12:34: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> ПРАВОСУДИЯ.НЕТ - Карим_Хайдаров. 10.11.2021 - 12:34: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Вадима Глогера, США - Карим_Хайдаров. 10.11.2021 - 09:18: НОВЫЕ ТЕХНОЛОГИИ - New Technologies -> Волновая генетика Петра Гаряева, 5G-контроль и управление - Карим_Хайдаров. 10.11.2021 - 09:18: ЭКОЛОГИЯ - Ecology -> ЭКОЛОГИЯ ДЛЯ ВСЕХ - Карим_Хайдаров. 10.11.2021 - 09:16: ЭКОЛОГИЯ - Ecology -> ПРОБЛЕМЫ МЕДИЦИНЫ - Карим_Хайдаров. 10.11.2021 - 09:15: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Екатерины Коваленко - Карим_Хайдаров. 10.11.2021 - 09:13: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Вильгельма Варкентина - Карим_Хайдаров.