home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Current Shareware 1994 January
/
SHAR194.ISO
/
graphuti
/
polyops.zip
/
POLYOPS.C
< prev
next >
Wrap
Text File
|
1991-03-31
|
18KB
|
665 lines
/* Demonstration of 'polycalc.c', a partial implementation of the program
"An algorithm for computing the union,intersection ... of two polygons",
by A. Margalit and G. D. Knott, Comput. & Graphics, 13, 2, 167-183, 1989.
Only the case of simple, regular curves is handled.
It is assumed that the polygons lie in the region [0,1]x[0,1]; input data
should be normalized to meet this condition.
The demonstration program consists of four modules:
POLYOPS.C - set up menu and execute choices
POLY_IN.C - accept input from file, screen, or keyboard
POLY_OUT.C - send program output to screen or disk
POLYCALC.C - the Margarit-Knott algorithm plus supporting routines.
The input/output routines use several features of Turbo C, but the the
algorithm itself should be acceptable to any ANSI C compiler.
Programmed by:
B. J. Ball, 3304 Glen Rose Drive, Austin, Texas 78731 (CompuServe 71141,2321)
Requires an IBM compatible computer with 256K EGA or VGA graphics hardware.
*/
#include <stdio.h>
#include <graphics.h>
#include <ctype.h>
#include <stdlib.h>
#define MAXPTS 100 /* maximum size of ANY polygon used, not just input */
#define MAXX 640 /* greater than any permissible x-coordinate */
#define MAXCHOICE 12 /* menu choices */
#define ESC 27
#define UP -72
#define DN -80
#define LEFT -75
#define RIGHT -77
typedef struct {double x; double y;} point;
typedef struct {point first; point second;} segment;
typedef struct {int nverts; double x[MAXPTS]; double y[MAXPTS];} polygon;
typedef struct {point v; int class; int next;} ventry; /* for vertex rings */
typedef struct {point p1; point p2; int del;} fentry; /* for frags list */
/* function prototypes */
void
copy_data(void),
disk_output(void),
draw_menu(void),
file_input(void),
graphics_input(void),
graphics_output(void),
gwindow(int,int,int,int,char **),
high(int),
keyboard_input(void),
norm(int),
operation(void),
putprompt(void),
save_polys(void),
text_output(void),
view_polys(void);
int
getdouble(int,char *),
getkey(void),
input(int x1, int y1, char *t);
extern void
clearline(int,int),
gprintf(int, int, int, char *,...),
graf_out(void),
initialize(void);
setpage(int);
extern int
prompt(int, int, int, char *),
save_data(char *),
save_output(char *),
simple(polygon);
extern int
polys,numcomps,mode,border,x0,y0;
extern int
xc,yc,yb,xx,yy,sxmax,symax,oper;
extern fentry EF[MAXPTS]; /* edge fragment list */
extern int EFsize; /* current number of edge fragments */
extern int skip[]; /* used in building polygons */
extern char fname[], *name[]; /* filename, name of current operation */
/* globals */
int border=14, bgrnd=7, normcolr=0, highcolr=4; /* menu color values */
int current=0; /* currently highlighted item */
int mn = 0; /* current submenu */
int polys = 0; /* flag indicating that polygons are loaded */
char s[80]; /* for user input */
double vd[60]; /* for user input */
char *item[12]; /* selectable entries */
char *msg[] = {
"Enter Polygons"," from",""," Screen"," Keyboard",
" File",
""," Operation","","Intersection"," Union", " A - B",
" B - A","------------","View Polys","Write Polys",
" Output"," to","","Graphics Screen","Text Screen",
"Disk File"};
/* column and row positions for items 0-11 */
int x1[] = {40,40,40,252,252,252,252,252,252,448,448,448};
int y1[] = {87,100,113,87,100,113,126,152,165,87,100,113};
main()
{
int ltr[] = {'s','k','f','i','u','a','b','v','w','g','t','d'};
/* functions corresponding to menu choices */
void (*cmnd[])() = {graphics_input,keyboard_input,file_input,operation,
operation,operation,operation,view_polys,save_polys,
graphics_output,text_output,disk_output};
int num_msgs,longest; /* menu variables */
int min[3] = {0,3,9}; /* minimum item number in submenu */
int max[3] = {2,8,11}; /* maximum item number in submenu */
int curn[] = {0,3,9}; /* most recent position in mn */
int i,c;
initialize();
for (i=0; i<3; i++) item[i] = msg[3+i];
for (i=3; i<7; i++) item[i] = msg[6+i];
item[7] = msg[14]; item[8] = msg[15];
for (i=9; i<12; i++) item[i] = msg[10+i];
draw_menu();
high(current);
while ((c=getkey()) != ESC) /* until Esc key pressed */
{
switch(c)
{
case UP:
norm(current);
if (current == min[mn])
current = max[mn];
else
current--;
high(current);
curn[mn] = current;
break;
case DN:
norm(current);
if (current == max[mn])
current = min[mn];
else
current++;
high(current);
curn[mn] = current;
break;
case LEFT:
if (mn==0)
mn = 2;
else
mn--;
norm(current);
current = curn[mn];
high(current);
break;
case RIGHT:
if (mn==2)
mn = 0;
else
mn++;
norm(current);
current = curn[mn];
high(current);
break;
case 13: /* do function when Enter key pressed */
(*cmnd[current])();
break;
default: /* if letter command, change highlight and do request */
for (i=0; i<MAXCHOICE; i++)
if (ltr[i] == c || ltr[i]-32 == c)
{
norm(current);
current = i;
if (current<3)
mn = 0; /* mn identifies the submenu for i */
else if (current<9)
mn = 1;
else
mn = 2;
high(current);
(*cmnd[current])();
break;
}
}
}
restorecrtmode();
}
/* ------------- set up polygons A,B from screen coordinates --------------- */
void
copy_data(void)
{
int i;
extern polygon A, B;
extern int nv1, nv2;
extern int ax1[], ay1[], ax2[], ay2[];
extern double wx(int), wy(int);
A.nverts = nv1;
for (i=0; i<nv1; i++)
{
A.x[i] = wx(ax1[i]);
A.y[i] = wy(ay1[i]);
}
B.nverts = nv2;
for (i=0; i<nv2; i++)
{
B.x[i] = wx(ax2[i]);
B.y[i] = wy(ay2[i]);
}
}
/* ---------------- Write output polygons to disk ------------------------- */
void
disk_output(void)
{
int r;
if (!numcomps)
{
prompt(xx,yy,15,"No output polygons. Press any key to continue");
getch();
clearline(xx,yy);
norm(current);
if (polys)
current = 3, mn = 1; /* start of operations choices */
else
current = 0, mn = 0; /* start of enter choices */
high(current);
return;
}
r = prompt(xx,yy,14,"Enter filename: ");
input(r,yy,s);
clearline(xx,yy);
if (!save_output(s))
{
prompt(xx,yy,15,"Save failed. Press any key to continue.");
getch();
clearline(xx,yy);
}
norm(current);
current=3;
mn=1;
high(current);
}
/* ------------------------ Set up basic menu screen ---------------------- */
void
draw_menu(void)
{
char *s1[11];
int i,x0,y0,num_msgs,longest;
setlinestyle(SOLID_LINE,0,THICK_WIDTH); /* for borders of windows */
setfillstyle(SOLID_FILL,bgrnd); /* for interiors of windows */
cleardevice();
num_msgs=6;
x0=32; y0=40;
longest=0;
for (i=0; i<num_msgs; i++)
s1[i] = msg[i];
gwindow(x0,y0,num_msgs,longest,s1);
num_msgs=10;
x0=244; y0=40;
longest=3;
for (i=0; i<num_msgs; i++)
s1[i] = msg[i+6];
gwindow(x0,y0,num_msgs,longest,s1);
num_msgs=6;
x0=440; y0=40;
longest=3;
for (i=0; i<num_msgs; i++)
s1[i] = msg[i+16];
gwindow(x0,y0,num_msgs,longest,s1);
putprompt();
setlinestyle(SOLID_LINE,0,NORM_WIDTH); /* for drawing polygons */
setcolor(normcolr);
setfillstyle(EMPTY_FILL,0); /* for general clearing */
}
/* -------------------- Enter polygons from disk file ------------------ */
void
file_input(void)
{
int r;
r = prompt(xx,yy,14,"Enter filename: ");
input(r,yy,s);
clearline(xx,yy);
if (!strlen(s))
return;
polys = load_data(s);
if (!polys)
{
prompt(xx,yy,15,"File not found - Press any key to continue");
getch();
}
else
numcomps = 0; /* disable any previously recorded output */
clearline(xx,yy);
if (polys)
{
view_polys();
norm(current);
current = 3; /* start of operations choices */
mn = 1;
high(current);
}
}
/* ---- extract n double values from string s, put them in array vd[] ---- */
int
getdouble(int n, char *s)
{
int cnt=0;
char *p;
if (n == 0) return cnt;
p = s;
while (cnt < n && *p)
{
while (!isdigit(*p) && *p != '.' && *p != '-') p++;
vd[cnt] = atof(p);
while (isdigit(*p) || *p == '.' || *p == '-') p++;
cnt++;
}
return cnt;
}
/* ----------------- basic input loop feeder --------------------------- */
int
getkey(void)
{
int k;
k = getch();
if (k == 0) k = -getch();
return k;
}
/* ------------- Enter polygons A,B from graphics screen ---------------- */
void
graphics_input(void)
{
int r;
setpage(1);
cleardevice();
setfillstyle(1,7);
setcolor(15);
bar3d(0,yb,sxmax,symax,0,0); /* prompt box */
polys = graf_in();
cleardevice();
setfillstyle(0,0);
setcolor(normcolr);
setpage(0);
if (polys) /* polys is 'loaded' flag */
{
copy_data(); /* graphics input gives integer values */
numcomps = 0; /* in case previous output in memory */
norm(current);
current = 3; /* start of operations choices */
high(current);
mn = 1;
}
}
/* ----------------------- display output polygons ----------------------- */
void
graphics_output(void)
{
if (!numcomps)
{
prompt(xx,yy,15,"No output polygons. Press any key to continue");
getch();
clearline(xx,yy);
norm(current);
if (polys)
current = 3, mn=1 ; /* start of operations choices */
else
current = 0, mn = 0; /* start of enter choices */
high(current);
return;
}
graf_out();
}
/* ---------------------- Set up graphics window ------------------------- */
void
gwindow(x0,y0,num_msgs,longest,s)
int x0,y0,num_msgs,longest;
char *s[];
{
int i,twmax,th,pwidth,pheight,spacing=5,v[10];
int x1,y1[25];
if (getgraphmode() != mode)
return;
setcolor(border);
twmax = textwidth(s[longest]);
th = textheight("H");
pwidth = 3+spacing+twmax+spacing;
/* 3=linewidth; spaces left and right */
pheight = 3+spacing+num_msgs*(th+spacing)+spacing;
/* spacing at top, after each msg, and at bottom */
for (i=0; i<num_msgs; i++)
y1[i] = y0+3+spacing+i*(th+spacing); /* start y-value for s[i] */
v[0] = v[6] = v[8] = x0;
v[1] = v[3] = v[9] = y0;
v[2] = v[4] = x0 + pwidth;
v[5] = v[7] = y0 + pheight;
fillpoly(5,v);
x1 = x0+3+spacing; /* start x-value for all messages */
setcolor(normcolr);
for (i=0; i<num_msgs; i++) /* write messages in normal color */
outtextxy(x1,y1[i],s[i]);
}
/* ----------------------------------------------------------------------- */
void
high(int i)
{
setcolor(highcolr);
outtextxy(x1[i],y1[i],item[i]);
setcolor(normcolr);
}
/* --------------------------------------------------------------------- */
/* get user input (into array t[]), echo on screen at (x1,y1) */
/* eol stops input; backspace ok, no other editing functions implemented */
int
input(int x1, int y1, char *t)
{
int x0=x1,width=8;
char *p, c, s1[2];
p=t;
s1[1] = '\0';
moveto(x1,y1);
setcolor(15);
while ((c=getch()) != '\r')
{
if (c == 27) /* leave if Esc pressed */
{
moveto(xc,yc); /* restore mark first */
setcolor(normcolr); /* restore normal color */
return 0; /* to indicate abnormal exit */
}
if (isprint(c) && x1 < MAXX-width)
{
s1[0] = c;
outtext(s1);
x1 = getx();
*p = c;
p++;
}
if (c == 8 && x1 > x0)
{
x1 -= width;
p--;
moveto(x1,y1);
bar(x1,y1,x1+width,y1+width);
}
}
*p = '\0';
setcolor(normcolr); /* restore normal color */
moveto(xc,yc); /* restore original CP */
return 1; /* normal exit, even if no input */
}
/* --------------------- Enter polygons A,B by hand ---------------------- */
void
keyboard_input(void)
{
restorecrtmode();
clrscr();
polys = kb_in();
if (polys)
{
numcomps = 0; /* disable any previous output record */
current = 3; /* start of operations choices */
mn = 1;
}
setgraphmode(mode);
draw_menu();
high(current);
}
/* ----------------------------------------------------------------------- */
void
norm(int i)
{
setcolor(normcolr);
outtextxy(x1[i],y1[i],item[i]);
}
/* ------------------ carry out selected operation --------------------- */
void
operation(void)
{
int i;
oper = current - 3; /* operations start at #3 in menu */
if (polys==0)
{
prompt(xx,yy,15,"No polygons loaded. Press any key to continue.");
getch();
clearline(xx,yy);
norm(current);
current = 0;
mn = 0;
high(current);
return;
}
if (!simple(A) || !simple(B))
{
prompt(xx,yy,15,
"Only simple polygons can be used. Press any key to continue.");
getch();
clearline(xx,yy);
norm(current);
current = 0;
mn = 0;
high(current);
return;
}
for (i=0; i<EFsize; i++) /* initialize skip[] and EF[] */
{
skip[i]=0;
EF[i].del=0;
}
EFsize = 0;
setcolor(14);
gprintf(xx,yy,14,"Calculating %s ",name[oper]);
numcomps = polygonsoperation();
if (numcomps == 0 )
{
clearline(xx,yy);
gprintf(xx,yy,15,"%s not found. Press any key to continue",name[oper]);
getch();
}
clearline(xx,yy);
norm(current);
if (numcomps>0)
{
current = 9; /* graphics output */
mn = 2;
}
else if (numcomps<=0)
{
current = 7; /* view polygons */
mn = 1;
}
high(current);
}
/* ----------------------------------------------------------------------- */
void
putprompt(void)
{
setcolor(15);
outtextxy(272,16,"POLYOPS");
setcolor(2);
outtextxy(96,322,"Press initial letter of desired selection, or");
outtextxy(96,336,"Use arrow keys to move highlight, then press Enter.");
setcolor(15); outtextxy(560,322,"Esc exits.");
setcolor(normcolr);
}
/* --------------------- Write A and B to disk --------------------------- */
void
save_polys(void)
{
int r;
if (!polys)
{
prompt(xx,yy,15,"No polygons loaded. Press any key to continue.");
getch();
clearline(xx,yy);
norm(current);
current = 0; /* start of 'load' options */
mn = 0;
high(current);
return;
}
r = prompt(xx,yy,14,"Enter filename: ");
input(r,yy,s);
clearline(xx,yy);
if (save_data(s)==0)
{
prompt(xx,yy,15,"Write failed - bad filename? Press any key to continue");
getch();
clearline(xx,yy);
}
norm(current);
current=mn=0;
high(current);
}
/* ----------------- Write output polygons to text screen ---------------- */
void
text_output(void)
{
if (!numcomps)
{
setcolor(15);
prompt(xx,yy,15,"No output polygons. Press any key to continue");
getch();
clearline(xx,yy);
norm(current);
if (polys)
current = 3, mn = 1; /* start of operations choices */
else
current = 0, mn = 0; /* start of enter choices */
high(current);
return;
}
restorecrtmode();
listoutput();
setgraphmode(mode);
draw_menu();
high(current);
}
/* ----------------- display current A and B ----------------------------- */
void
view_polys(void)
{
int i;
if (!polys)
{
prompt(xx,yy,15,"No polygons loaded. Press any key to continue.");
getch();
clearline(xx,yy);
norm(current);
current = 0; /* start of 'load' options */
mn = 0;
high(current);
return;
}
setpage(1);
draw_poly(A,10);
draw_poly(B,12);
setfillstyle(1,7);
setcolor(15);
bar3d(0,yb,sxmax,symax,0,0);
setfillstyle(0,0);
gprintf(24,yb+3,1,"%s",strupr(fname));
i = 48 + textwidth(fname);
gprintf(i,yb+3,1,"A:green B:red");
gprintf(sxmax-185,yb+3,1,"Press any key to return");
getch();
setcolor(normcolr);
cleardevice();
setpage(0);
}