#include #include #define ERROR 1 #define X 0 #define Y 1 typedef enum { FALSE, TRUE } bool; typedef enum { Pin, Qin, Unknown } tInFlag; #define DIM 2 /* Dimension of points */ typedef int tPointi[DIM]; /* type integer point */ typedef double tPointd[DIM]; /* type double point */ #define PMAX 1000 /* Max # of pts in polygon */ typedef tPointi tPolygoni[PMAX];/* type integer polygon */ int Area2( tPointi a, tPointi b, tPointi c ); void SubVec( tPointi a, tPointi b, tPointi c ); int Dot( tPointi a, tPointi b ); bool LeftOn( tPointi a, tPointi b, tPointi c ); void PrintPoly( int n, tPolygoni P ); void PrintPoint( tPointi p ); void PrintPointd( tPointd p ); void ConvexIntersect( tPolygoni P, tPolygoni Q, int n, int m ); tInFlag InOut( tPointd p, tInFlag inflag, bool aHB ); int Advance( int a, int *aadv, int n, bool inside, tPointi v ); bool Intersection( tPointi a, tPointi b, tPointi c, tPointi d, tPointd p ); main() { int n, m; tPolygoni P, Q; n = ReadPoly( P ); m = ReadPoly( Q ); ConvexIntersect( P, Q, n, m ); } void ConvexIntersect( tPolygoni P, tPolygoni Q, int n, int m ) /* P has n vertices, Q has m vertices. */ { int a, b; /* indices on P and Q (resp.) */ int a1, b1; /* a-1, b-1 (resp.) */ tPointi A, B; /* directed edges on P and Q (resp.) */ int cross; /* A x B */ bool bHA, aHB; /* b in H(A); a in H(b). */ tPointi Origin = {0,0}; /* (0,0) */ tPointd p; /* double point of intersection */ int i; /* loop counter */ tInFlag inflag; /* {Pin, Qin, Unknown}: which polygon is known to be inside */ int aadv, badv; /* # advances on a & b indices (from first intersection) */ /* Initialize variables. */ a = 0; b = 0; i = 0; inflag = Unknown; do { /* Computations of key variables. */ a1 = (a + n - 1) % n; b1 = (b + m - 1) % m; SubVec( P[a], P[a1], A ); SubVec( Q[b], Q[b1], B ); cross = Area2( Origin, A, B ); bHA = LeftOn( P[a1], P[a], Q[b] ); aHB = LeftOn( Q[b1], Q[b], P[a] ); /* If A & B intersect, update inflag. */ if ( Intersection( P[a1], P[a], Q[b1], Q[b], p ) ) { if ( inflag == Unknown ) { aadv = 0; badv = 0; } inflag = InOut( p, inflag, aHB ); } /* Advance rules. */ if ( cross >= 0 ) if ( bHA ) a = Advance( a, &aadv, n, inflag == Pin, P[a] ); else { b = Advance( b, &badv, m, inflag == Qin, Q[b] ); } else { if ( aHB ) b = Advance( b, &badv, m, inflag == Qin, Q[b] ); else a = Advance( a, &aadv, n, inflag == Pin, P[a] ); } /* Quit when both indices have cycled. */ } while ( (aadv < n) || (badv < m) ); /* Deal with special cases: not implemented here. */ if ( inflag == Unknown) { printf("The boundaries of P and Q do not intersect:\n"); printf("\tEither P and Q do not intersect, or\n"); printf("\tone properly contains the other\n"); } } /* Prints out the double point of intersection, and toggles in/out flag. */ tInFlag InOut( tPointd p, tInFlag inflag, bool aHB ) { PrintPointd( p ); putchar('\n'); /* Update inflag. */ if ( aHB ) return Pin; else return Qin; } /* Advances and prints out an inside vertex if appropriate. */ int Advance( int a, int *aadv, int n, bool inside, tPointi v ) { if ( inside ) { PrintPoint( v ); putchar('\n'); } (*aadv)++; return (a+1) % n; } bool Intersection( tPointi a, tPointi b, tPointi c, tPointi d, tPointd p ) { double s, t; /* The two parameters of the parametric eqns. */ double denom; /* Denoninator of solutions. */ denom = a[0] * ( d[1] - c[1] ) + b[0] * ( c[1] - d[1] ) + d[0] * ( b[1] - a[1] ) + c[0] * ( a[1] - b[1] ); /* If denom is zero, then the line segments are parallel. */ /* In this case, return false even though the segments might overlap. */ if (denom == 0.0) return FALSE; s = ( a[0] * ( d[1] - c[1] ) + c[0] * ( a[1] - d[1] ) + d[0] * ( c[1] - a[1] ) ) / denom; t = -( a[0] * ( c[1] - b[1] ) + b[0] * ( a[1] - c[1] ) + c[0] * ( b[1] - a[1] ) ) / denom; p[0] = a[0] + s * ( b[0] - a[0] ); p[1] = a[1] + s * ( b[1] - a[1] ); if ( (0.0 <= s) && (s <= 1.0) && (0.0 <= t) && (t <= 1.0) ) return TRUE; else return FALSE; } /* Implements a = b, assignment of points/vectors. Assignment between arrays is not possible in C. */ void PointAssign( tPointi a, tPointi b ) { int i; for ( i = 0; i < DIM; i++ ) a[i] = b[i]; } void PrintPoint( tPointi p ) { int i; putchar('('); for ( i = 0; i < DIM; i++ ) { printf("%d", p[i]); if ( i != DIM-1 ) putchar(','); } putchar(')'); } void PrintPointd( tPointd p ) { int i; putchar('('); for ( i = 0; i < DIM; i++ ) { printf("%5.2f", p[i]); if ( i != DIM-1 ) putchar(','); } putchar(')'); } /* Reads in the coordinates of the vertices of a polygon from stdin, puts them into P, and returns n, the number of vertices. Formatting conventions: etc. */ int ReadPoly( tPolygoni P ) { int n = 0; int nin; scanf("%d", &nin); printf("Polygon:\n"); printf(" i x y\n"); while ( (n < nin) && (scanf("%d %d",&P[n][0],&P[n][1]) != EOF) ) { printf("%3d%4d%4d\n", n, P[n][0], P[n][1]); ++n; } if (n < PMAX) printf("n = %3d vertices read\n",n); else printf("Error in read_poly: too many points; max is %d\n", PMAX); putchar('\n'); return n; } void PrintPoly( int n, tPolygoni P ) { int i; printf("Polygon:\n"); printf(" i l x y\n"); for( i = 0; i < n; i++ ) printf("%3d%4d%4d%4d\n", i, P[i][0], P[i][1]); } /* Returns true iff c is strictly to the left of the directed line through a to b. */ bool Left( tPointi a, tPointi b, tPointi c ) { return Area2( a, b, c ) > 0; } bool LeftOn( tPointi a, tPointi b, tPointi c ) { return Area2( a, b, c ) >= 0; } bool Collinear( tPointi a, tPointi b, tPointi c ) { return Area2( a, b, c ) == 0; } /* Puts a - b into c. */ void SubVec( tPointi a, tPointi b, tPointi c ) { int i; for( i = 0; i < DIM; i++ ) c[i] = a[i] - b[i]; } /* Returns twice the signed area of the triangle determined by a,b,c, positive if a,b,c are oriented ccw, and negative if cw. */ int Area2( tPointi a, tPointi b, tPointi c ) { return a[0] * b[1] - a[1] * b[0] + a[1] * c[0] - a[0] * c[1] + b[0] * c[1] - c[0] * b[1]; }