В данном приложении содержатся процедуры V_Plclip,
реализующие простой алгоритм отсечения произвольного
многоугольника по выпуклому многоугольному окну отсечения и
тестовая программа проверки их работы.
Процедуры реализуют алгоритм, который, как и алгоритм
Сазерленда-Ходгмана, последовательно отсекает весь
многоугольник по каждому из ребер окна отсечения.
0.19.1 V_Plclip - простой алгоритм отсечения многоугольника
/*=================================================== V_PLCLIP
* Файл V_PLCLIP.C - процедуры простого алгоритма отсечния
* многоугольника
* Последняя редакция:
* 25.12.93 17:25
*/
#include <graphics.h>
#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<Windn; ++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 */
/*=================================================== 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 <graphics.h>
#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<n; ++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;
Знаете ли Вы, что в 1974 - 1980 годах профессор Стефан Маринов из г. Грац, Австрия, проделал серию экспериментов, в которых показал, что Земля движется по отношению к некоторой космической системе отсчета со скоростью 360±30 км/с, которая явно имеет какой-то абсолютный статус. Естественно, ему не давали нигде выступать и он вынужден был начать выпуск своего научного журнала "Deutsche Physik", где объяснял открытое им явление. Подробнее читайте в FAQ по эфирной физике.
