/* polygon.c: Determine the convexity of a polygon // // Written by Michael J. Gourlay // Fall 1996, University of Colorado at Boulder // Algorithms */ #include #include #include /* Top level description: ---------------------- This program reads in polygon vertices represented as (x,y) ordered pair coordinates. The program determined whether the polygon is convex. */ /* ----------------------- */ /* Utility functions */ /* ----------------------- */ /* ABS: absolute value */ #define ABS(x) (((x)<0)?(-(x)):(x)) /* LTZ: less than zero */ #define LTZ(x) (((x)<0)?1:0) /* GTZ: greather than zero */ #define GTZ(x) (((x)>0)?1:0) /* SGN: sign */ #define SGN(x) (LTZ(x)?-1:(GTZ(x)?1:0)) /* PI: ratio of circumference to diameter of a circle */ #define PI 3.141592653589793238462643383279502884 #define TWO_PI 6.283185307179586476925286766559005768 /* FUZZY_ZERO: error tollerence in angle calculations */ #define FUZZY_ZERO 1e-8 /* my_calloc: memory allocation with error checking // Arguments are the same as for standard library function "calloc" // Exit program if memory allocation fails. */ void * my_calloc(size_t nelem, size_t elsize) { char *mem; if((mem=(char *)calloc(nelem, elsize))==NULL) { fprintf(stderr, "my_calloc: out of memory. Tried %i x %i\n", nelem, elsize); abort(); exit(1); } return mem; } /* MY_CALLOC: macro to do memory allocation easily // ne (in): number of elements. Must be integer. // type (in): type token (not a value). Must be a valid variable type. */ #define MY_CALLOC(ne,type) ((type *)my_calloc(ne,sizeof(type))) /* ------------------- */ /* Polygon object */ /* ------------------- */ /* VertexComponentT: primative of a coordinate. */ typedef double VertexComponentT; /* VertexT: vertex type. Ordered pair of x, y coordinate */ typedef struct { VertexComponentT x; VertexComponentT y; } VertexT; /* BooleanT: true or false. Never use TRUE for a test -- only for setting. */ typedef enum {FALSE, TRUE} BooleanT; /* PolygonT: polygon type. */ typedef struct { int num_vertices; /* number of vertices in the polygon */ VertexT *vertices; /* list of vertex coordinates */ } PolygonT; /* polygonInit: set and allocate memory of members of a polygon */ void polygonInit(PolygonT *polyP, const int num_vertices) { polyP->num_vertices = num_vertices; polyP->vertices = MY_CALLOC(polyP->num_vertices, VertexT); } /* polygonDelete: free dynamic memory of members of a polygon // does NOT free memory of instance */ void polygonDelete(PolygonT *polyP) { polyP->num_vertices = 0; if((polyP != NULL) && (polyP->vertices != NULL)) { free(polyP->vertices); } polyP->vertices = NULL; } /* polygonRead: read in the 2D points of a polygon // // fp (in/out): file pointer to read from // polyP (out): polygon // // File format: // // line 1: number of vertices and a manditory 1-word comment // note to grader: If this were some sort of production code, then // the manditory comment would be handled in a better way, but I // wanted to make a note to myself and to you about what each // polygon file contained, within the file. // // lines 2+: vertices as ordered pairs: // x y // // If any read error occurs, return nonzero. // // If there are fewer than 3 vertices then object is not a polygon, // and this routine returns an nonzero value. // // returns 0 if read went without error. */ int polygonRead(FILE *fp, PolygonT *polyP) { char comment[128]; /* comment string */ int num_vertices; /* number of vertices in the polygon */ int vi; /* vertex index, for iterating */ /* Read the number of sides in the polygon. */ if(fscanf(fp, "%i %s\n", &num_vertices, comment) < 1) { fprintf(stderr, "polygonRead: err: could not read number of vertices\n"); return 1; } /* Make sure the number of sides is at least 3. */ if(num_vertices < 3) { fprintf(stderr, "polygonRead: err: too few vertices\n"); return 2; } /* Create a new Polygon object */ polygonInit(polyP, num_vertices); /* Read in the 2D points which are the vertices of the polygon. */ for(vi=0; vi < polyP->num_vertices; vi++) { if(fscanf(fp,"%lf %lf",&polyP->vertices[vi].x,&polyP->vertices[vi].y) != 2) { fprintf(stderr, "polygonRead: err: at vertex %i\n", vi); return 3; } } return 0; } /* polygonPrint: print vertices of a polygon, in order */ void polygonPrint(const PolygonT *polyP) { int vi; for(vi=0; vi < polyP->num_vertices; vi++) { printf("vertex[%3i] = (%15lf, %15lf)\n", vi, polyP->vertices[vi].x, polyP->vertices[vi].y); } } /* vertexCross: cross product from one edge to another // // v0 (in): first vertex // v1 (in): second vertex // v2 (in): thrid vertex // // First edge is from v0 to v1. // Second edge is from v1 to v2. // // return cross product value. */ VertexComponentT vertexCross(const VertexT *v0, const VertexT *v1, const VertexT *v2) { return (v1->x - v0->x)*(v2->y - v0->y) - (v2->x - v0->x)*(v1->y - v0->y); } /* vertexAngle: angle of a turn through three vertices // // v0 (in): first vertex // v1 (in): second vertex // v2 (in): thrid vertex // // First edge is from v0 to v1. // Second edge is from v1 to v2. // // returns angle, in radians, from edge1 to edge2. */ double vertexAngle(const VertexT *v0, const VertexT *v1, const VertexT *v2) { VertexComponentT a1, a2; /* Find angles and make sure they're always positive. // a1 is the angle of the vector v1-v0. // a2 is the angle of the vector v2-v1. */ a1 = atan2(v1->y - v0->y, v1->x - v0->x); if(a1 < 0) { a1 += TWO_PI; } a2 = atan2(v2->y - v1->y, v2->x - v1->x); if(a2 < 0) { a2 += TWO_PI; } /* Compute external angle: a2 - a1. // Make sure returned angle is between -pi and pi. */ if(a2 - a1 > PI) { return a2 - a1 - TWO_PI; } else if(a2 - a1 < -PI) { return a2 - a1 + TWO_PI; } else { return a2 - a1; } } /* polygonIsConvex: test whether a polygon is convex // // returns TRUE if polygon corners all turn the same way. // return FALSE if polygon corners turn different ways. // // polyP (in): polygon // external_angle: (out) total external angle in radians of polygon. // if external angle > 2*pi and return value is TRUE // then the polygon has crossed lines, and is not convex. */ BooleanT polygonIsConvex(const PolygonT *polyP, double *external_angle) { int vi; /* vertex index */ int prev_angle_sign; int this_angle_sign; /* Find sign of first turn */ prev_angle_sign = SGN(vertexCross(&polyP->vertices[0], &polyP->vertices[1], &polyP->vertices[2])); *external_angle = vertexAngle(&polyP->vertices[0], &polyP->vertices[1], &polyP->vertices[2]); /* Test the turn angle of each edge, // and Keep track of the total external angle. */ for(vi=1; vi < polyP->num_vertices; vi++) { /* Find vertex cross product // and Accumulate external turning angle */ if(vi < (polyP->num_vertices-2)) { this_angle_sign = SGN(vertexCross(&polyP->vertices[vi], &polyP->vertices[vi+1], &polyP->vertices[vi+2])); *external_angle += vertexAngle(&polyP->vertices[vi], &polyP->vertices[vi+1], &polyP->vertices[vi+2]); } else if(vi < (polyP->num_vertices-1)) { /* Special case: next_to_last_vertex-to-first_vertex edge */ this_angle_sign = SGN(vertexCross(&polyP->vertices[vi], &polyP->vertices[vi+1], &polyP->vertices[0])); *external_angle += vertexAngle(&polyP->vertices[vi], &polyP->vertices[vi+1], &polyP->vertices[0]); } else { /* Special case: last_vertex-to-second_vertex edge */ this_angle_sign = SGN(vertexCross(&polyP->vertices[vi], &polyP->vertices[0], &polyP->vertices[1])); *external_angle += vertexAngle(&polyP->vertices[vi], &polyP->vertices[0], &polyP->vertices[1]); } /* Cases for turns: // this is non-zero: // prev is non-zero: // prev has different sign from this: not convex // prev is zero: set prev to this // this is zero: skip to next iteration */ if(this_angle_sign) { if(prev_angle_sign) { if(prev_angle_sign != this_angle_sign) { return FALSE; /* not convex */ } } else { prev_angle_sign = this_angle_sign; } } } return TRUE; } /* main: read in a polygon and test whether it's convex */ int main(int argc, char **argv) { PolygonT poly; BooleanT is_convex; double external_angle; /* Read a list of 2D polygon vertices (point). */ if(polygonRead(stdin, &poly)) { return 1; } /* Determine whether the polygon is convex. */ is_convex = polygonIsConvex(&poly, &external_angle); /* Print results */ if(is_convex) { if(ABS(external_angle) <= (TWO_PI + FUZZY_ZERO)) { printf("Polygon is convex\n"); } else { printf("Polygon is NOT convex\n"); printf("Lines cross: external angle is %lg radians\n", external_angle); } } else { printf("Polygon is NOT convex\n"); } /* Free dynamic memory */ polygonDelete(&poly); /* Make Unix happy */ return(0); }