Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Графика /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Заполнение многоугольника и заливка области - Программирование от RIN.RU
Заполнение многоугольника и заливка области



Приложение 5. Процедуры заполнения многоугольника


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


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


V_FP0 - простая процедура заливки многоугольника



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


#include
#include


#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 min= iarr[ll= ii];
for (jj=ii+1; 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 */




Тестовая процедуры 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 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 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_FP1
* Более эффективная по сравнению с V_FP0 подпрограмма
* однотонной заливки многоугольника методом построчного
* сканирования.
*
* Дублирувание занесения пикселов практически отсутствует
*
*/


#include
#include


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




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




<<<  НазадВперед  >>>
 1  2  3  4 


 8  Комментарии к статье  8 8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь