home *** CD-ROM | disk | FTP | other *** search
/ Current Shareware 1994 January / SHAR194.ISO / graphuti / polyops.zip / POLYOPS.C < prev    next >
Text File  |  1991-03-31  |  18KB  |  665 lines
  1.  
  2. /* Demonstration of 'polycalc.c', a partial implementation of the program
  3.    "An algorithm for computing the union,intersection ... of two polygons",
  4.    by A. Margalit and G. D. Knott, Comput. & Graphics, 13, 2, 167-183, 1989.
  5.  
  6.    Only the case of simple, regular curves is handled.
  7.    It is assumed that the polygons lie in the region [0,1]x[0,1]; input data
  8.    should be normalized to meet this condition.
  9.  
  10.    The demonstration program consists of four modules:
  11.       POLYOPS.C - set up menu and execute choices
  12.       POLY_IN.C  - accept input from file, screen, or keyboard
  13.       POLY_OUT.C - send program output to screen or disk
  14.       POLYCALC.C - the Margarit-Knott algorithm plus supporting routines.
  15.    The input/output routines use several features of Turbo C, but the the
  16.    algorithm itself should be acceptable to any ANSI C compiler.
  17.  
  18.    Programmed by:
  19.    B. J. Ball, 3304 Glen Rose Drive, Austin, Texas 78731 (CompuServe 71141,2321)
  20.    Requires an IBM compatible computer with 256K EGA or VGA graphics hardware.
  21. */
  22.  
  23. #include <stdio.h>
  24. #include <graphics.h>
  25. #include <ctype.h>
  26. #include <stdlib.h>
  27.  
  28. #define MAXPTS   100    /* maximum size of ANY polygon used, not just input */
  29. #define MAXX     640    /* greater than any permissible x-coordinate */
  30. #define MAXCHOICE 12    /* menu choices */
  31.  
  32. #define ESC       27
  33. #define UP       -72
  34. #define DN       -80
  35. #define LEFT     -75
  36. #define RIGHT    -77
  37.  
  38. typedef struct {double x; double y;} point;
  39. typedef struct {point first; point second;} segment;
  40. typedef struct {int nverts; double x[MAXPTS]; double y[MAXPTS];} polygon;
  41. typedef struct {point v; int class; int next;} ventry; /* for vertex rings */
  42. typedef struct {point p1; point p2; int del;} fentry;  /* for frags list */
  43.  
  44.  
  45. /* function prototypes */
  46. void
  47. copy_data(void),
  48. disk_output(void),
  49. draw_menu(void),
  50. file_input(void),
  51. graphics_input(void),
  52. graphics_output(void),
  53. gwindow(int,int,int,int,char **),
  54. high(int),
  55. keyboard_input(void),
  56. norm(int),
  57. operation(void),
  58. putprompt(void),
  59. save_polys(void),
  60. text_output(void),
  61. view_polys(void);
  62.  
  63. int
  64. getdouble(int,char *),
  65. getkey(void),
  66. input(int x1, int y1, char *t);
  67.  
  68. extern void
  69.   clearline(int,int),
  70.   gprintf(int, int, int, char *,...),
  71.   graf_out(void),
  72.   initialize(void);
  73.   setpage(int);
  74. extern int
  75.   prompt(int, int, int, char *),
  76.   save_data(char *),
  77.   save_output(char *),
  78.   simple(polygon);
  79.  
  80. extern int
  81.   polys,numcomps,mode,border,x0,y0;
  82. extern int
  83.  xc,yc,yb,xx,yy,sxmax,symax,oper;
  84. extern fentry EF[MAXPTS];          /* edge fragment list */
  85. extern int EFsize;                 /* current number of edge fragments */
  86. extern int skip[];                 /* used in building polygons */
  87. extern char fname[], *name[];      /* filename, name of current operation */
  88.  
  89. /* globals */
  90.  
  91. int border=14, bgrnd=7, normcolr=0, highcolr=4;   /* menu color values */
  92. int current=0;                /* currently highlighted item */
  93. int mn = 0;                   /* current submenu */
  94. int polys = 0;                /* flag indicating that polygons are loaded */
  95. char s[80];                   /* for user input */
  96. double vd[60];                /* for user input */
  97. char *item[12];               /* selectable entries */
  98. char *msg[] = {
  99.                 "Enter Polygons","    from","","   Screen","   Keyboard",
  100.                 "   File",
  101.                 ""," Operation","","Intersection","  Union", "  A - B",
  102.                 "  B - A","------------","View Polys","Write Polys",
  103.                 "   Output","    to","","Graphics Screen","Text Screen",
  104.                 "Disk File"};
  105. /* column and row positions for items 0-11 */
  106. int x1[] = {40,40,40,252,252,252,252,252,252,448,448,448};
  107. int y1[] = {87,100,113,87,100,113,126,152,165,87,100,113};
  108.  
  109. main()
  110. {
  111.    int ltr[] = {'s','k','f','i','u','a','b','v','w','g','t','d'};
  112.    /* functions corresponding to menu choices */
  113.    void (*cmnd[])() = {graphics_input,keyboard_input,file_input,operation,
  114.                       operation,operation,operation,view_polys,save_polys,
  115.                       graphics_output,text_output,disk_output};
  116.    int num_msgs,longest;                  /* menu variables */
  117.    int min[3] = {0,3,9};                  /* minimum item number in submenu */
  118.    int max[3] = {2,8,11};                 /* maximum item number in submenu */
  119.    int curn[] = {0,3,9};                  /* most recent position in mn */
  120.    int i,c;
  121.  
  122.    initialize();
  123.  
  124.    for (i=0; i<3; i++) item[i] = msg[3+i];
  125.    for (i=3; i<7; i++) item[i] = msg[6+i];
  126.    item[7] = msg[14]; item[8] = msg[15];
  127.    for (i=9; i<12; i++) item[i] = msg[10+i];
  128.  
  129.    draw_menu();
  130.    high(current);
  131.  
  132.    while ((c=getkey()) != ESC)             /* until Esc key pressed */
  133.      {
  134.       switch(c)
  135.        {
  136.         case UP:
  137.           norm(current);
  138.           if (current == min[mn])
  139.              current = max[mn];
  140.           else
  141.              current--;
  142.           high(current);
  143.           curn[mn] = current;
  144.           break;
  145.         case DN:
  146.           norm(current);
  147.           if (current == max[mn])
  148.              current = min[mn];
  149.           else
  150.              current++;
  151.           high(current);
  152.           curn[mn] = current;
  153.           break;
  154.         case LEFT:
  155.           if (mn==0)
  156.              mn = 2;
  157.           else
  158.              mn--;
  159.           norm(current);
  160.           current = curn[mn];
  161.           high(current);
  162.           break;
  163.         case RIGHT:
  164.           if (mn==2)
  165.              mn = 0;
  166.           else
  167.              mn++;
  168.           norm(current);
  169.           current = curn[mn];
  170.           high(current);
  171.           break;
  172.         case 13:                   /* do function when Enter key pressed */
  173.           (*cmnd[current])();
  174.           break;
  175.         default:      /* if letter command, change highlight and do request */
  176.           for (i=0; i<MAXCHOICE; i++)
  177.             if (ltr[i] == c || ltr[i]-32 == c)
  178.               {
  179.                norm(current);
  180.                current = i;
  181.                if (current<3)
  182.                   mn = 0;   /* mn identifies the submenu for i */
  183.                else if (current<9)
  184.                   mn = 1;
  185.                else
  186.                   mn = 2;
  187.                high(current);
  188.                (*cmnd[current])();
  189.                break;
  190.               }
  191.         }
  192.      }
  193.    restorecrtmode();
  194. }
  195.  
  196.  
  197. /* ------------- set up polygons A,B from screen coordinates --------------- */
  198. void
  199. copy_data(void)
  200. {
  201.    int i;
  202.    extern polygon A, B;
  203.    extern int nv1, nv2;
  204.    extern int ax1[], ay1[], ax2[], ay2[];
  205.    extern double wx(int), wy(int);
  206.  
  207.    A.nverts = nv1;
  208.    for (i=0; i<nv1; i++)
  209.     {
  210.      A.x[i] = wx(ax1[i]);
  211.      A.y[i] = wy(ay1[i]);
  212.     }
  213.  
  214.    B.nverts = nv2;
  215.    for (i=0; i<nv2; i++)
  216.     {
  217.      B.x[i] = wx(ax2[i]);
  218.      B.y[i] = wy(ay2[i]);
  219.     }
  220. }
  221. /* ---------------- Write output polygons to disk ------------------------- */
  222. void
  223. disk_output(void)
  224. {
  225.    int r;
  226.  
  227.    if (!numcomps)
  228.      {
  229.       prompt(xx,yy,15,"No output polygons. Press any key to continue");
  230.       getch();
  231.       clearline(xx,yy);
  232.       norm(current);
  233.       if (polys)
  234.          current = 3, mn = 1;   /* start of operations choices */
  235.       else
  236.          current = 0, mn = 0;   /* start of enter choices */
  237.       high(current);
  238.       return;
  239.      }
  240.    r = prompt(xx,yy,14,"Enter filename: ");
  241.    input(r,yy,s);
  242.    clearline(xx,yy);
  243.    if (!save_output(s))
  244.      {
  245.       prompt(xx,yy,15,"Save failed. Press any key to continue.");
  246.       getch();
  247.       clearline(xx,yy);
  248.      }
  249.    norm(current);
  250.    current=3;
  251.    mn=1;
  252.    high(current);
  253. }
  254. /* ------------------------ Set up basic menu screen ---------------------- */
  255. void
  256. draw_menu(void)
  257. {
  258.    char *s1[11];
  259.    int i,x0,y0,num_msgs,longest;
  260.  
  261.    setlinestyle(SOLID_LINE,0,THICK_WIDTH);   /* for borders of windows */
  262.    setfillstyle(SOLID_FILL,bgrnd);           /* for interiors of windows */
  263.    cleardevice();
  264.    num_msgs=6;
  265.    x0=32; y0=40;
  266.    longest=0;
  267.    for (i=0; i<num_msgs; i++)
  268.       s1[i] = msg[i];
  269.    gwindow(x0,y0,num_msgs,longest,s1);
  270.  
  271.    num_msgs=10;
  272.    x0=244; y0=40;
  273.    longest=3;
  274.    for (i=0; i<num_msgs; i++)
  275.       s1[i] = msg[i+6];
  276.    gwindow(x0,y0,num_msgs,longest,s1);
  277.  
  278.    num_msgs=6;
  279.    x0=440; y0=40;
  280.    longest=3;
  281.    for (i=0; i<num_msgs; i++)
  282.       s1[i] = msg[i+16];
  283.    gwindow(x0,y0,num_msgs,longest,s1);
  284.    putprompt();
  285.    setlinestyle(SOLID_LINE,0,NORM_WIDTH);   /* for drawing polygons */
  286.    setcolor(normcolr);
  287.    setfillstyle(EMPTY_FILL,0);              /* for general clearing */
  288. }
  289. /* -------------------- Enter polygons from disk file ------------------ */
  290. void
  291. file_input(void)
  292. {
  293.    int r;
  294.  
  295.    r = prompt(xx,yy,14,"Enter filename: ");
  296.    input(r,yy,s);
  297.    clearline(xx,yy);
  298.    if (!strlen(s))
  299.       return;
  300.    polys = load_data(s);
  301.    if (!polys)
  302.      {
  303.       prompt(xx,yy,15,"File not found - Press any key to continue");
  304.       getch();
  305.      }
  306.    else
  307.       numcomps = 0;         /* disable any previously recorded output */
  308.    clearline(xx,yy);
  309.    if (polys)
  310.      {
  311.       view_polys();
  312.       norm(current);
  313.       current = 3;           /* start of operations choices */
  314.       mn = 1;
  315.       high(current);
  316.      }
  317. }
  318. /* ---- extract n double values from string s, put them in array vd[] ---- */
  319. int
  320. getdouble(int n, char *s)
  321. {
  322.   int cnt=0;
  323.   char *p;
  324.  
  325.   if (n == 0) return cnt;
  326.  
  327.   p = s;
  328.   while (cnt < n && *p)
  329.     {
  330.      while (!isdigit(*p) && *p != '.' && *p != '-') p++;
  331.      vd[cnt] = atof(p);
  332.      while (isdigit(*p) || *p == '.' || *p == '-') p++;
  333.      cnt++;
  334.     }
  335.   return cnt;
  336. }
  337. /* ----------------- basic input loop feeder --------------------------- */
  338. int 
  339. getkey(void)
  340. {
  341.  int k;
  342.  
  343.  k = getch();
  344.  if (k == 0) k = -getch();
  345.  return k;
  346. }
  347. /* ------------- Enter polygons A,B from graphics screen ---------------- */
  348. void
  349. graphics_input(void)
  350. {
  351.    int r;
  352.  
  353.    setpage(1);
  354.    cleardevice();
  355.    setfillstyle(1,7);
  356.    setcolor(15);
  357.    bar3d(0,yb,sxmax,symax,0,0);     /* prompt box */
  358.    polys = graf_in();
  359.    cleardevice();
  360.    setfillstyle(0,0);
  361.    setcolor(normcolr);
  362.    setpage(0);
  363.    if (polys)                /* polys is 'loaded' flag */
  364.      {
  365.       copy_data();           /* graphics input gives integer values */
  366.       numcomps = 0;          /* in case previous output in memory */
  367.       norm(current);
  368.       current = 3;           /* start of operations choices */
  369.       high(current);
  370.       mn = 1;
  371.      }
  372. }
  373. /* ----------------------- display output polygons ----------------------- */
  374. void
  375. graphics_output(void)
  376. {
  377.    if (!numcomps)
  378.      {
  379.       prompt(xx,yy,15,"No output polygons. Press any key to continue");
  380.       getch();
  381.       clearline(xx,yy);
  382.       norm(current);
  383.       if (polys)
  384.          current = 3, mn=1 ;   /* start of operations choices */
  385.       else
  386.          current = 0, mn = 0;   /* start of enter choices */
  387.       high(current);
  388.       return;
  389.      }
  390.  
  391.    graf_out();
  392. }
  393.  
  394. /* ---------------------- Set up graphics window ------------------------- */
  395. void
  396. gwindow(x0,y0,num_msgs,longest,s)
  397. int x0,y0,num_msgs,longest;
  398. char *s[];
  399. {
  400.    int i,twmax,th,pwidth,pheight,spacing=5,v[10];
  401.    int x1,y1[25];
  402.  
  403.    if (getgraphmode() != mode)
  404.       return;
  405.  
  406.    setcolor(border);
  407.    twmax = textwidth(s[longest]);
  408.    th = textheight("H");
  409.    pwidth = 3+spacing+twmax+spacing;
  410.                  /* 3=linewidth; spaces left and right */
  411.    pheight = 3+spacing+num_msgs*(th+spacing)+spacing;
  412.                  /* spacing at top, after each msg, and at bottom */
  413.    for (i=0; i<num_msgs; i++)
  414.       y1[i] = y0+3+spacing+i*(th+spacing); /* start y-value for s[i] */
  415.    v[0] = v[6] = v[8] = x0;
  416.    v[1] = v[3] = v[9] = y0;
  417.    v[2] = v[4] = x0 + pwidth;
  418.    v[5] = v[7] = y0 + pheight;
  419.    fillpoly(5,v);
  420.    x1 = x0+3+spacing;                   /* start x-value for all messages */
  421.    setcolor(normcolr);
  422.    for (i=0; i<num_msgs; i++)           /* write messages in normal color */
  423.       outtextxy(x1,y1[i],s[i]);
  424. }
  425. /* ----------------------------------------------------------------------- */
  426. void
  427. high(int i)
  428. {
  429.    setcolor(highcolr);
  430.    outtextxy(x1[i],y1[i],item[i]);
  431.    setcolor(normcolr);
  432. }
  433. /* --------------------------------------------------------------------- */
  434. /* get user input (into array t[]), echo on screen at (x1,y1)            */
  435. /* eol stops input; backspace ok, no other editing functions implemented */
  436.  
  437. int
  438. input(int x1, int y1, char *t)
  439. {
  440.  int x0=x1,width=8;
  441.  char *p, c, s1[2];
  442.  
  443.  p=t;
  444.  s1[1] = '\0';
  445.  moveto(x1,y1);
  446.  setcolor(15);
  447.  
  448.  while ((c=getch()) != '\r')
  449.    {
  450.     if (c == 27)            /* leave if Esc pressed */
  451.       {
  452.        moveto(xc,yc);       /* restore mark first */
  453.        setcolor(normcolr);  /* restore normal color */
  454.        return 0;            /* to indicate abnormal exit */
  455.       }
  456.     if (isprint(c) && x1 < MAXX-width)
  457.       {
  458.        s1[0] = c;
  459.        outtext(s1);
  460.        x1 = getx();
  461.        *p = c;
  462.        p++;
  463.       }
  464.     if (c == 8 && x1 > x0)
  465.       {
  466.        x1 -= width;
  467.        p--;
  468.        moveto(x1,y1);
  469.        bar(x1,y1,x1+width,y1+width);
  470.       }
  471.    }
  472.  *p = '\0';
  473.  setcolor(normcolr);                /* restore normal color */
  474.  moveto(xc,yc);                     /* restore original CP */
  475.  return 1;                          /* normal exit, even if no input */
  476. }
  477.  
  478. /* --------------------- Enter polygons A,B by hand ---------------------- */
  479. void
  480. keyboard_input(void)
  481. {
  482.    restorecrtmode();
  483.    clrscr();
  484.    polys = kb_in();
  485.    if (polys)
  486.      {
  487.       numcomps = 0;          /* disable any previous output record */
  488.       current = 3;           /* start of operations choices */
  489.       mn = 1;
  490.      }
  491.    setgraphmode(mode);
  492.    draw_menu();
  493.    high(current);
  494. }
  495. /* ----------------------------------------------------------------------- */
  496. void
  497. norm(int i)
  498. {
  499.    setcolor(normcolr);
  500.    outtextxy(x1[i],y1[i],item[i]);
  501. }
  502. /* ------------------ carry out selected operation --------------------- */
  503. void
  504. operation(void)
  505. {
  506.    int i;
  507.  
  508.    oper = current - 3;           /* operations start at #3 in menu */
  509.  
  510.    if (polys==0)
  511.      {
  512.       prompt(xx,yy,15,"No polygons loaded. Press any key to continue.");
  513.       getch();
  514.       clearline(xx,yy);
  515.       norm(current);
  516.       current = 0;
  517.       mn = 0;
  518.       high(current);
  519.       return;
  520.      }
  521.  
  522.    if (!simple(A) || !simple(B))
  523.      {
  524.       prompt(xx,yy,15,
  525.              "Only simple polygons can be used. Press any key to continue.");
  526.       getch();
  527.       clearline(xx,yy);
  528.       norm(current);
  529.       current = 0;
  530.       mn = 0;
  531.       high(current);
  532.       return;
  533.      }
  534.  
  535.    for (i=0; i<EFsize; i++)        /* initialize skip[] and EF[] */
  536.      {
  537.       skip[i]=0;
  538.       EF[i].del=0;
  539.      }
  540.      EFsize = 0;
  541.    setcolor(14);
  542.    gprintf(xx,yy,14,"Calculating %s ",name[oper]);
  543.    numcomps = polygonsoperation();
  544.    if (numcomps == 0 )
  545.      {
  546.       clearline(xx,yy);
  547.       gprintf(xx,yy,15,"%s not found. Press any key to continue",name[oper]);
  548.       getch();
  549.      }
  550.    clearline(xx,yy);
  551.    norm(current);
  552.    if (numcomps>0)
  553.      {
  554.       current = 9;             /* graphics output */
  555.       mn = 2;
  556.      }
  557.    else if (numcomps<=0)
  558.      {
  559.       current = 7;      /* view polygons */
  560.       mn = 1;
  561.      }
  562.    high(current);
  563. }
  564. /* ----------------------------------------------------------------------- */
  565. void 
  566. putprompt(void)
  567. {
  568.    setcolor(15);
  569.    outtextxy(272,16,"POLYOPS");
  570.    setcolor(2);
  571.    outtextxy(96,322,"Press initial letter of desired selection, or");
  572.    outtextxy(96,336,"Use arrow keys to move highlight, then press Enter.");
  573.    setcolor(15); outtextxy(560,322,"Esc exits.");
  574.    setcolor(normcolr);
  575. }
  576. /* --------------------- Write A and B to disk --------------------------- */
  577. void
  578. save_polys(void)
  579. {
  580.    int r;
  581.  
  582.    if (!polys)
  583.      {
  584.       prompt(xx,yy,15,"No polygons loaded. Press any key to continue.");
  585.       getch();
  586.       clearline(xx,yy);
  587.       norm(current);
  588.       current = 0;        /* start of 'load' options */
  589.       mn = 0;
  590.       high(current);
  591.       return;
  592.      }
  593.    r = prompt(xx,yy,14,"Enter filename: ");
  594.    input(r,yy,s);
  595.    clearline(xx,yy);
  596.    if (save_data(s)==0)
  597.      {
  598.       prompt(xx,yy,15,"Write failed - bad filename?  Press any key to continue");
  599.       getch();
  600.       clearline(xx,yy);
  601.      }
  602.    norm(current);
  603.    current=mn=0;
  604.    high(current);
  605. }
  606. /* ----------------- Write output polygons to text screen ---------------- */
  607. void
  608. text_output(void)
  609. {
  610.    if (!numcomps)
  611.      {
  612.       setcolor(15);
  613.       prompt(xx,yy,15,"No output polygons. Press any key to continue");
  614.       getch();
  615.       clearline(xx,yy);
  616.       norm(current);
  617.       if (polys)
  618.          current = 3, mn = 1;   /* start of operations choices */
  619.       else
  620.          current = 0, mn = 0;   /* start of enter choices */
  621.       high(current);
  622.       return;
  623.      }
  624.    restorecrtmode();
  625.    listoutput();
  626.    setgraphmode(mode);
  627.    draw_menu();
  628.    high(current);
  629. }
  630. /* ----------------- display current A and B ----------------------------- */
  631. void
  632. view_polys(void)
  633. {
  634.    int i;
  635.  
  636.    if (!polys)
  637.      {
  638.       prompt(xx,yy,15,"No polygons loaded. Press any key to continue.");
  639.       getch();
  640.       clearline(xx,yy);
  641.       norm(current);
  642.       current = 0;        /* start of 'load' options */
  643.       mn = 0;
  644.       high(current);
  645.       return;
  646.      }
  647.  
  648.    setpage(1);
  649.    draw_poly(A,10);
  650.    draw_poly(B,12);
  651.    setfillstyle(1,7);
  652.    setcolor(15);
  653.    bar3d(0,yb,sxmax,symax,0,0);
  654.    setfillstyle(0,0);
  655.    gprintf(24,yb+3,1,"%s",strupr(fname));
  656.    i = 48 + textwidth(fname);
  657.    gprintf(i,yb+3,1,"A:green B:red");
  658.    gprintf(sxmax-185,yb+3,1,"Press any key to return");
  659.    getch();
  660.    setcolor(normcolr);
  661.    cleardevice();
  662.    setpage(0);
  663. }
  664.  
  665.