Скриншот (новое окно)Pers.narod.ru. Алгоритмы. Алгоритмы Сазерленда-Ходжмена - отсечение многоугольника окном, объединение многоугольников |
Первая программа реализует обработку отсечения прямоугольным окном, широко применяемую в самых разных графических построениях. Ниже приводятся полный листинг программы и скриншот. Так как писалось это во времена DOS-графики, сегодня можно запустить разве что из-под DOSBox или другого эмулятора (в конце этой главы даны ссылки на эмуляторы).
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <bios.h>
#include <math.h>
#include <graphics.h>
#define X_BAR 200
#define Y_BAR 150
#define SIDES 15
#define MAXPOINT 100
#define BKCOLOR WHITE
typedef struct {
float x,y;
} Point;
Point P[MAXPOINT], //Исходный многоугольник
Q[MAXPOINT], //Копия исходного многоугольника для отрисовки
W[5], //Окно
C[MAXPOINT]; //Рабочий многоугольник для отсечения
int Np,Nq,Nw,x1,y1,x2,y2,nx;
int Round (float x) { return ((x-floor(x)<0.5) ? floor(x) : ceil(x)); }
int Enter (void) { //Вернет 1,если нажата Enter, 0 - если нажата Esc
int c;
while (1) {
fflush (stdin);
c=getch();
if (c==13) return 1;
else if (c==27) return 0;
}
}
void Message (unsigned char *s) {
setfillstyle (SOLID_FILL,BKCOLOR);
bar (x1,y2+2,x2,getmaxy()-2);
setcolor (BLACK);
outtextxy (x1,y2+2,s);
}
void Redraw (void) {
int i;
setfillstyle (SOLID_FILL,WHITE);
bar (x1+1,y1+1,x2-1,y2-1);
setlinestyle (DOTTED_LINE,0,1);
for (i=0; i<Nq-1; i++) line (Round(Q[i].x),Round(Q[i].y),Round(Q[i+1].x),Round(Q[i+1].y));
line (Round(Q[0].x),Round(Q[0].y),Round(Q[Nq-1].x),Round(Q[Nq-1].y));
setlinestyle (SOLID_LINE,0,1);
setcolor (GREEN);
rectangle (W[0].x,W[0].y,W[2].x,W[2].y);
setcolor (BLUE);
for (i=0; i<Np-1; i++) line (Round(P[i].x),Round(P[i].y),Round(P[i+1].x),Round(P[i+1].y));
line (Round(P[0].x),Round(P[0].y),Round(P[Np-1].x),Round(P[Np-1].y));
Message ("Cutting by next side of window"); //Выполнено отсечение стороной окна
Enter();
}
char InitVga (void) { //Инициализация графического режима 640*480 точек
int gdriver = VGA, gmode=2;
initgraph(&gdriver, &gmode, "");
if (graphresult()!=grOk) return 0;
return 1;
}
#define LEFT 0x01
#define RIGHT 0x02
#define TOP 0x08
#define BOTTOM 0x04
void Line (Point P1,Point P2, float *a,float *b) {
*a=(P1.y-P2.y)/(P1.x-P2.x);
*b=P1.y-*a*P1.x;
}
int Between (float x1, float x, float x2) {
if ((Round(x)>=Round(x1)) && (Round(x)<=Round(x2)) ||
(Round(x)<=Round(x1)) && (Round(x)>=Round(x2))) return 1;
return 0;
}
void Re (void) {
int i;
Np=nx;
for (i=0; i<nx; i++) {P[i]=C[i]; }
P[Np].x=P[0].x; P[Np].y=P[0].y; Np++;
Redraw ();
}
void Hodgmen2 (void) {
int i,j;
float a,b,X[MAXPOINT];
nx=0;
for (j=0; j<Np-1; j++) { //верхняя
if (Between (P[j].y,W[0].y,P[j+1].y)) {
if (P[j].y>W[0].y) { C[nx].y=P[j].y; C[nx++].x=P[j].x; }
C[nx].y=W[0].y;
if (Round(P[j].x)==Round(P[j+1].x)) C[nx++].x=P[j].x;
else {
Line (P[j],P[j+1],&a,&b);
C[nx++].x=(W[0].y-b)/a;
}
}
else if ((P[j].y<W[0].y) && (P[j+1].y<W[0].y)) continue;
else {
C[nx].y=P[j].y; C[nx++].x=P[j].x;
}
}
Re ();
nx=0;
for (j=0; j<Np-1; j++) { //правая
if (Between (P[j].x,W[1].x,P[j+1].x)) {
if (P[j].x<W[1].x) { C[nx].y=P[j].y; C[nx++].x=P[j].x; }
C[nx].x=W[1].x;
if (Round(P[j].y)==Round(P[j+1].y)) C[nx++].y=P[j].y;
else {
Line (P[j],P[j+1],&a,&b);
C[nx++].y=a*W[1].x+b;
}
}
else if ((P[j].x>W[1].x) && (P[j+1].x>W[1].x)) continue;
else {
C[nx].y=P[j].y; C[nx++].x=P[j].x;
}
}
Re ();
nx=0;
for (j=0; j<Np-1; j++) { //нижняя
if (Between (P[j].y,W[2].y,P[j+1].y)) {
if (P[j].y<W[2].y) { C[nx].y=P[j].y; C[nx++].x=P[j].x; }
C[nx].y=W[2].y;
if (Round(P[j].x)==Round(P[j+1].x)) C[nx++].x=P[j].x;
else {
Line (P[j],P[j+1],&a,&b);
C[nx++].x=(W[2].y-b)/a;
}
}
else if ((P[j].y>W[2].y) && (P[j+1].y>W[2].y)) continue;
else {
C[nx].y=P[j].y; C[nx++].x=P[j].x;
}
}
Re ();
nx=0;
for (j=0; j<Np-1; j++) { //левая
if (Between (P[j].x,W[3].x,P[j+1].x)) {
if (P[j].x>W[3].x) { C[nx].y=P[j].y; C[nx++].x=P[j].x; }
C[nx].x=W[3].x;
if (Round(P[j].y)==Round(P[j+1].y)) C[nx++].y=P[j].y;
else {
Line (P[j],P[j+1],&a,&b);
C[nx++].y=a*W[3].x+b;
}
}
else if ((P[j].x<W[3].x) && (P[j+1].x<W[3].x)) continue;
else {
C[nx].y=P[j].y; C[nx++].x=P[j].x;
}
}
Re ();
}
int main (void) {
int i,dx,dy;
unsigned char *s=" "
" ";
if (!InitVga()) {
clrscr();
printf ("\n Can't open VGA graphics mode!");
//Не могу инициализировать графику VGA
return 1;
}
do {
x1=10; x2=getmaxx()-10;
y1=4+textheight("W"); y2=getmaxy()-4-textheight("W");
setfillstyle (SOLID_FILL,WHITE);
bar (0,0,getmaxx(),getmaxy());
setcolor (RED);
rectangle (x1,y1,x2,y2);
outtextxy (x1,2,"Cutting! Press ENTER to continue");
//Отсечение многоугольника прямоугольным окном (ENTER - продолжить)
W[0].x=(getmaxx()-X_BAR)/2; W[0].y=(getmaxy()-Y_BAR)/2;
W[1].x=(getmaxx()+X_BAR)/2; W[1].y=(getmaxy()-Y_BAR)/2;
W[2].x=(getmaxx()+X_BAR)/2; W[2].y=(getmaxy()+Y_BAR)/2;
W[3].x=(getmaxx()-X_BAR)/2; W[3].y=(getmaxy()+Y_BAR)/2;
W[4].x=W[0].x; W[4].y=W[0].y;
Nw=5;
randomize();
Np=8+random(SIDES-7); //Число вершин многоугольника
P[0].x=x1+random (W[0].x-x1); //Первая точка - левее и выше окна
dx=2*(x2-P[0].x)/Np; //Шаг по x для остальных точек
for (i=1; i<=Np/2; i++) P[i].x=P[i-1].x+dx; //Идем вперед по оси x
for (i=Np/2+1; i<Np; i++) P[i].x=P[i-1].x-dx; //Возвращаемся назад
P[0].y=y1+random (W[0].y-y1);
dy=(W[0].y+W[2].y)/2;
for (i=1; i<=Np/2; i++) P[i].y=y1+random(dy-y1);
for (i=Np/2+1; i<Np; i++) P[i].y=y2-random (y2-dy);
P[Np].x=P[0].x; P[Np].y=P[0].y; Np++;
Nq=Np;
for (i=0; i<Nq; i++) { Q[i].x=P[i].x; Q[i].y=P[i].y; }
setcolor (BLUE);
for (i=0; i<Np-1; i++) line (P[i].x,P[i].y,P[i+1].x,P[i+1].y);
line (P[0].x,P[0].y,P[Np-1].x,P[Np-1].y);
setcolor (GREEN);
rectangle (W[0].x,W[0].y,W[2].x,W[2].y);
sprintf (s,"Window coordinates: from (%5.0f,%5.0f) to (%5.0f,%5.0f)",W[0].x,W[0].y,W[2].x,W[2].y);
//Координанты окна: от (%5.0f,%5.0f) до (%5.0f,%5.0f)
Message (s);
Enter();
Hodgmen2();
} while (Enter());
closegraph();
return 0;
}
Многоугольники генерируются повторно, достаточно нажимать ENTER.
Скриншот (новое окно)
Архив ZIP с файлами .CPP и .EXE (43 Кб)
Вторая распространенная задача обработки графики - объединение двух многоугольников. Данные для этой программы должны храниться в текущей папке в файле с именем bars.dat, например, таком:
5 50 250 250 50 490 230 460 280 250 410 7 100 100 400 100 420 120 400 400 100 400 80 350 75 300
Формат файла описан в листинге. Требования к программе = те же, что и к первой (DOS-графика).
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <bios.h>
#include <math.h>
#include <values.h>
#include <graphics.h>
#define SIDES 100
#define BKCOLOR WHITE
typedef struct {
float x,y;
} Point;
int x1,x2,y1,y2,n1,n2,n,nc;
Point P[SIDES],W[SIDES],S[SIDES],C[SIDES];
void Read (FILE *f) {
int i;
fscanf (f,"%d",&n1);
for (i=0; i<n1; i++) {
fscanf (f,"%f",&P[i].x);
fscanf (f,"%f",&P[i].y);
}
fscanf (f,"%d",&n2);
for (i=0; i<n2; i++) {
fscanf (f,"%f",&W[i].x);
fscanf (f,"%f",&W[i].y);
}
}
char InitVga (void) { //Инициализация графического режима 640*480 точек
int gdriver = VGA, gmode=2;
initgraph(&gdriver, &gmode, "");
if (graphresult()!=grOk) return 0;
return 1;
}
int Enter (void) { //Вернет 1,если нажата Enter, 0 - если нажата Esc
int c;
while (1) {
fflush (stdin);
c=getch();
if (c==13) return 1;
else if (c==27) return 0;
}
}
void Message (unsigned char *s) {
setfillstyle (SOLID_FILL,BKCOLOR);
bar (x1,y2+2,x2,getmaxy()-2);
setcolor (BLACK);
outtextxy (x1,y2+2,s);
}
int Round (float x) { return ((x-floor(x)<0.5) ? floor(x) : ceil(x)); }
int Between (float x1, float x, float x2) {
if ((Round(x)>=Round(x1)) && (Round(x)<=Round(x2)) ||
(Round(x)<=Round(x1)) && (Round(x)>=Round(x2))) return 1;
return 0;
}
int Cross (Point P1, Point P2, Point W1, Point W2) {
//Факт пересечения прямых, проходящих через точки (P1,P2) и (W1,W2)
float r1,r2;
if (P1.x==P2.x) {
if (Between (W1.x,P1.x,W2.x)) return 1;
return 0;
}
if (P1.y==P2.y) {
if (Between (W1.y,P1.y,W2.y)) return 1;
return 0;
}
r1=(W1.x-P1.x)/(P2.x-P1.x)-(W1.y-P1.y)/(P2.y-P1.y);
r2=(W2.x-P1.x)/(P2.x-P1.x)-(W2.y-P1.y)/(P2.y-P1.y);
if ((r1<0) && (r2>0) || (r1>0) && (r2<0)) return 1;
else return 0;
}
Point T;
int CrossPoint (Point P1, Point P2, Point W1, Point W2) {
//Координаты точки пересечения отрезков (P1,P2) и (W1,W2)
//записываются во внешнюю точку T. Возвращает 1, если отрезки пересекаются
float a1,b1,a2,b2;
if (P1.x==P2.x) {
a2=(W1.y-W2.y)/(W1.x-W2.x);
b2=W1.y-a2*W1.x;
T.x=P1.x;
T.y=a2*P1.x+b2;
if (Between (W1.x,T.x,W2.x) && Between (W1.y,T.y,W2.y)) return 1;
return 0;
}
if (W1.x==W2.x) {
a1=(P1.y-P2.y)/(P1.x-P2.x);
b1=P1.y-a1*P1.x;
T.x=W1.x;
T.y=a1*W1.x+b1;
if (Between (P1.x,T.x,P2.x) && Between (P1.y,T.y,P2.y)) return 1;
return 0;
}
a1=(P1.y-P2.y)/(P1.x-P2.x);
b1=P1.y-a1*P1.x;
a2=(W1.y-W2.y)/(W1.x-W2.x);
b2=W1.y-a2*W1.x;
T.x=(b2-b1)/(a1-a2);
T.y=a1*T.x+b1;
if (Between (P1.x,T.x,P2.x) && Between (P1.y,T.y,P2.y) &&
Between (W1.x,T.x,W2.x) && Between (W1.y,T.y,W2.y)) return 1;
return 0;
}
void Draw(void) {
int i;
setcolor (BLUE);
for (i=0; i<n1-1; i++) line (Round(P[i].x),Round(P[i].y),Round(P[i+1].x),Round(P[i+1].y));
line (Round(P[0].x),Round(P[0].y),Round(P[n1-1].x),Round(P[n1-1].y));
setcolor (RED);
for (i=0; i<n2-1; i++) line (Round(W[i].x),Round(W[i].y),Round(W[i+1].x),Round(W[i+1].y));
line (Round(W[0].x),Round(W[0].y),Round(W[n2-1].x),Round(W[n2-1].y));
}
float Rast (Point P,Point W) {
return (sqrt((P.x-W.x)*(P.x-W.x)+(P.y-W.y)*(P.y-W.y)));
}
int Check (void) {
int i,j;
for (i=0; i<n-1; i++) {
for (j=i+1; j<n; j++) {
if (Round(S[i].x)==Round(S[j].x) && Round(S[i].y)==Round(S[j].y)) {
n--; return 1;
}
}
}
return 0;
}
void Objed(void) {
//Объединение P из n1 вершин и W из n2 вершин в многоугольник S из n вершин
int i=0,j=0,Nj[SIDES],nmin,k,kmin;
Point P1,P2,W1,W2;
float r,rmin;
i=0;
n=0;
NEXT_I:
S[n].x=P[i].x; S[n].y=P[i].y; n++;
if (Check()) return;
nc=0;
if (i==n1-1) { P2.x=P[0].x; P2.y=P[0].y; }
else { P2.x=P[i+1].x; P2.y=P[i+1].y; }
P1.x=P[i].x; P1.y=P[i].y;
for (j=0; j<n2; j++) {
if (j==n2-1) { W2.x=W[0].x; W2.y=W[0].y; }
else { W2.x=W[j+1].x; W2.y=W[j+1].y; }
W1.x=W[j].x; W1.y=W[j].y;
if (Cross(P1,P2,W1,W2)) {
if (CrossPoint(P1,P2,W1,W2)) {
C[nc].x=T.x; C[nc].y=T.y;
Nj[nc]=(j==n2-1 ? 0 : j+1);
nc++;
}
}
}
if (nc>0) {
//В массиве C - все координаты точек пересечения ребрами W данного ребра P
//а в Nj - номера вершин W, для которых есть эти пересечения
rmin=MAXFLOAT;
for (k=0; k<nc; k++) { //Ищем ближайшее к началу ребра пересечение
r=Rast (P1,C[k]);
if (r<rmin) {
kmin=k; nmin=Nj[k]; rmin=r;
}
}
S[n].x=C[kmin].x; S[n].y=C[kmin].y; n++;
if (Check()) return;
j=nmin;
//Перейти на многоугольник W и идти дальше по контуру
NEXT_J:
S[n].x=W[j].x; S[n].y=W[j].y; n++;
if (Check()) return;
nc=0;
if (j==n2-1) { W2.x=W[0].x; W2.y=W[0].y; }
else { W2.x=W[j+1].x; W2.y=W[j+1].y; }
W1.x=W[j].x; W1.y=W[j].y;
for (i=0; i<n1; i++) {
if (i==n1-1) { P2.x=P[0].x; P2.y=P[0].y; }
else { P2.x=P[i+1].x; P2.y=P[i+1].y; }
P1.x=P[i].x; P1.y=P[i].y;
if (Cross(W1,W2,P1,P2)) {
if (CrossPoint(W1,W2,P1,P2)) {
C[nc].x=T.x; C[nc].y=T.y;
Nj[nc]=(i==n1-1 ? 0 : i+1);
nc++;
}
}
}
if (nc==0) {
j++; if (j==n2) j=0;
goto NEXT_J;
}
else {
rmin=MAXFLOAT;
for (k=0; k<nc; k++) { //Ищем ближайшее к началу ребра пересечение
r=Rast (W1,C[k]);
if (r<rmin) {
kmin=k; nmin=Nj[k]; rmin=r;
}
}
S[n].x=C[kmin].x; S[n].y=C[kmin].y; n++;
if (Check()) return;
i=nmin;
//S[n].x=P[i].x; S[n].y=P[i].y; n++;
goto NEXT_I; //Идем дальше по P
}
}
else { //Нет пересечений - идти дальше по P
i++; if (i==n1) i=0;
goto NEXT_I;
}
}
int main (void) {
int i;
FILE *f;
f=fopen ("bars.dat","rt");
if (f==NULL) {
clrscr();
printf ("\n Не могу открыть файл bars.dat для чтения данных!");
printf ("\n Файл должен содержать данные для 2 многоугольников в виде");
printf ("\n n1 PX1 PY1 ... PXn1 PYn1");
printf ("\n n2 WX1 WY1 ... WXn2 WYn2");
printf ("\n где N1,N2 - число вершин, PXi,PYi,WXi,WYi их X- и Y- координаты");
printf ("\n Вершины P,W упорядочены по часовой стрелке, многоугольники без самопересечений");
printf ("\n Начальная вершина должна принадлежать контуру");
return 1;
}
Read (f); fclose (f);
if (!InitVga()) {
clrscr();
printf ("\n Can't open VGA graphics!");
return 1;
}
x1=10; x2=getmaxx()-10;
y1=4+textheight("Щ"); y2=getmaxy()-4-textheight("Щ");
setfillstyle (SOLID_FILL,WHITE);
bar (0,0,getmaxx(),getmaxy());
setcolor (RED);
rectangle (x1,y1,x2,y2);
Draw ();
Message("Press ENTER to continue");
Enter();
Objed();
setfillstyle (SOLID_FILL,GREEN);
setlinestyle (SOLID_LINE,0,3);
for (i=0; i<n-1; i++) line (Round(S[i].x),Round(S[i].y),Round(S[i+1].x),Round(S[i+1].y));
line (Round(S[0].x),Round(S[0].y),Round(S[n-1].x),Round(S[n-1].y));
Message("OK. Press ESC to exit");
Enter();
closegraph();
return 0;
}
После вывода объединения происходит выход из программы по нажатию клавиши.
Скриншот (новое окно)
Архив ZIP с файлами .CPP и .EXE (43 Кб)
 гостевая; E-mail
|
