В данном приложении содержатся процедуры V_Plclip, реализующие простой алгоритм отсечения произвольного многоугольника по выпуклому многоугольному окну отсечения и тестовая программа проверки их работы. Процедуры реализуют алгоритм, который, как и алгоритм Сазерленда-Ходгмана, последовательно отсекает весь многоугольник по каждому из ребер окна отсечения. V_Plclip - простой алгоритм отсечения многоугольника /*=================================================== V_PLCLIP * Файл V_PLCLIP.C - процедуры простого алгоритма отсечния * многоугольника * Последняя редакция: * 25.12.93 17:25 */ #include #include "V_WINDOW.C" /* Глобалы и проц работы с окнами */ /* Включаемый файл V_WINDOW.C содержит * подрограммы и глобалы для окон: * * V_SetPclip - установить размеры многоугольного окна * отсечения * V_GetPclip - опросить параметры многоугольного окна * отсечения * V_SetRclip - установить размеры прямоугольного окна * отсечения * V_GetRclip - опросить размеры прямоугольного окна * отсечения * * Глобальные скаляры для алгоритмов отсечения по * прямоугольному окну - Коэна-Сазерленда, Fc-алгоритм, * Лианга-Барски * * static float Wxlef= 100.0, -- Координаты левого нижнего и * Wybot= 100.0, -- правого верхнего углов окна * Wxrig= 300.0, -- отсечения * Wytop= 200.0; * * Глобальные скаляры для алгоритма Кируса-Бека * отсечения по многоугольному окну * * Координаты прямоугольного окна * static float Wxrect[4]= {100.0, 100.0, 300.0, 300.0 }; * static float Wyrect[4]= {100.0, 200.0, 200.0, 100.0 }; * * Перепендикуляры к сторонам прямоугольного окна * static float WxNrec[4]= {1.0, 0.0, -1.0, 0.0 }; * static float WyNrec[4]= {0.0, -1.0, 0.0, 1.0 }; * * Данные для многоугольного окна * static int Windn=4; -- Кол-во вершин у окна * static float *Windx= Wxrect, -- Координаты вершин окна * *Windy= Wyrect; * static float *Wnormx= WxNrec, -- Координаты нормалей * *Wnormy= WyNrec; */ /*-------------------------------------------------- Pl_clip0 * Служебная процедура, отсекает многоугольник * относительно одного ребра окна * * Отсечение выполняется в цикле по сторонам многоугольника * При первом входе в цикл только вычисляются величины для * начальной точки: координаты, скалярное произведение, * определяющее ее расположение относительно ребра окна, и * код расположения. * При последующих входах в цикл эти значения вычисляются * для очередной вершины. * По значениям кодов расположения вершин для стороны * многоугольника определяется как она расположена * относительно ребра и вычисляются координаты результирующего * многоугольника. */ static int Pl_clip0 (N_reb, N_in, X_in, Y_in, X_ou, Y_ou) int N_reb, N_in; float *X_in, *Y_in, *X_ou, *Y_ou; { int ii, jj; int pozb, /* Коды расположения начальной точки */ pozn, /* многоугольника и точек тек стороны */ pozk; /* 0/1/2 - пред точка вне/на/внутри */ float Rx,Ry; /* Координаты начала ребра окна */ float Nx, Ny; /* Нормаль к ребру окна */ float xb, yb; /* Начальная точка многоугольника */ float xn, yn; /* Начальная точка текущей стороны */ float xk, yk; /* Конечная точка текущей стороны */ float t; /* Значение параметра точки пересечения */ float Qb,Qn,Qk; /* Скалярные произведения */ float *ptx_ou; /* Запрос параметров ребра окна */ Rx= Windx[N_reb]; Ry= Windy[N_reb]; Nx= Wnormx[N_reb]; Ny= Wnormy[N_reb]; /* Цикл отсчения многоугольника ребром окна */ ii= 0; ++N_in; ptx_ou= X_ou; while (--N_in >= 0) { if (N_in) { xk= *X_in++; yk= *Y_in++; /* Кон точка стороны */ Qk= (xk-Rx)*Nx + (yk-Ry)*Ny; /* Параметр положения */ pozk= 1; /* 1 - точка на гр. */ if (Qk < 0) --pozk; else /* 0 - точка вне */ if (Qk > 0) ++pozk; /* 2 - точка внутри */ } else { xk= xb; yk= yb; Qk= Qb; pozk= pozb; } if (!ii) { xb= xn= xk; yb= yn= yk; Qb= Qn= Qk; pozb= pozn= pozk; ++ii; continue; } jj= 0; switch (pozn*3 + pozk) { /* Стар Нов Выход */ case 0: goto no_point; /* вне-вне нет */ case 1: goto endpoint; /* вне-на конечная */ case 2: goto intersec; /* вне-вну перес,кон */ case 3: goto no_point; /* на -вне нет */ case 4: /* на -на конечная */ case 5: goto endpoint; /* на -вну конечная */ case 6: goto no_end; /* вну-вне пересечен */ case 7: /* вну-на конечная */ case 8: goto endpoint; /* вну-вну конечная */ } no_end: ++jj; intersec: t= Qn/(Qn-Qk); *X_ou++= xn + t*(xk-xn); *Y_ou++= yn + t*(yk-yn); if (!jj) { endpoint: *X_ou++= xk; *Y_ou++= yk; } no_point: xn= xk; yn= yk; Qn= Qk; pozn= pozk; } return (X_ou - ptx_ou); } /* Pl_clip0 */ /*--------------------------------------------------- V_Plclip * Простая процедура отсечения многоугольника * N_in - число вершин во входном многоугольнике * X_in, Y_in - координаты вершин отсекаемого мног-ка * этот массив будет испорчен * Возвращает: * < 0 - ошибки * >= 0 - количество вершин в выходном многоугольнике * X_ou, Y_ou - координаты вершин отсеченного многоугольника */ int V_Plclip (N_in, X_in, Y_in, X_ou, Y_ou) int N_in; float *X_in, *Y_in, *X_ou, *Y_ou; { int ii, N_ou; float *ptr; if ((N_ou= N_in) < 3) {N_ou= -1; goto all; } if (Windn < 3) {N_ou= -2; goto all; } for (ii=0; ii N_ou= Pl_clip0 (ii, N_ou, X_in, Y_in, X_ou, Y_ou); ptr= X_in; X_in= X_ou; X_ou= ptr; ptr= Y_in; Y_in= Y_ou; Y_ou= ptr; } if (!(Windn & 1)) { ii= N_ou; while (--ii >= 0) {*X_ou++= *X_in++; *Y_ou++= *Y_in++; } } all: return N_ou; } /* V_Plclip */ Тест процедуры V_Plclip /*=================================================== T_PLCLIP * ТЕСТ процедуры V_Plclip для отсечения многоугольника * * При первом входе устанавливается восьмиугольное окно * отсечения: * X: 150, 100, 100, 150, 250, 300, 300, 250 * Y: 100, 150, 250, 300, 300, 250, 150, 100 * * И на нем отсекается треугольник: * (10,160),(90,220),(170,160) * * Затем выдается запрос на количество вершин в * новом отсекаемом многоугольнике: * --- Vertexs in polyline= XX ? * При вводе числа > 0 будут запрашиваться координаты вершин * много-ка и выполняться его отсечение * При вводе числа = 0 программа затребует ввод координат * нового прямоугольного окна отсечения * При вводе числа < 0 программа запросит переустановку * многоугольного окна отсечения: * * ----Vertexs in clip window= XX ? * При вводе числа > 0 будут запрашиваться координаты вершин. * При вводе числа = 0 программа затребует ввод координат * прямоугольного окна. * При вводе числа < 0 программа закончится. */ #include #include "V_PLCLIP.C" /*--------------------------------------------------- DrawPoly * Чертит контур многоугольника */ void DrawPoly (col, n, x, y) int col, n; float *x, *y; { int ii, jj; setcolor (col); for (ii=0; ii if ((jj= ii+1) >= n) jj= 0; line (x[ii], y[ii], x[jj], y[jj]); } } /* DrawPoly */ /*---------------------------------------------------- CLR_STR * Зачищает строку выводом в нее пробелов */ void CLR_STR (void) { printf (" \r"); } /*------------------------------------------------ PLCLIP_MAIN */ void main (void) { int ii, jj, fon; /* Индекс фона */ float Wxn,Wyn, /* Прямоугольный отсекатель */ Wxk,Wyk; int N_wind= 0; /* Вводимый отсекатель */ float X_wind[100], Y_wind[100]; float X_norm[100], Y_norm[100]; int wnum; /* Запрошенный отсекатель */ float *wx,*wy,*wnx,*wny; int N_poly= 0; /* Отсекаемый многугольник */ float X_poly[100], Y_poly[100]; int N_clip= 0; /* Отсеченный многугольник */ float X_clip[100], Y_clip[100]; int entry= 0; /* 0/1 - нет/был вывод по умолчанию */ int gdriver= DETECT, gmode; initgraph (&gdriver, &gmode, ""); fon= 0; /* Цвет фона */ setbkcolor(fon); /* Очистка экрана */ cleardevice(); /*--------------- Установить окно отсечения ----------------*/ new_window: gotoxy (1,1); if (!entry) { N_wind= 8; wx= X_wind; wy= Y_wind; *wx++= 150; *wx++= 100; *wx++= 100; *wx++= 150; *wy++= 100; *wy++= 150; *wy++= 250; *wy++= 300; *wx++= 250; *wx++= 300; *wx++= 300; *wx++= 250; *wy++= 300; *wy++= 250; *wy++= 150; *wy++= 100; goto wr_window; } if (!N_poly) goto set_rect; /*---------- Задание многоугольного окна отсечения ---------*/ set_window: CLR_STR (); printf ("----Vertexs in clip window= %d ? ", N_wind); scanf ("%d", &N_wind); if (N_wind < 0) goto all; if (!N_wind) goto set_rect; for (ii=0; ii CLR_STR (); printf ("X_wind[%d], Y_wind[%d] ? ", ii, ii); scanf ("%f%f", &X_wind[ii], &Y_wind[ii]); } wr_window: jj= V_SetPclip (N_wind, X_wind, Y_wind, X_norm, Y_norm); if (jj) { printf ("Error=%d in polyline window\n", jj); goto set_window; } else goto ou_win; /*---------- Задание прямоугольного окна отсечения ---------*/ set_rect: V_GetRclip (&Wxn, &Wyn, &Wxk, &Wyk); get_rect: CLR_STR (); printf ("Rect window: (Xn=%f Yn=%f Xk=%f Yk=%f) ? ", Wxn, Wyn, Wxk, Wyk); scanf ("%f%f%f%f", &Wxn, &Wyn, &Wxk, &Wyk); wr_rect: jj= V_SetRclip (Wxn, Wyn, Wxk, Wyk); if (jj) { printf ("Error=%d in rectangle window\n", jj); goto get_rect; } /*--------------- Прорисовка окна отсечения ----------------*/ ou_win: wnum= V_GetPclip (&wx, &wy, &wnx, &wny); DrawPoly (LIGHTRED, wnum, wx, wy); /*------- Ввод координат отсекаемого многоугольника --------*/ set_poly: gotoxy (1,1); if (!entry) { /* При первом входе отрисовка по умолчанию */ N_poly= 3; X_poly[0]= 10; X_poly[1]= 90; X_poly[2]= 170; Y_poly[0]= 160; Y_poly[1]= 220; Y_poly[2]= 160; } else { CLR_STR (); printf ("--- Vertexs in polyline= %d ? ",N_poly); scanf ("%d", &N_poly); if (N_poly <= 0) goto new_window; for (ii=0; ii printf (" \r"); printf ("X_poly[%d], Y_poly[%d] ? ", ii, ii); scanf ("%f%f", &X_poly[ii], &Y_poly[ii]); } } ++entry; /*---------- Прорисовка отсекателя и отсекаемого -----------*/ wnum= V_GetPclip (&wx, &wy, &wnx, &wny); DrawPoly (LIGHTRED, wnum, wx, wy); DrawPoly (LIGHTGREEN, N_poly, X_poly, Y_poly); /*----------------------- Отсечение ------------------------*/ N_clip= V_Plclip(N_poly, X_poly, Y_poly, X_clip, Y_clip); /*----------------- Прорисовка отсеченного -----------------*/ DrawPoly (YELLOW, N_clip, X_clip, Y_clip); goto set_poly; all: closegraph(); } /* PLCLIP_MAIN */  8  Комментарии к статье  8 8  Обсудить в чате