home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 3 / RISC_DISC_3.iso / resources / etexts / gems / gemsiv / ptpoly_haines / p_test.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  24.2 KB  |  947 lines
  1. /* p_test.c - point in polygon inside/outside tester.  This is
  2.  * simply testing and display code, the actual algorithms are in ptinpoly.c.
  3.  *
  4.  * Probably the most important thing to set for timings is TEST_RATIO (too
  5.  * low and the timings are untrustworthy, too high and you wait forever).
  6.  * Start low and see how consistent separate runs appear to be.
  7.  *
  8.  * To add a new algorithm to the test suite, add code at the spots marked
  9.  * with '+++'.
  10.  *
  11.  * See Usage() for command line options (or just do "p_test -?").
  12.  *
  13.  * by Eric Haines, 3D/Eye Inc, erich@eye.com
  14.  */
  15.  
  16. /* Define TIMER to perform timings on code (need system timing function) */
  17. /* #define TIMER */
  18.  
  19. /* Number of times to try a single point vs. a polygon, per vertex.
  20.  * This should be greater than 1 / ( HZ * approx. single test time in seconds )
  21.  * in order to get a meaningful timings difference.  200 is reasonable for a
  22.  * IBM PC 25 MHz 386 with no FPU, 50000 is good for an HP 720 workstation.
  23.  * Start low and see how consistent separate runs appear to be.
  24.  */
  25.  
  26. #ifndef M_PI
  27. #define M_PI    3.14159265358979323846
  28. #endif
  29.  
  30. #ifdef    TIMER
  31. #define MACHINE_TEST_RATIO    50000
  32. #else
  33. #define MACHINE_TEST_RATIO        1
  34. #endif
  35.  
  36. /* ===========    that's all the easy stuff than can be changed  ============ */
  37.  
  38. #include <stdio.h>
  39. #include <stdlib.h>
  40. #include <math.h>
  41. #include "ptinpoly.h"
  42.  
  43. #ifdef    TIMER
  44. #ifdef    IBM_PC
  45. #include <bios.h>
  46. #include <time.h>
  47. #define HZ    CLK_TCK
  48. #define mGetTime(t)    (t) = biostime(0,0L) ;
  49.  
  50. #else    /* UNIX */
  51. #include <sys/types.h>
  52. #include <sys/param.h>
  53. #include <sys/times.h>
  54. struct    tms    Timebuf ;
  55.  
  56. #define mGetTime(t)    (t) = times(&Timebuf) ;
  57. #if (!(defined(sparc)||defined(__sparc__)))
  58. #define mGetTime(t)     (t) = times(&Timebuf) ;
  59. #else /* sparc (and others, you figure it out) */
  60. /* for Sun and others do something like: */
  61. #define mGetTime(t)  times(&Timebuf) ;                               \
  62.    (t) = Timebuf.tms_utime + Timebuf.tms_stime ;
  63. #endif /* sparc */
  64.  
  65. #endif
  66. #endif
  67.  
  68. #ifdef    DISPLAY
  69. #include <starbase.c.h>        /* HP display */
  70. #endif
  71.  
  72. #ifndef TRUE
  73. #define TRUE    1
  74. #define FALSE    0
  75. #endif
  76.  
  77. #ifndef HUGE
  78. #define HUGE    1.79769313486232e+308
  79. #endif
  80.  
  81. #define X    0
  82. #define Y    1
  83.  
  84. #ifdef    DISPLAY
  85. int    Display_Tests = 0 ;
  86. double    Display_Scale ;
  87. double    Display_OffsetX ;
  88. double    Display_OffsetY ;
  89. int    Fd ;
  90. #endif
  91.  
  92. typedef struct {
  93.     double    time_total ;
  94.     int    test_ratio ;
  95.     int    test_times ;
  96.     int    work ;
  97.     char    *name ;
  98.     int    flag ;
  99. } Statistics, *pStatistics ;
  100.  
  101. #define ANGLE_TEST         0
  102. #define BARYCENTRIC_TEST     1
  103. #define CROSSINGS_TEST         2
  104. #define EXTERIOR_TEST         3
  105. #define GRID_TEST         4
  106. #define INCLUSION_TEST         5
  107. #define CROSSMULT_TEST         6
  108. #define PLANE_TEST         7
  109. #define SPACKMAN_TEST         8
  110. #define TRAPEZOID_TEST         9
  111. #define WEILER_TEST         10
  112. /* +++ add new name here and increment TOT_NUM_TESTS +++ */
  113. #define TOT_NUM_TESTS         11
  114.  
  115. Statistics    St[TOT_NUM_TESTS] ;
  116.  
  117. char    *TestName[] = {
  118.     "angle",
  119.     "barycentric",
  120.     "crossings",
  121.     "exterior",
  122.     "grid",
  123.     "inclusion",
  124.     "cross-mult",
  125.     "plane",
  126.     "spackman",
  127.     "trapezoid",
  128.     "weiler" } ;
  129. /* +++ add new name here +++ */
  130.  
  131. /* minimum & maximum number of polygon vertices to generate */
  132. #define TOT_VERTS    1000
  133. static int    Min_Verts = 3 ;
  134. static int    Max_Verts = 6 ;
  135.  
  136. /* Test polygons are generated by going CCW in a circle around the origin from
  137.  * the X+ axis around and generating vertices.    The radius is how big the
  138.  * circumscribing circle is, the perturbation is how much each vertex is varied.
  139.  * So, radius 1 and perturbation 0 gives a regular, inscribed polygon;
  140.  * radius 0 and perturbation 1 gives a totally random polygon in the
  141.  * space [-1,1)
  142.  */
  143. static double    Vertex_Radius = 1.0 ;
  144. static double    Vertex_Perturbation = 0.0 ;
  145.  
  146. /* A box is circumscribed around the test polygon.  Making this box bigger
  147.  * is useful for a higher rejection rate.  For example, a ray tracing bounding
  148.  * box usually contains a few polygons, so making the box ratio say 2 or so
  149.  * could simulate this type of box.
  150.  */
  151. static double    Box_Ratio = 1.0 ;
  152.  
  153. /* for debugging purposes, you might want to set Test_Polygons and Test_Points
  154.  * high (say 1000), and then set the *_Test_Times to 1.     The timings will be
  155.  * useless, but you'll test 1000 polygons each with 1000 points.  You'll also
  156.  * probably want to set the Vertex_Perturbation to something > 0.0.
  157.  */
  158. /* number of different polygons to try - I like 50 or so; left low for now */
  159. static int    Test_Polygons = 20 ;
  160.  
  161. /* number of different intersection points to try - I like 50 or so */
  162. static int    Test_Points = 20 ;
  163.  
  164. /* for debugging or constrained test purposes, this value constrains the value
  165.  * of the polygon points and the test points to those on a grid emanating from
  166.  * the origin with this increment.  Points are shifted to the closest grid
  167.  * point.  0.0 means no grid.  NOTE:  by setting this value, a large number
  168.  * of points will be generated exactly on interior (triangle fan) or exterior
  169.  * edges.  Interior edge points will cause problems for the algorithms that
  170.  * generate interior edges (triangle fan).  "On edge" points are arbitrarily
  171.  * determined to be inside or outside the polygon, so results can differ.
  172.  */
  173. static double    Constraint_Increment = 0.0 ;
  174.  
  175. /* default resolutions */
  176. static    int    Grid_Resolution = 20 ;
  177. static    int    Trapezoid_Bins = 20 ;
  178.  
  179. #define Max(a,b)    (((a)>(b))?(a):(b))
  180.  
  181. #define FPRINTF_POLYGON                        \
  182.         fprintf( stderr, "point %g %g\n",        \
  183.             (float)point[X], (float)point[Y] ) ;    \
  184.         fprintf( stderr, "polygon (%d vertices):\n",    \
  185.             numverts ) ;                \
  186.         for ( n = 0 ; n < numverts ; n++ ) {        \
  187.             fprintf( stderr, "    %g %g\n",        \
  188.             (float)pgon[n][X], (float)pgon[n][Y]);    \
  189.         }
  190.  
  191. /* timing functions */
  192. #ifdef    TIMER
  193.  
  194. #define START_TIMER( test_id )                        \
  195.     /* do the test a bunch of times to get a useful time reading */ \
  196.     mGetTime( timestart ) ;                        \
  197.     for ( tcnt = St[test_id].test_times+1 ; --tcnt ; )
  198.  
  199. #define STOP_TIMER( test_id )                        \
  200.     mGetTime( timestop ) ;                        \
  201.     /* time in microseconds */                    \
  202.     St[test_id].time_total +=                    \
  203.         1000000.0 * (double)(timestop - timestart) /        \
  204.         (double)(HZ * St[test_id].test_times) ;
  205. #else
  206. #define START_TIMER( test_id )
  207. #define STOP_TIMER( test_id )
  208. #endif
  209.  
  210. char    *getenv() ;
  211. void    Usage() ;
  212. void    ScanOpts() ;
  213. void    ConstrainPoint() ;
  214. void    BreakString() ;
  215. #ifdef    DISPLAY
  216. void    DisplayPolygon() ;
  217. void    DisplayPoint() ;
  218. #endif
  219.  
  220.  
  221. /* test program - see Usage() for command line options */
  222. main(argc,argv)
  223. int argc;  char *argv[];
  224. {
  225. #ifdef    TIMER
  226. register long    tcnt ;
  227. long    timestart ;
  228. long    timestop ;
  229. #endif
  230.  
  231. int    i, j, k, n, numverts, inside_flag, inside_tot, numrec ;
  232. double    pgon[TOT_VERTS][2], point[2], angle, ran_offset ;
  233. double    rangex, rangey, scale, minx, maxx, diffx, miny, maxy, diffy ;
  234. double    offx, offy ;
  235. char    str[256], *strplus ;
  236. GridSet grid_set ;
  237. pPlaneSet    p_plane_set ;
  238. pSpackmanSet    p_spackman_set ;
  239. TrapezoidSet    trap_set ;
  240.  
  241. #ifdef    CONVEX
  242. pPlaneSet    p_ext_set ;
  243. pInclusionAnchor    p_inc_anchor ;
  244. #endif
  245.  
  246.     SRAN() ;
  247.  
  248.     ScanOpts( argc, argv ) ;
  249.  
  250.     for ( i = 0 ; i < TOT_NUM_TESTS ; i++ ) {
  251.     St[i].time_total = 0.0 ;
  252.     if ( i == ANGLE_TEST ) {
  253.         /* angle test is real slow, so test it fewer times */
  254.         St[i].test_ratio = MACHINE_TEST_RATIO / 10 ;
  255.     } else {
  256.         St[i].test_ratio = MACHINE_TEST_RATIO ;
  257.     }
  258.     St[i].name = TestName[i] ;
  259.     St[i].flag = 0 ;
  260.     }
  261.  
  262.     inside_tot = 0 ;
  263.  
  264. #ifdef    CONVEX
  265.     if ( Vertex_Perturbation > 0.0 && Max_Verts > 3 ) {
  266.     fprintf( stderr,
  267.         "warning: vertex perturbation is > 0.0, which is exciting\n");
  268.     fprintf( stderr,
  269.         "    when using convex-only algorithms!\n" ) ;
  270.     }
  271. #endif
  272.  
  273.     if ( Min_Verts == Max_Verts ) {
  274.     sprintf( str, "\nPolygons with %d vertices, radius %g, "
  275.         "perturbation +/- %g, bounding box scale %g",
  276.         Min_Verts, Vertex_Radius, Vertex_Perturbation, Box_Ratio ) ;
  277.     } else {
  278.     sprintf( str, "\nPolygons with %d to %d vertices, radius %g, "
  279.         "perturbation +/- %g, bounding box scale %g",
  280.         Min_Verts, Max_Verts, Vertex_Radius, Vertex_Perturbation,
  281.         Box_Ratio ) ;
  282.     }
  283.     strplus = &str[strlen(str)] ;
  284.     if ( St[TRAPEZOID_TEST].work ) {
  285.     sprintf( strplus, ", %d trapezoid bins", Trapezoid_Bins ) ;
  286.     strplus = &str[strlen(str)] ;
  287.     }
  288.     if ( St[GRID_TEST].work ) {
  289.     sprintf( strplus, ", %d grid resolution", Grid_Resolution ) ;
  290.     strplus = &str[strlen(str)] ;
  291.     }
  292. #ifdef    CONVEX
  293.     sprintf( strplus, ", convex" ) ;
  294.     strplus = &str[strlen(str)] ;
  295. #ifdef    HYBRID
  296.     sprintf( strplus, ", hybrid" ) ;
  297.     strplus = &str[strlen(str)] ;
  298. #endif
  299. #endif
  300. #ifdef    SORT
  301.     if ( St[PLANE_TEST].work || St[SPACKMAN_TEST].work ) {
  302.     sprintf( strplus, ", using triangles sorted by edge lengths" ) ;
  303.     strplus = &str[strlen(str)] ;
  304. #ifdef    CONVEX
  305.     sprintf( strplus, " and areas" ) ;
  306.     strplus = &str[strlen(str)] ;
  307. #endif
  308.     }
  309. #endif
  310. #ifdef    RANDOM
  311.     if ( St[EXTERIOR_TEST].work ) {
  312.     sprintf( strplus, ", exterior edges' order randomized" ) ;
  313.     strplus = &str[strlen(str)] ;
  314.     }
  315. #endif
  316.     sprintf( strplus, ".\n" ) ;
  317.     strplus = &str[strlen(str)] ;
  318.     BreakString( str ) ;
  319.     printf( "%s", str ) ;
  320.  
  321.     printf(
  322.     " Testing %d polygons with %d points\n", Test_Polygons, Test_Points ) ;
  323.  
  324. #ifdef    TIMER
  325.     printf( "doing timings" ) ;
  326.     fflush( stdout ) ;
  327. #endif
  328.     for ( i = 0 ; i < Test_Polygons ; i++ ) {
  329.  
  330.     /* make an arbitrary polygon fitting 0-1 range in x and y */
  331.     numverts = Min_Verts +
  332.         (int)(RAN01() * (double)(Max_Verts-Min_Verts+1)) ;
  333.  
  334.     /* add a random offset to the angle so that each polygon is not in
  335.      * some favorable (or unfavorable) alignment.
  336.      */
  337.     ran_offset = 2.0 * M_PI * RAN01() ;
  338.     minx = miny =  99999.0 ;
  339.     maxx = maxy = -99999.0 ;
  340.     for ( j = 0 ; j < numverts ; j++ ) {
  341.         angle = 2.0 * M_PI * (double)j / (double)numverts + ran_offset ;
  342.         pgon[j][X] = cos(angle) * Vertex_Radius +
  343.         ( RAN01() * 2.0 - 1.0 ) * Vertex_Perturbation ;
  344.         pgon[j][Y] = sin(angle) * Vertex_Radius +
  345.         ( RAN01() * 2.0 - 1.0 ) * Vertex_Perturbation ;
  346.  
  347.         ConstrainPoint( pgon[j] ) ;
  348.  
  349.         if ( pgon[j][X] < minx ) minx = pgon[j][X] ;
  350.         if ( pgon[j][X] > maxx ) maxx = pgon[j][X] ;
  351.         if ( pgon[j][Y] < miny ) miny = pgon[j][Y] ;
  352.         if ( pgon[j][Y] > maxy ) maxy = pgon[j][Y] ;
  353.     }
  354.  
  355.     offx = ( maxx + minx ) / 2.0 ;
  356.     offy = ( maxy + miny ) / 2.0 ;
  357.     if ( (diffx = maxx - minx ) > ( diffy = maxy - miny ) ) {
  358.         scale = 2.0 / (Box_Ratio * diffx) ;
  359.         rangex = 1.0 ;
  360.         rangey = diffy / diffx ;
  361.     } else {
  362.         scale = 2.0 / (Box_Ratio * diffy) ;
  363.         rangex = diffx / diffy ;
  364.         rangey = 1.0 ;
  365.     }
  366.  
  367.     for ( j = 0 ; j < numverts ; j++ ) {
  368.         pgon[j][X] = ( pgon[j][X] - offx ) * scale ;
  369.         pgon[j][Y] = ( pgon[j][Y] - offy ) * scale ;
  370.     }
  371.  
  372.     /* Set up number of times to test a point against a polygon, for
  373.      * the sake of getting a reasonable timing.  We already know how
  374.      * most of these will perform, so scale their # tests accordingly.
  375.      */
  376.     for ( j = 0 ; j < TOT_NUM_TESTS ; j++ ) {
  377.         if ( ( j == GRID_TEST ) || ( j == TRAPEZOID_TEST ) ) {
  378.         St[j].test_times = Max( St[j].test_ratio /
  379.             (int)sqrt((double)numverts), 1 ) ;
  380.         } else {
  381.         St[j].test_times = Max( St[j].test_ratio / numverts, 1 ) ;
  382.         }
  383.     }
  384.  
  385.     /* set up tests */
  386. #ifdef    CONVEX
  387.     if ( St[EXTERIOR_TEST].work ) {
  388.         p_ext_set = ExteriorSetup( pgon, numverts ) ;
  389.     }
  390. #endif
  391.  
  392.     if ( St[GRID_TEST].work ) {
  393.         GridSetup( pgon, numverts, Grid_Resolution, &grid_set ) ;
  394.     }
  395.  
  396. #ifdef    CONVEX
  397.     if ( St[INCLUSION_TEST].work ) {
  398.         p_inc_anchor = InclusionSetup( pgon, numverts ) ;
  399.     }
  400. #endif
  401.  
  402.     if ( St[PLANE_TEST].work ) {
  403.         p_plane_set = PlaneSetup( pgon, numverts ) ;
  404.     }
  405.  
  406.     if ( St[SPACKMAN_TEST].work ) {
  407.         p_spackman_set = SpackmanSetup( pgon, numverts, &numrec ) ;
  408.     }
  409.  
  410.     if ( St[TRAPEZOID_TEST].work ) {
  411.         TrapezoidSetup( pgon, numverts, Trapezoid_Bins, &trap_set ) ;
  412.     }
  413.  
  414. #ifdef    DISPLAY
  415.     if ( Display_Tests ) {
  416.         DisplayPolygon( pgon, numverts, i ) ;
  417.     }
  418. #endif
  419.  
  420.     /* now try # of points against it */
  421.     for ( j = 0 ; j < Test_Points ; j++ ) {
  422.         point[X] = RAN01() * rangex * 2.0 - rangex ;
  423.         point[Y] = RAN01() * rangey * 2.0 - rangey ;
  424.  
  425.         ConstrainPoint( point ) ;
  426.  
  427. #ifdef    DISPLAY
  428.         if ( Display_Tests ) {
  429.         DisplayPoint( point, TRUE ) ;
  430.         }
  431. #endif
  432.  
  433.         if ( St[ANGLE_TEST].work ) {
  434.         START_TIMER( ANGLE_TEST )
  435.             St[ANGLE_TEST].flag = AngleTest( pgon, numverts, point ) ;
  436.         STOP_TIMER( ANGLE_TEST )
  437.         }
  438.         if ( St[BARYCENTRIC_TEST].work ) {
  439.         START_TIMER( BARYCENTRIC_TEST )
  440.             St[BARYCENTRIC_TEST].flag =
  441.                 BarycentricTest( pgon, numverts, point ) ;
  442.         STOP_TIMER( BARYCENTRIC_TEST )
  443.         }
  444.         if ( St[CROSSINGS_TEST].work ) {
  445.         START_TIMER( CROSSINGS_TEST )
  446.             St[CROSSINGS_TEST].flag =
  447.                 CrossingsTest( pgon, numverts, point ) ;
  448.         STOP_TIMER( CROSSINGS_TEST )
  449.         }
  450. #ifdef    CONVEX
  451.         if ( St[EXTERIOR_TEST].work ) {
  452.         START_TIMER( EXTERIOR_TEST )
  453.             St[EXTERIOR_TEST].flag =
  454.                 ExteriorTest( p_ext_set, numverts, point );
  455.         STOP_TIMER( EXTERIOR_TEST )
  456.         }
  457. #endif
  458.         if ( St[GRID_TEST].work ) {
  459.         START_TIMER( GRID_TEST )
  460.             St[GRID_TEST].flag = GridTest( &grid_set, point ) ;
  461.         STOP_TIMER( GRID_TEST )
  462.         }
  463. #ifdef    CONVEX
  464.         if ( St[INCLUSION_TEST].work ) {
  465.         START_TIMER( INCLUSION_TEST )
  466.             St[INCLUSION_TEST].flag =
  467.                 InclusionTest( p_inc_anchor, point );
  468.         STOP_TIMER( INCLUSION_TEST )
  469.         }
  470. #endif
  471.         if ( St[CROSSMULT_TEST].work ) {
  472.         START_TIMER( CROSSMULT_TEST )
  473.             St[CROSSMULT_TEST].flag = CrossingsMultiplyTest(
  474.                 pgon, numverts, point ) ;
  475.         STOP_TIMER( CROSSMULT_TEST )
  476.         }
  477.         if ( St[PLANE_TEST].work ) {
  478.         START_TIMER( PLANE_TEST )
  479.             St[PLANE_TEST].flag =
  480.                 PlaneTest( p_plane_set, numverts, point ) ;
  481.         STOP_TIMER( PLANE_TEST )
  482.         }
  483.         if ( St[SPACKMAN_TEST].work ) {
  484.         START_TIMER( SPACKMAN_TEST )
  485.             St[SPACKMAN_TEST].flag =
  486.             SpackmanTest( pgon[0], p_spackman_set, numrec, point ) ;
  487.         STOP_TIMER( SPACKMAN_TEST )
  488.         }
  489.         if ( St[TRAPEZOID_TEST].work ) {
  490.         START_TIMER( TRAPEZOID_TEST )
  491.             St[TRAPEZOID_TEST].flag =
  492.                 TrapezoidTest( pgon, numverts, &trap_set, point ) ;
  493.         STOP_TIMER( TRAPEZOID_TEST )
  494.         }
  495.         if ( St[WEILER_TEST].work ) {
  496.         START_TIMER( WEILER_TEST )
  497.             St[WEILER_TEST].flag =
  498.                 WeilerTest( pgon, numverts, point ) ;
  499.         STOP_TIMER( WEILER_TEST )
  500.         }
  501. /* +++ add new procedure call here +++ */
  502.  
  503.         /* reality check if crossings test is used */
  504.         if ( St[CROSSINGS_TEST].work ) {
  505.         for ( k = 0 ; k < TOT_NUM_TESTS ; k++ ) {
  506.             if ( St[k].work &&
  507.                 ( St[k].flag != St[CROSSINGS_TEST].flag ) ) {
  508.             fprintf( stderr,
  509.                 "%s test says %s, crossings test says %s\n",
  510.                 St[k].name,
  511.                 St[k].flag ? "INSIDE" : "OUTSIDE",
  512.                 St[CROSSINGS_TEST].flag ? "INSIDE" : "OUTSIDE" ) ;
  513.             FPRINTF_POLYGON ;
  514.             }
  515.         }
  516.         }
  517.  
  518.         /* see if any flag is TRUE (i.e. the test point is inside) */
  519.         for ( k = 0, inside_flag = 0
  520.         ; k < TOT_NUM_TESTS && !inside_flag
  521.         ; k++ ) {
  522.         inside_flag = St[k].flag ;
  523.         }
  524.         inside_tot += inside_flag ;
  525.  
  526.         /* turn off highlighting for this point */
  527. #ifdef    DISPLAY
  528.         if ( Display_Tests ) {
  529.         DisplayPoint( point, FALSE ) ;
  530.         }
  531. #endif
  532.     }
  533.  
  534.     /* clean up test structures */
  535. #ifdef    CONVEX
  536.     if ( St[EXTERIOR_TEST].work ) {
  537.         ExteriorCleanup( p_ext_set ) ;
  538.         p_ext_set = NULL ;
  539.     }
  540. #endif
  541.  
  542.     if ( St[GRID_TEST].work ) {
  543.         GridCleanup( &grid_set ) ;
  544.     }
  545.  
  546. #ifdef    CONVEX
  547.     if ( St[INCLUSION_TEST].work ) {
  548.         InclusionCleanup( p_inc_anchor ) ;
  549.         p_inc_anchor = NULL ;
  550.     }
  551. #endif
  552.  
  553.     if ( St[PLANE_TEST].work ) {
  554.         PlaneCleanup( p_plane_set ) ;
  555.         p_plane_set = NULL ;
  556.     }
  557.  
  558.     if ( St[SPACKMAN_TEST].work ) {
  559.         SpackmanCleanup( p_spackman_set ) ;
  560.         p_spackman_set = NULL ;
  561.     }
  562.  
  563.     if ( St[TRAPEZOID_TEST].work ) {
  564.         TrapezoidCleanup( &trap_set ) ;
  565.     }
  566.  
  567. #ifdef    TIMER
  568.     /* print a "." every polygon done to give the user a warm feeling */
  569.     printf( "." ) ;
  570.     fflush( stdout ) ;
  571. #endif
  572.     }
  573.  
  574.     printf( "\n%g %% of all points were inside polygons\n",
  575.     (float)inside_tot * 100.0 / (float)(Test_Points*Test_Polygons) ) ;
  576.  
  577. #ifdef    TIMER
  578.     for ( i = 0 ; i < TOT_NUM_TESTS ; i++ ) {
  579.     if ( St[i].work ) {
  580.         printf( "  %s test time: %g microseconds per test\n",
  581.         St[i].name,
  582.         (float)( St[i].time_total/(double)(Test_Points*Test_Polygons) ) ) ;
  583.     }
  584.     }
  585. #endif
  586.  
  587.     return 0 ;
  588. }
  589.  
  590. void Usage()
  591. {
  592. /* +++ add new routine here +++ */
  593. printf("p_test [options] -{ABCEGIMPSTW}\n");
  594. printf("  -v minverts [maxverts] = variation in number of polygon vertices\n");
  595. printf("  -r radius = radius of polygon vertices generated\n");
  596. printf("  -p perturbation = perturbation of polygon vertices generated\n");
  597. printf("       These first three determine the type of polygon tested.\n");
  598. printf("       No perturbation gives regular polygons, while no radius\n");
  599. printf("       gives random polygons, and a mix gives semi-random polygons\n");
  600. printf("  -s size = scale of test point box around polygon (1.0 default)\n");
  601. printf("       A larger size means more points generated outside the\n");
  602. printf("       polygon.     By default test points are in the bounding box.\n");
  603. printf("  -b bins = number of y bins for trapezoid test\n");
  604. printf("  -g resolution = grid resolution for grid test\n");
  605. printf("  -n polygons = number of polygons to test (default %d)\n",
  606.         Test_Polygons);
  607. printf("  -i points = number of points to test per polygon (default %d)\n",
  608.         Test_Points);
  609. printf("  -c increment = constrain polygon and test points to grid\n");
  610. /* +++ add new routine here +++ */
  611. printf("  -{ABCEGIMPSTW} = angle/bary/crossings/exterior/grid/inclusion/cross-mult/\n");
  612. printf("       plane/spackman/trapezoid (bin)/weiler test (default is all)\n");
  613. printf("  -d = display polygons and points using starbase\n");
  614. }
  615.  
  616. void    ScanOpts( argc, argv )
  617. int argc;  char *argv[];
  618. {
  619. float    f1 ;
  620. int    i1 ;
  621. int    test_flag = FALSE ;
  622.  
  623.     for ( argc--, argv++; argc > 0; argc--, argv++ ) {
  624.     if ( **argv == '-' ) {
  625.         switch ( *++(*argv)) {
  626.  
  627.         case 'v':    /* vertex min & max */
  628.         argv++ ; argc-- ;
  629.         if ( argc && sscanf ( *argv, "%d", &i1 ) == 1 ) {
  630.             Min_Verts = i1 ;
  631.             argv++ ; argc-- ;
  632.             if ( argc && sscanf ( *argv, "%d", &i1 ) == 1 ) {
  633.             Max_Verts = i1 ;
  634.             } else {
  635.             argv-- ; argc++ ;
  636.             Max_Verts = Min_Verts ;
  637.             }
  638.         } else {
  639.             Usage() ;
  640.             exit(1) ;
  641.         }
  642.         break;
  643.  
  644.         case 'r':    /* vertex radius */
  645.         argv++ ; argc-- ;
  646.         if ( argc && sscanf ( *argv, "%f", &f1 ) == 1 ) {
  647.             Vertex_Radius = (double)f1 ;
  648.         } else {
  649.             Usage() ;
  650.             exit(1) ;
  651.         }
  652.         break;
  653.  
  654.         case 'p':    /* vertex perturbation */
  655.         argv++ ; argc-- ;
  656.         if ( argc && sscanf ( *argv, "%f", &f1 ) == 1 ) {
  657.             Vertex_Perturbation = (double)f1 ;
  658.         } else {
  659.             Usage() ;
  660.             exit(1) ;
  661.         }
  662.         break;
  663.  
  664.         case 's':    /* centered box size ratio - higher is bigger */
  665.         argv++ ; argc-- ;
  666.         if ( argc && sscanf ( *argv, "%f", &f1 ) == 1 ) {
  667.             Box_Ratio = (double)f1 ;
  668.             if ( Box_Ratio < 1.0 ) {
  669.             fprintf(stderr,"warning: ratio is smaller than 1.0\n");
  670.             }
  671.         } else {
  672.             Usage() ;
  673.             exit(1) ;
  674.         }
  675.         break;
  676.  
  677.         case 'b':    /* number of bins for trapezoid test */
  678.         argv++ ; argc-- ;
  679.         if ( argc && sscanf ( *argv, "%d", &i1 ) == 1 ) {
  680.             Trapezoid_Bins = i1 ;
  681.         } else {
  682.             Usage() ;
  683.             exit(1) ;
  684.         }
  685.         break;
  686.  
  687.         case 'g':    /* grid resolution for grid test */
  688.         argv++ ; argc-- ;
  689.         if ( argc && sscanf ( *argv, "%d", &i1 ) == 1 ) {
  690.             Grid_Resolution = i1 ;
  691.         } else {
  692.             Usage() ;
  693.             exit(1) ;
  694.         }
  695.         break;
  696.  
  697.         case 'n':    /* number of polygons to test */
  698.         argv++ ; argc-- ;
  699.         if ( argc && sscanf ( *argv, "%d", &i1 ) == 1 ) {
  700.             Test_Polygons = i1 ;
  701.         } else {
  702.             Usage() ;
  703.             exit(1) ;
  704.         }
  705.         break;
  706.  
  707.         case 'i':    /* number of intersections per polygon to test */
  708.         argv++ ; argc-- ;
  709.         if ( argc && sscanf ( *argv, "%d", &i1 ) == 1 ) {
  710.             Test_Points = i1 ;
  711.         } else {
  712.             Usage() ;
  713.             exit(1) ;
  714.         }
  715.         break;
  716.  
  717.         case 'c':    /* constrain increment (0 means don't use) */
  718.         argv++ ; argc-- ;
  719.         if ( argc && sscanf ( *argv, "%f", &f1 ) == 1 ) {
  720.             Constraint_Increment = (double)f1 ;
  721.         } else {
  722.             Usage() ;
  723.             exit(1) ;
  724.         }
  725.         break;
  726.  
  727.         case 'd':    /* display polygon & test points */
  728. #ifdef    DISPLAY
  729.         Display_Tests = 1 ;
  730. #else
  731.         fprintf( stderr,
  732.             "warning: display mode not compiled in - ignored\n" ) ;
  733. #endif
  734.         break;
  735.  
  736.         /* +++ add new symbol here +++ */
  737.         case 'A':    /* do tests specified */
  738.         case 'B':
  739.         case 'C':
  740.         case 'E':
  741.         case 'G':
  742.         case 'I':
  743.         case 'M':
  744.         case 'P':
  745.         case 'S':
  746.         case 'T':
  747.         case 'W':
  748.         test_flag = TRUE ;
  749.         if ( strchr( *argv, 'A' ) ) {
  750.             St[ANGLE_TEST].work = 1 ;
  751.         }
  752.         if ( strchr( *argv, 'B' ) ) {
  753.             St[BARYCENTRIC_TEST].work = 1 ;
  754.         }
  755.         if ( strchr( *argv, 'C' ) ) {
  756.             St[CROSSINGS_TEST].work = 1 ;
  757.         }
  758.         if ( strchr( *argv, 'E' ) ) {
  759. #ifdef    CONVEX
  760.             St[EXTERIOR_TEST].work = 1 ;
  761. #else
  762.             fprintf( stderr,
  763.             "warning: exterior test for -DCONVEX only - ignored\n" ) ;
  764. #endif
  765.         }
  766.         if ( strchr( *argv, 'G' ) ) {
  767.             St[GRID_TEST].work = 1 ;
  768.         }
  769.         if ( strchr( *argv, 'I' ) ) {
  770. #ifdef    CONVEX
  771.             St[INCLUSION_TEST].work = 1 ;
  772. #else
  773.             fprintf( stderr,
  774.             "warning: inclusion test for -DCONVEX only - ignored\n" ) ;
  775. #endif
  776.         }
  777.         if ( strchr( *argv, 'M' ) ) {
  778.             St[CROSSMULT_TEST].work = 1 ;
  779.         }
  780.         if ( strchr( *argv, 'P' ) ) {
  781.             St[PLANE_TEST].work = 1 ;
  782.         }
  783.         if ( strchr( *argv, 'S' ) ) {
  784.             St[SPACKMAN_TEST].work = 1 ;
  785.         }
  786.         if ( strchr( *argv, 'T' ) ) {
  787.             St[TRAPEZOID_TEST].work = 1 ;
  788.         }
  789.         if ( strchr( *argv, 'W' ) ) {
  790.             St[WEILER_TEST].work = 1 ;
  791.         }
  792.         /* +++ add new symbol test here +++ */
  793.         break;
  794.  
  795.         default:
  796.         Usage() ;
  797.         exit(1) ;
  798.         break ;
  799.         }
  800.  
  801.     } else {
  802.         Usage() ;
  803.         exit(1) ;
  804.     }
  805.     }
  806.  
  807.     if ( !test_flag ) {
  808.     fprintf( stderr,
  809.         "error: no point in polygon tests were specified, e.g. -PCS\n" ) ;
  810.     Usage() ;
  811.     exit(1) ;
  812.     }
  813. }
  814.  
  815. void ConstrainPoint( pt )
  816. double    *pt ;
  817. {
  818. double    val ;
  819.  
  820.     if ( Constraint_Increment > 0.0 ) {
  821.     pt[X] -=
  822.         ( val = fmod( pt[X], Constraint_Increment ) ) ;
  823.     if ( fabs(val) > Constraint_Increment * 0.5 ) {
  824.         pt[X] += (val > 0.0) ? Constraint_Increment :
  825.                     -Constraint_Increment ;
  826.     }
  827.     pt[Y] -=
  828.         ( val = fmod( pt[Y], Constraint_Increment ) ) ;
  829.     if ( fabs(val) > Constraint_Increment * 0.5 ) {
  830.         pt[Y] += (val > 0.0) ? Constraint_Increment :
  831.                     -Constraint_Increment ;
  832.     }
  833.     }
  834. }
  835.  
  836. /* break long strings into 80 or less character output.     Not foolproof, but
  837.  * good enough.
  838.  */
  839. void BreakString( str )
  840. char    *str ;
  841. {
  842. int    length, i, last_space, col ;
  843.  
  844.     length = strlen( str ) ;
  845.     last_space = 0 ;
  846.     col = 0 ;
  847.     for ( i = 0 ; i < length ; i++ ) {
  848.     if ( str[i] == ' ' ) {
  849.         last_space = i ;
  850.     }
  851.     if ( col == 79 ) {
  852.         str[last_space] = '\n' ;
  853.         col = i - last_space ;
  854.         last_space = 0 ;
  855.     } else {
  856.         col++ ;
  857.     }
  858.     }
  859. }
  860.  
  861. #ifdef    DISPLAY
  862. /* ================================= display routines ====================== */
  863. /* Currently for HP Starbase - pretty easy to modify */
  864. void DisplayPolygon( pgon, numverts, id )
  865. double    pgon[][2] ;
  866. int    numverts ;
  867. {
  868. static    int    init_flag = 0 ;
  869. int    i ;
  870. char    str[256] ;
  871.  
  872.     if ( !init_flag ) {
  873.     init_flag = 1 ;
  874.     /* make things big enough to avoid clipping */
  875.     Display_Scale = 0.45 / ( Vertex_Radius + Vertex_Perturbation ) ;
  876.     Display_OffsetX = Display_Scale + 0.05 ;
  877.     Display_OffsetY = Display_Scale + 0.10 ;
  878.  
  879.     Fd = DevOpen(OUTDEV,INIT) ;
  880.     shade_mode( Fd, CMAP_FULL|INIT, 0 ) ;
  881.     background_color( Fd, 0.1, 0.2, 0.4 ) ;
  882.     line_color( Fd, 1.0, 0.9, 0.7 ) ;
  883.     text_color( Fd, 1.0, 1.0, 0.2 ) ;
  884.     character_height( Fd, 0.08 ) ;
  885.     marker_type( Fd, 3 ) ;
  886.     }
  887.     clear_view_surface( Fd ) ;
  888.  
  889.     move2d( Fd,
  890.     (float)( pgon[numverts-1][X] * Display_Scale + Display_OffsetX ),
  891.     (float)( pgon[numverts-1][Y] * Display_Scale + Display_OffsetY ) ) ;
  892.     for ( i = 0 ; i < numverts ; i++ ) {
  893.     draw2d( Fd,
  894.         (float)( pgon[i][X] * Display_Scale + Display_OffsetX ),
  895.         (float)( pgon[i][Y] * Display_Scale + Display_OffsetY ) ) ;
  896.     }
  897.  
  898.     sprintf( str, "%4d sides, %3d of %d\n", numverts, id+1, Test_Polygons ) ;
  899.     text2d( Fd, 0.01, 0.01, str, VDC_TEXT, 0 ) ;
  900.     flush_buffer( Fd ) ;
  901. }
  902.  
  903. void DisplayPoint( point, hilit )
  904. double    point[2] ;
  905. int    hilit ;
  906. {
  907. float    clist[2] ;
  908.  
  909.     if ( hilit ) {
  910.     marker_color( Fd, 1.0, 0.0, 0.0 ) ;
  911.     } else {
  912.     marker_color( Fd, 0.2, 1.0, 1.0 ) ;
  913.     }
  914.  
  915.     clist[0] = (float)( point[0] * Display_Scale + Display_OffsetX ) ;
  916.     clist[1] = (float)( point[1] * Display_Scale + Display_OffsetY ) ;
  917.     polymarker2d( Fd, clist, 1, 0 ) ;
  918.     flush_buffer( Fd ) ;
  919. }
  920.  
  921. int DevOpen(dev_kind,init_mode)
  922. int dev_kind,init_mode;
  923. {
  924. char    *dev, *driver;
  925. int    fildes ;
  926.  
  927.     if ( dev_kind == OUTDEV ) {
  928.     dev = getenv("OUTINDEV");
  929.     if (!dev) dev = getenv("OUTDEV");
  930.     if (!dev) dev = "/dev/crt" ;
  931.     driver = getenv("OUTDRIVER");
  932.     if (!driver) driver = "hp98731" ;
  933.     } else {
  934.     dev = getenv("OUTINDEV");
  935.     if (!dev) dev = getenv("INDEV");
  936.     if (!dev) dev = "/dev/hil2" ;
  937.     driver = getenv("INDRIVER");
  938.     if (!driver) driver = "hp-hil" ;
  939.     }
  940.  
  941.     /* driver?    we don't need no stinking driver... */
  942.     fildes = gopen(dev,dev_kind,NULL,init_mode);
  943.  
  944.     return(fildes) ;
  945. }
  946. #endif
  947.