Приложение 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  Обсудить в чате