Алгоритмы взяты из прекрасной книги
П.В.Вельтмандер "Машинная графика"

В большинстве приложений используется одно из существенных достоинств растровых устройств - возможность заполнения областей экрана.

Существует две разновидности заполнения:

· первая, связанная как с интерактивной работой, так и с программным синтезом изображения, служит для заполнения внутренней части многоугольника, заданного координатами его вершин.

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

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

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

Определить принадлежность пиксела многоугольнику можно, например, подсчетом суммарного угла с вершиной на пикселе при обходе контура многоугольника. Если пиксел внутри, то угол будет равен 360^°, если вне - 0^° (рис. ).

Вычисление принадлежности должно производиться для всех пикселов экрана и так как большинство пикселов скорее всего вне многоугольников, то данный способ слишком расточителен. Объем лишних вычислений в некоторых случаях можно сократить использованием прямоугольной оболочки - минимального прямоугольника, объемлющего интересующий объект, но все равно вычислений будет много. Другой метод определения принадлежности точки внутренней части многоугольника будет рассмотрен ниже при изучении отсечения отрезков по алгоритму Кируса-Бека.

Реально используются алгоритмы построчного заполнения, основанные на том, что соседние пикселы в строке скорее всего одинаковы и меняются только там где строка пересекается с ребром многоугольника. Это называется когерентностью растровых строк (строки сканирования Y_i, Y_i+1, Y_i+2 на рис. ). При этом достаточно определить X-координаты пересечений строк сканирования с ребрами. Пары отсортированных точек пересечения задают интервалы заливки.

Кроме того, если какие-либо ребра пересекались i-й строкой, то они скорее всего будут пересекаться также и строкой i+1. (строки сканирования Y_i и Y_i+1 на рис. 0.2). Это называется когерентностью ребер. При переходе к новой строке легко вычислить новую X-координату точки пересечения ребра, используя X-координату старой точки пересечения и тангенс угла наклона ребра:

(тангенс угла наклона ребра - k = dy/dx, так как dy = 1, то 1/k = dx).

Смена же количества интервалов заливки происходит только тогда, когда в строке сканирования появляется вершина.

Учет когерентности строк и ребер позволяет построить для заполнения многоугольников различные высокоэффективные алгоритмы построчного сканирования. Для каждой строки сканирования рассматриваются только те ребра, которые пересекают строку. Они задаются списком активных ребер (САР). При переходе к следующей строке для пересекаемых ребер перевычисляются X-координаты пересечений. При появлении в строке сканирования вершин производится перестройка САР. Ребра, которые перестали пересекаться, удаляются из САР, а все новые ребра, пересекаемые строкой заносятся в него.

Общая схема алгоритма, динамически формирующего список активных ребер и заполняющего многоугольник снизу-вверх, следующая:

1. Подготовить служебные целочисленные массивы Y-координат вершин и номеров вершин.
2. Совместно отсортировать Y-координаты по возрастанию и массив номеров вершин для того, чтобы можно было определить исходный номер вершины.
3. Определить пределы заполнения по оси Y - Y_мin и Y_max. Стартуя с текущим значением Y_tek = Y_min, исполнять пункты 4-9 до завершения раскраски.
4. Определить число вершин, расположенных на строке Y_tek - текущей строке сканирования.
5. Если вершины есть, то для каждой из вершин дополнить список активных ребер, используя информацию о соседних вершинах.
   Для каждого ребра в список активных ребер заносятся:

   • максимальное значение Y-координаты ребра,
   • приращение X-координаты при увеличении Y на 1,
   • начальное значение X-координаты.

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

6. По списку активных ребер определяется Y_след - Y-координата ближайшей вершины. (Вплоть до Y_след можно не заботиться о модификации САР а только менять X-координаты пересечений строки сканирования с активными ребрами).
7. В цикле от Y_tek до Y_след:

   • выбрать из списка активных ребер и отсортировать X-координаты пересечений активных ребер со строкой сканирования;
   • определить интервалы и выполнить закраску;
   • перевычислить координаты пересечений для следующей строки сканирования.

8. Проверить не достигли ли максимальной Y-координаты. Если достигли, то заливка закончена, иначе выполнить пункт .
9. Очистить список активных ребер от ребер, закончившихся на строке Y_след и перейти к пункту 4.

В Приложении 5 приведены две подпрограммы заполнения многоугольника - V_FP0 и V_FP1. Первая реализует данный (простейший) алгоритм. Эта программа вполне работоспособна, но генерирует двух и трехкратное занесение части пикселов. Это мало приемлемо для устройств вывода типа матричных или струйных принтеров.

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

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

Для рассмотрения алгоритма предположим, что надо отсортировать числа, заданные в массиве с именем "Исходный_массив"; количество сортируемых чисел задается скаляром "Кол-во_чисел"; сортируемые числа J удовлетворяют условию:

Для сортировки потребуются описания:

int  Max_число;        /* Верхняя граница значений */
int  *Повтор;          /* Длина этого массива = Max_число */
int  Кол_чисел;        /* Кол-во сортируемых чисел */
int  *Исходный_массив; /* Длина этого массива >= Кол_чисел */
int  *Результат;       /* Длина этого массива >= Кол_чисел */
int  ii,jj, kk;        /* Рабочие переменные */

1. Обнуляется служебный массив для подсчета числа повторений исходных кодов.

      for (ii=0; ii<Max_число; ++ii) Повтор[ii]= 0;
   

2. Сортируемый массив просматривается и вычисляется количество раз повторений каждого числа:

      for (ii= 0; ii < Кол_чисел; ++ii) {
         jj= Исходный_массив[ii];
         Повтор[jj]= Повтор[jj] + 1;
      }
   

3. Суммируется количество повторений каждого числа, так что значение Повтор[J] даст начальное расположение группы чисел, равных J, в отсортированном массиве:

      jj= 0;
      for (ii=0; ii<Max_число; ++ii) {
         jj= jj + Повтор[ii];
         Повтор[ii]= jj;
      }
   

4. Просматривается исходный массив и числа из него заносятся в массив результатов той же длины. Индекс занесения числа J в массив результатов равен значению J-го элемента массива Повтор. После занесения числа J значение Повтор[J] уменьшается на 1:

      for (ii= 0; ii < Кол_чисел; ++ii) {
         jj= Исходный_массив[ii];
         kk= Повтор[jj];
         Результат[kk]= jj;
         Повтор[jj]= Повтор[jj] - 1;
      }
   

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

При этом тем или иным образом задается заливаемая (перекрашиваемая) область, код пиксела, которым будет выполняться заливка и начальная точка в области, начиная с которой начнется заливка.

По способу задания области делятся на два типа:

· гранично-определенные, задаваемые своей (замкнутой) границей такой, что коды пикселов границы отличны от кодов внутренней, перекрашиваемой части области. На коды пикселы внутренней части области налагаются два условия - они должны быть отличны от кода пикселов границы и кода пиксела перекраски. Если внутри гранично-определенной области имеется еще одна граница, нарисованная пикселами с тем же кодом, что и внешняя граница, то соответствующая часть области не должна перекрашиваться;

· внутренне-определенные, нарисованные одним определенным кодом пиксела. При заливке этот код заменяется на новый код закраски.

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

Заливаемая область или ее граница - некоторое связное множество пикселов. По способам доступа к соседним пикселам области делятся на 4-х и 8-ми связные. В 4-х связных областях доступ к соседним пикселам осуществляется по четырем направлениям - горизонтально влево и вправо и в вертикально вверх и вниз. В 8-ми связных областях к этим направлениям добавляются еще 4 диагональных. Используя связность мы может, двигаясь от точки затравки, достичь и закрасить все пикселы области.

Важно отметить, что для 4-х связной прямоугольной области граница 8-ми связна (рис. а) и наоборот у 8-ми связной области граница 4-х связна (см. рис. б). Поэтому заполнение 4-х связной области 8-ми связным алгоритмом может привести к "просачиванию" через границу и заливке пикселов в примыкающей области.

В общем, 4-х связную область мы можем заполнить как 4-х, так и 8-ми связным алгоритмом. Обратное же неверно. Так область на рис. а мы можем заполнить любым алгоритмом, а область на рис. б, состоящую из двух примыкающих 4-х связных областей можно заполнить только 8-ми связным алгоритмом.

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

Рассмотрим простой алгоритм заливки гранично-определенной 4-х связной области. В [] приведена рекурсивная реализация подпрограммы заливки 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_FAB4R */

Заливка выполняется следующим образом:

· определяется является ли пиксел граничным или уже закрашенным,

· если нет, то пиксел перекрашивается, затем проверяются и если надо перекрашиваются 4 соседних пиксела.

Полный текст тестовой программы V_FAB4R с использованием этой подпрограммы приведен в Приложении 6.

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

В [] приведен итеративный алгоритм закраски 4-х связной гранично-определенной области. Логика работы алгоритма следующая:

Поместить координаты затравки в стек

Пока стек не пуст

Извлечь координаты пиксела из стека.

Перекрасить пиксел.

Для всех четырех соседних пикселов проверить

является ли он граничным или уже перекрашен.

Если нет, то занести его координаты в стек.

На рис.  а) показан выбранный порядок перебора соседних пикселов, а на рис.  б) соответствующий ему порядок закраски простой гранично-определенной области.

a) Порядок перебора соседних пикселов

б) Порядок заливки области

Ясно, что такой алгоритм экономнее, так как в стек надо упрятывать только координаты.

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

Программа V_FAB4, реализующая данный алгоритм, приведена в Приложении 6.

Сравнительные прогоны тестовых программ V_FAB4R и V_FAB4 подтвердили соображения о неэкономности рекурсивного алгоритма: при стандартном окне стека в 64 K с помощью рекурсивной программы можно закрасить квадратик не более чем 57×57 пикселов. Итеративная же программа V_FAB4 при тех же условиях позволяет закрасить прямоугольник размером 110×110 истратив на массив координат 16382 байта.

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

Использует пространственную когерентность:

· пикселы в строке меняются только на границах;

· при перемещении к следующей строке размер заливаемой строки скорее всего или неизменен или меняется на 1 пиксел.

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

Последовательность работы алгоритма для гранично определенной области следующая:

1. Координата затравки помещается в стек, затем до исчерпания стека выполняются пункты 2-4.

2. Координата очередной затравки извлекается из стека и выполняется максимально возможное закрашивание вправо и влево по строке с затравкой, т.е. пока не попадется граничный пиксел. Пусть это Хлев и Хправ, соответственно.

3. Анализируется строка ниже закрашиваемой в пределах от Хлев до Хправ и в ней находятся крайние правые пикселы всех незакрашенных фрагментов. Их координаты заносятся в стек.

4. То же самое проделывается для строки выше закрашиваемой.

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

В данном приложении приведены две процедуры заливки многоугольника: 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();
}

[1]

Encarnacao J. Einfurung in die Graphische Datenverarbeiterung// Eurographics '89. Tutorial Notes 1. Hamburg, FRG, September 4-8, 1989. 122 s.

[2]

Ньюмен У., Спрулл Р. Основы интерактивной машинной графики. Пер. с англ. М.: Мир, 1976.

[3]

Роджерс Д. Алгоритмические основы машинной графики. Пер. с англ. М.: Мир, 1989. 512 c.

[4]

Фоли Дж., вэн Дэм А. Основы интерактивной машинной графики: В 2-х книгах. Пер. с англ. М.: Мир, 1985.

[5]

Антонофф М., Линдерхолм О. Лазерные принтеры// Компьютер Пресс, сборник N 1, 1989, с. 3-8.