В данном приложении приведены процедуры, обеспечивающие
выполнение отсечения по прямоугольному и многоугольному
выпуклому окну и тестовая программа проверки работы процедур
отсечения.
/*=================================================== V_CLIP.C
*
* Подрограммы, связанные с отсечением:
*
* V_SetPclip - установить размеры многоугольного окна
* отсечения
* V_SetRclip - установить размеры прямоугольного окна
* отсечения
* V_GetRclip - опросить размеры прямоугольного окна
* отсечения
* V_CSclip - отсечение по алгоритму Коэна-Сазерленда
* прямоугольное окно, кодирование
* концов отсекаемого отрезка
* V_FCclip - отсечение по алгоритму быстрого отсечения
* Алгоритм Собкова-Поспишила-Янга -
* прямоугольное окно, кодирование
* отсекаемого отрезка
* V_LBclip - отсечение по алгоритму Лианга-Барски
* прямоугольное окно, параметрическое
* представление линий
* V_CBclip - отсечение по алгоритму Кируса-Бека
* окно - выпуклый многоугольник,
* параметрическое представление линий
*/
/* Глобальные скаляры для алгоритмов отсечения по
* прямоугольному окну - Коэна-Сазерленда, Fc-алгоритм,
* Лианга-Барски
*/
static float Wxlef= 0.0, /* Координаты левого нижнего и */
Wybot= 0.0, /* правого верхнего углов окна */
Wxrig= 7.0, /* отсечения */
Wytop= 5.0;
/* Глобальные скаляры для алгоритма Кируса-Бека
* отсечения по многоугольному окну
*/
/* Координаты прямоугольного окна */
static float Wxrect[4]= {0.0, 0.0, 7.0, 7.0 };
static float Wyrect[4]= {0.0, 5.0, 5.0, 0.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;
0.18.1 V_SetPclip - установить многоугольник отсечения
/*------------------------------------------------- V_SetPclip
* Устанавливает многоугольное окно отсечения
* kv - количество вершин в окне
* wx - X-координаты вершин
* wy - Y-координаты вершин
* nx - X-координаты нормалей к ребрам
* ny - Y-координаты нормалей к ребрам
*
* Проверяет окно на выпуклость и невырожденность
*
* Если окно правильное, то
* 1. Обновляет глобалы описания многоугольного окна:
* Windn= kv;
* Windx= wx; Windy= wy; --Координаты вершин окна
* Wnormx= nx; Wnormy= ny; --Координаты перпендикуляров
*
* 2. Вычисляет координаты перепендикуляров к сторонам окна
*
* Возвращает:
* 0 - норма
* 1 - вершин менее трех
* 2 - многоугольник вырожден в отрезок
* 3 - многоугольник невыпуклый
*/
int V_SetPclip (kv, wx, wy, nx, ny)
int kv; float *wx, *wy, *nx, *ny;
{ int ii, jj, sminus, splus, szero, otw;
float r,
vox, voy, /* Координаты (i-1)-й вершины */
vix, viy, /* Координаты i-й вершины */
vnx, vny; /* Координаты (i+1)-й вершины */
/* Проверка на выпуклость
* для этого вычисляются векторные произведения
* смежных сторон и определяется знак
* если все знаки == 0 то многоугольник вырожден
* если все знаки >= 0 то многоугольник выпуклый
* если все знаки <= 0 то многоугольник невыпуклый
*/
otw= 0;
if (--kv < 2) {++otw; goto all; }
sminus= 0;
splus= 0;
szero= 0;
vox= wx[kv]; voy= wy[kv];
vix= *wx; viy= *wy;
ii= 0;
do {
if (++ii > kv) ii= 0; /* Следующая вершина */
vnx= wx[ii]; vny= wy[ii]; /* Координаты (i+1)-й */
r= (vix-vox)*(vny-viy) - /* Вект произв ребер */
(viy-voy)*(vnx-vix); /* смежных с i-й верш */
if (r < 0) ++sminus; else
if (r > 0) ++splus; else ++szero;
vox= vix; voy= viy; /* Обновлен координат */
vix= vnx; viy= vny;
} while (ii);
if (!splus && !sminus) /* Все векторные равны нулю */
{otw= 2; goto all; } /* Многоугольник вырожден */
if (splus && sminus) /* Знакопеременн. векторные */
{otw= 3; goto all; } /* Многоугольник невыпуклый */
/* Установление глобалов для правильного окна */
Windn= kv+1; /* Количество вершин у окна */
Windx= wx; Windy= wy; /* Координаты вершин окна */
Wnormx= nx; Wnormy= ny; /* Координ. перпендикуляров */
/* Вычисление координат перпендикуляров к сторонам */
vox= *wx; voy= *wy;
ii= 0;
do {
if (++ii > kv) ii= 0;
vix= wx[ii]; viy= wy[ii]; /* Текущая вершина */
vnx= viy-voy; vny= vox-vix; /* Поворот по часовой */
if (splus) { /* Внутр нормали влево */
vnx= -vnx; vny= -vny;
}
*nx++= vnx; *ny++= vny;
vox= vix; voy= viy; /* Обновление координат */
} while (ii);
all:
return (otw);
} /* V_SetPclip */
0.18.2 V_SetRclip - установить прямоугольник отсечения
/*--------------------------------------------------- V_CSclip
* Реализует алгоритм отсечения Коэна-Сазерленда с
* кодированием концов отсекаемого отрезка
*
* int V_CSclip (float *x0, float *y0, float *x1, float *y1)
*
* Отсекает отрезок, заданный значениями координат его
* точек (x0,y0), (x1,y1), по окну отсечения, заданному
* глобальными скалярами Wxlef, Wybot, Wxrig, Wytop
*
* Конечным точкам отрезка приписываются коды,
* характеризующие его положение относительно окна отсечения
* по правилу:
*
* 1001 | 1000 | 1010
* -----|------|-----
* | Окно |
* 0001 | 0000 | 0010
* -----|------|-----
* 0101 | 0100 | 0110
*
* Отрезок целиком видим если оба его конца имеют коды 0000
* Если логическое И кодов концов не равно 0, то отрезок
* целиком вне окна и он просто отбрасывается.
* Если же результат этой операции = 0, то отрезок
* подозрительный. Он может быть и вне и пересекать окно.
* Для подозрительных отрезков определяются координаты их
* пересечений с теми сторонами, с которыми они могли бы
* пересечься в соответствии с кодами концов.
* При этом используется горизонтальность и вертикальность
* сторон окна, что позволяет определить одну из координат
* без вычислений.
* Часть отрезка, оставшаяся за окном отбрасывается.
* Оставшаяся часть отрезка проверяется на возможность его
* принятия или отбрасывания целиком. Если это невозможно,
* то процесс повторяется для другой стороны окна.
* На каждом цикле вычислений конечная точка отрезка,
* выходившая за окно, заменяется на точку, лежащую или на
* стороне окна или его продолжении.
*
* Вспомогательная процедура Code вычисляет код положения
* для конца отрезка.
*
*/
static float CSxn, CSyn; /* Координаты начала отрезка */
static int CScode (void) /* Определяет код точки xn, yn */
{ register int i;
i= 0;
if (CSxn < Wxlef) ++i; else
if (CSxn > Wxrig) i+= 2;
if (CSyn < Wybot) i+= 4; else
if (CSyn > Wytop) i+= 8;
return (i);
} /* CScode */
int V_CSclip (x0, y0, x1, y1)
float *x0, *y0, *x1, *y1;
{
float CSxk, CSyk; /* Координаты конца отрезка */
int cn, ck, /* Коды концов отрезка */
visible, /* 0/1 - не видим/видим*/
ii, s; /* Рабочие переменные */
float dx, dy, /* Приращения координат*/
dxdy,dydx, /* Наклоны отрезка к сторонам */
r; /* Рабочая переменная */
CSxk= *x1; CSyk= *y1;
CSxn= *x1; CSyn= *y1; ck= CScode ();
CSxn= *x0; CSyn= *y0; cn= CScode ();
/* Определение приращений координат и наклонов отрезка
* к осям. Заодно сразу на построение передается отрезок,
* состоящий из единственной точки, попавшей в окно
*/
dx= CSxk - CSxn;
dy= CSyk - CSyn;
if (dx != 0) dydx= dy / dx; else {
if (dy == 0) {
if (cn==0 && ck==0) goto out; else goto all;
}
}
if (dy != 0) dxdy= dx / dy;
/* Основной цикл отсечения */
visible= 0; ii= 4;
do {
if (cn & ck) break; /* Целиком вне окна */
if (cn == 0 && ck == 0) { /* Целиком внутри окна */
++visible; break;
}
if (!cn) { /* Если Pn внутри окна, то */
s= cn; cn= ck; ck= s; /* перестить точки Pn,Pk и */
r=CSxn; CSxn=CSxk; CSxk=r; /* их коды, чтобы Pn */
r=CSyn; CSyn=CSyk; CSyk=r; /* оказалась вне окна */
}
/* Теперь отрезок разделяется. Pn помещается в точку
* пересечения отрезка со стороной окна.
*/
if (cn & 1) { /* Пересечение с левой стороной */
CSyn= CSyn + dydx * (Wxlef-CSxn);
CSxn= Wxlef;
} else if (cn & 2) { /* Пересечение с правой стороной*/
CSyn= CSyn + dydx * (Wxrig-CSxn);
CSxn= Wxrig;
} else if (cn & 4) { /* Пересечение в нижней стороной*/
CSxn= CSxn + dxdy * (Wybot-CSyn);
CSyn= Wybot;
} else if (cn & 8) { /*Пересечение с верхней стороной*/
CSxn= CSxn + dxdy * (Wytop-CSyn);
CSyn= Wytop;
}
cn= CScode (); /* Перевычисление кода точки Pn */
} while (--ii >= 0);
if (visible) {
out: *x0= CSxn; *y0= CSyn;
*x1= CSxk; *y1= CSyk;
}
all:
return (visible);
} /* V_CSclip */
Знаете ли Вы, что только в 1990-х доплеровские измерения радиотелескопами показали скорость Маринова для CMB (космического микроволнового излучения), которую он открыл в 1974. Естественно, о Маринове никто не хотел вспоминать. Подробнее читайте в FAQ по эфирной физике.
