/*This code is described in "Computational Geometry in C" (Second Edition),Chapter 1.  It is not written to be comprehensible without the explanation in that book.Input: 2n integer coordinates for vertices of a simple polygon,       in counterclockwise order.  NB: the code will not work       for points in clockwise order!Output: the diagonals of a triangulation, in PostScript.Compile: gcc -o tri tri.c (or simply: make)Written by Joseph O'Rourke, with contributions by Min Xu.Last modified: October 1997Questions to orourke@cs.smith.edu.--------------------------------------------------------------------This code is Copyright 1998 by Joseph O'Rourke.  It may be freely redistributed in its entirety provided that this copyright notice is not removed.--------------------------------------------------------------------*/#include <stdio.h>#include <math.h>#define	EXIT_FAILURE 1#define	X 0#define	Y 1typedef	enum { FALSE, TRUE } bool;#define	DIM 2               /* Dimension of points */typedef	int tPointi[DIM];   /* Type integer point */typedef	struct tVertexStructure tsVertex;	/* Used only in NEW(). */typedef	tsVertex *tVertex;struct	tVertexStructure {   int		vnum;		/* Index */   tPointi	v;		/* Coordinates */   bool 	ear;		/* TRUE iff an ear */   tVertex 	next,prev;};/* Global variable definitions */tVertex	vertices  = NULL;	/* "Head" of circular list. */int	nvertices = 0;		/* Total number of polygon vertices. */#include "macros.h"	/* NEW, ADD *//*---------------------------------------------------------------------Function prototypes.---------------------------------------------------------------------*/int	AreaPoly2( void );void	Triangulate( void );void	EarInit( void );bool	Diagonal( tVertex a, tVertex b );bool	Diagonalie( tVertex a, tVertex b );bool	InCone( tVertex a, tVertex b );int     Area2( tPointi a, tPointi b, tPointi c );int     AreaSign( tPointi a, tPointi b, tPointi c );bool	Xor( bool x, bool y );bool	Left( tPointi a, tPointi b, tPointi c );bool	LeftOn( tPointi a, tPointi b, tPointi c );bool	Collinear( tPointi a, tPointi b, tPointi c );bool	Between( tPointi a, tPointi b, tPointi c );bool	Intersect( tPointi a, tPointi b, tPointi c, tPointi d );bool	IntersectProp( tPointi a, tPointi b, tPointi c, tPointi d );tVertex	MakeNullVertex( void );void	ReadVertices( void );void	PrintVertices( void );void	PrintDiagonal( tVertex a, tVertex b );void	PrintPoly( void );/*-------------------------------------------------------------------*/main(){   ReadVertices();   PrintVertices();   printf("%%Area of polygon = %g\n", 0.5 * AreaPoly2() );   Triangulate();   printf("showpage\n%%%%EOF\n");}/*---------------------------------------------------------------------Returns twice the signed area of the triangle determined by a,b,c.The area is positive if a,b,c are oriented ccw, negative if cw,and zero if the points are collinear.---------------------------------------------------------------------*/int     Area2( tPointi a, tPointi b, tPointi c ){   return          (b[X] - a[X]) * (c[Y] - a[Y]) -          (c[X] - a[X]) * (b[Y] - a[Y]);}/*---------------------------------------------------------------------Exclusive or: TRUE iff exactly one argument is true.---------------------------------------------------------------------*/bool	Xor( bool x, bool y ){   /* The arguments are negated to ensure that they are 0/1 values. */   /* (Idea due to Michael Baldwin.) */   return   !x ^ !y;}/*---------------------------------------------------------------------Returns true iff ab properly intersects cd: they sharea point interior to both segments.  The properness of theintersection is ensured by using strict leftness.---------------------------------------------------------------------*/bool	IntersectProp( tPointi a, tPointi b, tPointi c, tPointi d ){   /* Eliminate improper cases. */   if (      Collinear(a,b,c) ||      Collinear(a,b,d) ||      Collinear(c,d,a) ||      Collinear(c,d,b)      )      return FALSE;   return         Xor( Left(a,b,c), Left(a,b,d) )      && Xor( Left(c,d,a), Left(c,d,b) );}/*---------------------------------------------------------------------Returns true iff c is strictly to the left of the directedline through a to b.---------------------------------------------------------------------*/bool	Left( tPointi a, tPointi b, tPointi c ){    return  AreaSign( a, b, c ) > 0;}bool	LeftOn( tPointi a, tPointi b, tPointi c ){   return  AreaSign( a, b, c ) >= 0;}bool	Collinear( tPointi a, tPointi b, tPointi c ){   return  AreaSign( a, b, c ) == 0;}/*---------------------------------------------------------------------Returns TRUE iff point c lies on the closed segement ab.First checks that c is collinear with a and b.---------------------------------------------------------------------*/bool	Between( tPointi a, tPointi b, tPointi c ){   tPointi	ba, ca;   if ( ! Collinear( a, b, c ) )      return  FALSE;   /* If ab not vertical, check betweenness on x; else on y. */   if ( a[X] != b[X] )       return ((a[X] <= c[X]) && (c[X] <= b[X])) ||             ((a[X] >= c[X]) && (c[X] >= b[X]));   else      return ((a[Y] <= c[Y]) && (c[Y] <= b[Y])) ||             ((a[Y] >= c[Y]) && (c[Y] >= b[Y]));}/*---------------------------------------------------------------------Returns TRUE iff segments ab and cd intersect, properly or improperly.---------------------------------------------------------------------*/bool	Intersect( tPointi a, tPointi b, tPointi c, tPointi d ){   if      ( IntersectProp( a, b, c, d ) )      return  TRUE;   else if (   Between( a, b, c )            || Between( a, b, d )            || Between( c, d, a )            || Between( c, d, b )           )      return  TRUE;   else    return  FALSE;}/*---------------------------------------------------------------------Returns TRUE iff (a,b) is a proper internal *or* externaldiagonal of P, *ignoring edges incident to a and b*.---------------------------------------------------------------------*/bool   Diagonalie( tVertex a, tVertex b ){   tVertex c, c1;   /* For each edge (c,c1) of P */   c = vertices;   do {      c1 = c->next;      /* Skip edges incident to a or b */      if (    ( c != a ) && ( c1 != a )           && ( c != b ) && ( c1 != b )           && Intersect( a->v, b->v, c->v, c1->v )         )         return FALSE;      c = c->next;   } while ( c != vertices );   return TRUE;}/*---------------------------------------------------------------------This function initializes the data structures, and callsTriangulate2 to clip off the ears one by one.---------------------------------------------------------------------*/void   EarInit( void ){   tVertex v0, v1, v2;   /* three consecutive vertices */   /* Initialize v1->ear for all vertices. */   v1 = vertices;   printf("newpath\n");   do {      v2 = v1->next;      v0 = v1->prev;      v1->ear = Diagonal( v0, v2 );      v1 = v1->next;   } while ( v1 != vertices );   printf("closepath stroke\n\n");}/*---------------------------------------------------------------------Prints out n-3 diagonals (as pairs of integer indices)which form a triangulation of P.---------------------------------------------------------------------*/void   Triangulate( void ){   tVertex v0, v1, v2, v3, v4;	/* five consecutive vertices */   int   n = nvertices;		/* number of vertices; shrinks to 3. */   bool earfound;		/* for debugging and error detection only. */   EarInit();   printf("\nnewpath\n");   /* Each step of outer loop removes one ear. */   while ( n > 3 ) {           /* Inner loop searches for an ear. */      v2 = vertices;      earfound = FALSE;      do {         if (v2->ear) {            earfound = TRUE;            /* Ear found. Fill variables. */            v3 = v2->next; v4 = v3->next;            v1 = v2->prev; v0 = v1->prev;            /* (v1,v3) is a diagonal */            PrintDiagonal( v1, v3 );                        /* Update earity of diagonal endpoints */            v1->ear = Diagonal( v0, v3 );            v3->ear = Diagonal( v1, v4 );                        /* Cut off the ear v2 */            v1->next = v3;            v3->prev = v1;            vertices = v3;	/* In case the head was v2. */            n--;            break;   /* out of inner loop; resume outer loop */         } /* end if ear found */         v2 = v2->next;      } while ( v2 != vertices );      if ( !earfound ) {         printf("%%Error in Triangulate:  No ear found.\n");         PrintPoly();         printf("showpage\n%%%%EOF\n");         exit(EXIT_FAILURE);      }   } /* end outer while loop */   printf("closepath stroke\n\n");}/*---------------------------------------------------------------------Returns TRUE iff the diagonal (a,b) is strictly internal to the polygon in the neighborhood of the a endpoint.  ---------------------------------------------------------------------*/bool   InCone( tVertex a, tVertex b ){   tVertex a0,a1;	/* a0,a,a1 are consecutive vertices. */   a1 = a->next;   a0 = a->prev;   /* If a is a convex vertex ... */   if( LeftOn( a->v, a1->v, a0->v ) )       return    Left( a->v, b->v, a0->v )              && Left( b->v, a->v, a1->v );   /* Else a is reflex: */       return !(    LeftOn( a->v, b->v, a1->v )                 && LeftOn( b->v, a->v, a0->v ) );}/*---------------------------------------------------------------------Returns TRUE iff (a,b) is a proper internal diagonal.---------------------------------------------------------------------*/bool	Diagonal( tVertex a, tVertex b ){   return InCone( a, b ) && InCone( b, a ) && Diagonalie( a, b );}/*---------------------------------------------------------------------ReadVertices: Reads in the vertices, and links them into a circularlist with MakeNullVertex.  There is no need for the # of vertices to bethe first line: the function looks for EOF instead.---------------------------------------------------------------------*/void   ReadVertices( void ){   tVertex	v;   int		x, y;   int		vnum = 0;   while ( scanf ("%d %d", &x, &y ) != EOF )  {      v = MakeNullVertex();      v->v[X] = x;      v->v[Y] = y;      v->vnum = vnum++;   }   nvertices = vnum;   if (nvertices < 3)       printf("%%Error in ReadVertices: nvertices=%d<3\n", nvertices),      exit(EXIT_FAILURE);}/*---------------------------------------------------------------------MakeNullVertex: Makes a vertex.---------------------------------------------------------------------*/tVertex   MakeNullVertex( void ){   tVertex  v;      NEW( v, tsVertex );   ADD( vertices, v );   return v;}/*---------------------------------------------------------------------For debugging; not currently invoked.---------------------------------------------------------------------*/void   PrintPoly( void ){   tVertex  v;   printf("%%Polygon circular list:\n");   v = vertices;   do {                                       printf( "%% vnum=%5d:\tear=%d\n", v->vnum, v->ear );      v = v->next;   } while ( v != vertices );}/*---------------------------------------------------------------------Print: Prints out the vertices.  Uses the vnum indices corresponding to the order in which the vertices were input.Output is in PostScript format.---------------------------------------------------------------------*/void   PrintVertices( void ){   /* Pointers to vertices, edges, faces. */   tVertex  v;   int xmin, ymin, xmax, ymax;   /* Compute bounding box for Encapsulated PostScript. */   v = vertices;   xmin = xmax = v->v[X];   ymin = ymax = v->v[Y];   do {      if      ( v->v[X] > xmax ) xmax = v->v[X];      else if ( v->v[X] < xmin ) xmin = v->v[X];      if      ( v->v[Y] > ymax ) ymax = v->v[Y];      else if ( v->v[Y] < ymin ) ymin = v->v[Y];      v = v->next;   } while ( v != vertices );      /* PostScript header */   printf("%%!PS\n");   printf("%%%%Creator: tri.c (Joseph O'Rourke)\n");   printf("%%%%BoundingBox: %d %d %d %d\n", xmin, ymin, xmax, ymax);   printf("%%%%EndComments\n");   printf(".00 .00 setlinewidth\n");   printf("%d %d translate\n", -xmin+72, -ymin+72 );   /* The +72 shifts the figure one inch from the lower left corner */   /* Output vertex info as a PostScript comment. */   printf("\n%% number of vertices = %d\n", nvertices);   v = vertices;   do {                                       printf( "%% vnum=%5d:\tx=%5d\ty=%5d\n", v->vnum, v->v[X], v->v[Y] );      v = v->next;   } while ( v != vertices );   /* Draw the polygon. */   printf("\n%%Polygon:\n");   printf("newpath\n");   v = vertices;   printf("%d\t%d\tmoveto\n", v->v[X], v->v[Y] );   v = v->next;   do {                                       printf("%d\t%d\tlineto\n", v->v[X], v->v[Y] );      v = v->next;   } while ( v != vertices );   printf("closepath stroke\n");}void	PrintDiagonal( tVertex a, tVertex b ){   printf("%%Diagonal: (%d,%d)\n", a->vnum, b->vnum );   printf("%d\t%d\tmoveto\n", a->v[X], a->v[Y] );   printf("%d\t%d\tlineto\n", b->v[X], b->v[Y] );}int	AreaPoly2( void ){   int     sum = 0;   tVertex p, a;   p = vertices;   /* Fixed. */   a = p->next;    /* Moving. */   do {      sum += Area2( p->v, a->v, a->next->v );      a = a->next;   } while ( a->next != vertices );   return sum;}int     AreaSign( tPointi a, tPointi b, tPointi c ){    double area2;    area2 = ( b[0] - a[0] ) * (double)( c[1] - a[1] ) -            ( c[0] - a[0] ) * (double)( b[1] - a[1] );    /* The area should be an integer. */    if      ( area2 >  0.5 ) return  1;    else if ( area2 < -0.5 ) return -1;    else                     return  0;}