#include <sys/types.h>#include <stdarg.h>#include <stdio.h> #include <sys/stat.h> #define X 0 #define Y 1 //typedef enum { FALSE, TRUE } bool; #define DIM 2 /* Dimension of points */ typedef int tPointi[DIM]; /* type integer point */ typedef double tPointd[DIM]; /* type double point */ #define PMAX 10000 /* Max # of pts in polygon */ typedef tPointi tPolygoni[PMAX];/* type integer polygon */ char InPoly( tPointi q, tPolygoni P, int n ); void PrintPoly( int n, tPolygoni P ); void PrintPoint( tPointi p ); void Copy ( tPolygoni a, tPolygoni b , int n ); int ReadPoly( tPolygoni P ) ; main() { int n; tPolygoni P, Porig; tPointi q; n = ReadPoly( P ); Copy( P, Porig, n ); while( scanf( "%d %d", &q[X], &q[Y]) != EOF ) { printf( "InPoly = %c/n", InPoly( q, P, n ) ); /* Refill the destroyed polygon with original. */ Copy( Porig, P, n ); } } /* InPoly returns a char in {i,o,v,e}. See above for definitions. */ char InPoly( tPointi q, tPolygoni P, int n ) { int i, i1; /* point index; i1 = i-1 mod n */ int d; /* dimension index */ double x; /* x intersection of e with ray */ int Rcross = 0; /* number of right edge/ray crossings */ int Lcross = 0; /* number of left edge/ray crossings */ printf("/n==>InPoly: q = "); PrintPoint(q); putchar('/n'); /* Shift so that q is the origin. Note this destroys the polygon. This is done for pedogical clarity. */ for( i = 0; i < n; i++ ) { for( d = 0; d < DIM; d++ ) P[i][d] = P[i][d] - q[d]; } /* For each edge e=(i-1,i), see if crosses ray. */ for( i = 0; i < n; i++ ) { /* First see if q=(0,0) is a vertex. */ if ( P[i][X]==0 && P[i][Y]==0 ) return 'v'; i1 = ( i + n - 1 ) % n; /* printf("e=(%d,%d)/t", i1, i); */ /* if e "straddles" the x-axis... */ /* The commented-out statement is logically equivalent to the one following. */ /* if( ( ( P[i][Y] > 0 ) && ( P[i1][Y] <= 0 ) ) || ( ( P[i1][Y] > 0 ) && ( P[i] [Y] <= 0 ) ) ) { */ if( ( P[i][Y] > 0 ) != ( P[i1][Y] > 0 ) ) { /* e straddles ray, so compute intersection with ray. */ x = (P[i][X] * (double)P[i1][Y] - P[i1][X] * (double)P[i][Y])/(double)(P[i1][Y] - P[i][Y]); /* printf("straddles: x = %g/t", x); */ /* crosses ray if strictly positive intersection. */ if (x > 0) Rcross++; } /* printf("Right cross=%d/t", Rcross); */ /* if e straddles the x-axis when reversed... */ /* if( ( ( P[i] [Y] < 0 ) && ( P[i1][Y] >= 0 ) ) || ( ( P[i1][Y] < 0 ) && ( P[i] [Y] >= 0 ) ) ) { */ if ( ( P[i][Y] < 0 ) != ( P[i1][Y] < 0 ) ) { /* e straddles ray, so compute intersection with ray. */ x = (P[i][X] * P[i1][Y] - P[i1][X] * P[i][Y]) / (double)(P[i1][Y] - P[i][Y]); /* printf("straddles: x = %g/t", x); */ /* crosses ray if strictly positive intersection. */ if (x < 0) Lcross++; } /* printf("Left cross=%d/n", Lcross); */ } /* q on the edge if left and right cross are not the same parity. */ if( ( Rcross % 2 ) != (Lcross % 2 ) ) return 'e'; /* q inside iff an odd number of crossings. */ if( (Rcross % 2) == 1 ) return 'i'; else return 'o'; } void PrintPoint( tPointi p ) { int i; putchar('('); for ( i = 0; i < DIM; i++ ) { printf("%d", 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 i, n; do { printf( "Input the number of vertices:/n"); scanf( "%d", &n ); if ( n <= PMAX ) break; printf("Error in read_poly: too many points; max is %d/n", PMAX); } while ( 1 ); printf( "Polygon:/n" ); printf( " i x y/n"); for ( i = 0; i < n; i++ ) { scanf( "%d %d", &P[i][0], &P[i][1] ); printf("=MM/n", i, P[i][0], P[i][1]); } printf("n = = vertices read/n",n); putchar('/n'); return n; } void PrintPoly( int n, tPolygoni P ) { int i; printf("Polygon:/n"); printf(" i x y/n"); for( i = 0; i < n; i++ ) printf("=MM/n", i, P[i][0], P[i][1]); } /* Copy polygon a to b (overwriting b). */ void Copy( tPolygoni a, tPolygoni b, int n ) { int i, j; for ( i=0; i < n; i++) for ( j = 0; j < DIM; j++ ) b[i][j] = a[i][j]; } /* bool EqPoint( tPointi a, tPointi b ) { int i; for ( i = 0; i < DIM; i++ ) if ( a[i] != b[i]) return FALSE; return TRUE; } */ /*gcc -lstdc++ testpoint.cpp
645 2035 1010 1530 2520 3540 3025 1525 2525 20
*/
