home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 3 / RISC_DISC_3.iso / resources / etexts / gems / gemsv / ch7_5 / tri.c < prev   
Encoding:
C/C++ Source or Header  |  1995-04-04  |  3.1 KB  |  144 lines
  1. #include "basic.h"
  2. #include <sys/time.h>
  3.  
  4.  
  5. static int initialise(nseg)
  6.      int nseg;
  7. {
  8.   register int i;
  9.  
  10.   for (i = 1; i <= nseg; i++)
  11.     seg[i].is_inserted = FALSE;
  12.   generate_random_ordering(nseg);
  13.   
  14.   return 0;
  15. }
  16.  
  17. #ifdef STANDALONE
  18.  
  19. int main(argc, argv)
  20.      int argc;
  21.      char *argv[];
  22. {
  23.   int n, nmonpoly;
  24.   FILE *infile;
  25.   int op[SEGSIZE][3], i;
  26.  
  27.   if (argc < 2)
  28.     {
  29.       fprintf(stderr, "usage: triangulate <filename>\n");
  30.       exit(1);
  31.     }
  32.   else
  33.     if ((infile = fopen(argv[1], "r")) == NULL)
  34.       {
  35.     perror(argv[1]);
  36.     exit(1);
  37.       }
  38.   
  39. #ifdef CLOCK
  40.   clock();
  41. #endif
  42.   
  43.   n = read_segments(infile);
  44.   for (i = 0; i < 1; i++)
  45.     {
  46.       initialise(n);
  47.       construct_trapezoids(n, seg);
  48.       nmonpoly = monotonate_trapezoids(n);
  49.       triangulate_monotone_polygons(nmonpoly, op);
  50.     }
  51.   
  52. #ifdef CLOCK
  53.   printf("CPU time used: %ld microseconds\n", clock());
  54. #endif
  55.   
  56.   return 0;
  57. }
  58.  
  59. #else  /* Not standalone. Use this as an interface routine */
  60.  
  61. /* The points constituting the polygon are specified in anticlockwise
  62.  * order. If there are n points in the polygon, i/p would be the
  63.  * points p0, p1....p(n) (where p0 and pn are the same point). The
  64.  * output is contained in the array "triangles".
  65.  * Every triangle is output in anticlockwise order and the 3
  66.  * integers are the indices of the points. Thus, the triangle (i, j, k)
  67.  * refers to the triangle formed by the points (pi, pj, pk). Before
  68.  * using this routine, please check-out that you do not conflict with
  69.  * the global variables  defined in basic.h.
  70.  *
  71.  * n:         number of points in polygon (p0 = pn)
  72.  * vertices:  the vertices p0, p1..., p(n) of the polygon
  73.  * triangles: output array containing the triangles 
  74.  */
  75.  
  76. int triangulate_polygon(n, vertices, triangles)
  77.      int n;
  78.      double vertices[][2];
  79.      int triangles[][3];
  80. {
  81.   register int i;
  82.   int nmonpoly;
  83.  
  84.   memset((void *)seg, 0, sizeof(seg));
  85.   for (i = 1; i <= n; i++)
  86.     {
  87.       seg[i].is_inserted = FALSE;
  88.  
  89.       seg[i].v0.x = vertices[i][0]; /* x-cood */
  90.       seg[i].v0.y = vertices[i][1]; /* y-cood */
  91.       if (i == 1)
  92.     {
  93.       seg[n].v1.x = seg[i].v0.x;
  94.       seg[n].v1.y = seg[i].v0.y;
  95.     }
  96.       else
  97.     {
  98.       seg[i - 1].v1.x = seg[i].v0.x;
  99.       seg[i - 1].v1.y = seg[i].v0.y;
  100.     }    
  101.     }
  102.   
  103.   global.nseg = n;
  104.   initialise(n);
  105.   construct_trapezoids(n, seg);
  106.   nmonpoly = monotonate_trapezoids(n);
  107.   triangulate_monotone_polygons(nmonpoly, triangles);
  108.   
  109.   return 0;
  110. }
  111.  
  112.  
  113. /* This function returns TRUE or FALSE depending upon whether the 
  114.  * vertex is inside the polygon or not. The polygon must already have
  115.  * been triangulated before this routine is called.
  116.  * This routine will always detect all the points belonging to the 
  117.  * set (polygon-area - polygon-boundary). The return value for points 
  118.  * on the boundary is not consistent!!!
  119.  */
  120.  
  121. int is_point_inside_polygon(vertex)
  122.      double vertex[2];
  123. {
  124.   point_t v;
  125.   int trnum, rseg;
  126.   trap_t *t;
  127.  
  128.   v.x = vertex[0];
  129.   v.y = vertex[1];
  130.   
  131.   trnum = locate_endpoint(v, v, 1);
  132.   t = &tr[trnum];
  133.   
  134.   if (t->state == ST_INVALID)
  135.     return FALSE;
  136.   
  137.   if ((t->lseg <= 0) || (t->rseg <= 0))
  138.     return FALSE;
  139.   rseg = t->rseg;
  140.   return _greater_than_equal_to(&seg[rseg].v1, &seg[rseg].v0);
  141. }
  142.  
  143. #endif
  144.