Основные алгоритмы компьютерной графики
Процедуры заполнения многоугольника
0.16.1 V_FP0 - простая процедура заливки многоугольника 0.16.2 Тестовая процедуры V_FP0 0.16.3 V_FP1 - эффективная процедура заливки многоугольника 0.16.4 Тестовая процедуры V_FP1 В данном приложении приведены две процедуры заливки
многоугольника: V_FP0 и V_FP1. Обе они реализуют алгоритм
построчного заполнения, описанный в разделе 5.
В данных процедурах все массивы используются, начиная с
элемента с индексом 1, а не 0, как это принято в языке C.
0.16.1 V_FP0 - простая процедура заливки многоугольника
/*===================================================== 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 */
0.16.2 Тестовая процедуры 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();
}
0.16.3 V_FP1 - эффективная процедура заливки многоугольника
/*===================================================== 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 */
0.16.4 Тестовая процедуры 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();
}
НОВОСТИ ФОРУМА Рыцари теории эфира 10.11.2021 - 12:37: ПЕРСОНАЛИИ - Personalias -> WHO IS WHO - КТО ЕСТЬ КТО - Карим_Хайдаров.СОВЕСТЬ - Conscience -> РАСЧЕЛОВЕЧИВАНИЕ ЧЕЛОВЕКА. КОМУ ЭТО НАДО? - Карим_Хайдаров.ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от д.м.н. Александра Алексеевича Редько - Карим_Хайдаров.ЭКОЛОГИЯ - Ecology -> Биологическая безопасность населения - Карим_Хайдаров.ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> Проблема государственного терроризма - Карим_Хайдаров.ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> ПРАВОСУДИЯ.НЕТ - Карим_Хайдаров.ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Вадима Глогера, США - Карим_Хайдаров.НОВЫЕ ТЕХНОЛОГИИ - New Technologies -> Волновая генетика Петра Гаряева, 5G-контроль и управление - Карим_Хайдаров.ЭКОЛОГИЯ - Ecology -> ЭКОЛОГИЯ ДЛЯ ВСЕХ - Карим_Хайдаров.ЭКОЛОГИЯ - Ecology -> ПРОБЛЕМЫ МЕДИЦИНЫ - Карим_Хайдаров.ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Екатерины Коваленко - Карим_Хайдаров.ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Вильгельма Варкентина - Карим_Хайдаров.
