home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 3 / RISC_DISC_3.iso / resources / etexts / gems / gemsiv / convex_test / convex_opt.c next >
Encoding:
C/C++ Source or Header  |  1994-05-16  |  3.8 KB  |  117 lines
  1. /*
  2.  * C code from the article
  3.  * "Testing the Convexity of a Polygon"
  4.  * by Peter Schorn and Frederick Fisher,
  5.  *    (schorn@inf.ethz.ch, fred@kpc.com)
  6.  * in "Graphics Gems IV", Academic Press, 1994
  7.  */
  8.  
  9. /* Reasonably Optimized Routine to Classify a Polygon's Shape */
  10.  
  11. /*
  12.  
  13. .. code omitted which reads polygon, stores in an array, and calls
  14.     classifyPolygon2()
  15. */
  16.  
  17. typedef enum { NotConvex, NotConvexDegenerate,
  18.            ConvexDegenerate, ConvexCCW, ConvexCW } PolygonClass;
  19.  
  20. typedef double    Number;        /* float or double */
  21.  
  22. #define ConvexCompare(delta)                        \
  23.     ( (delta[0] > 0) ? -1 :    /* x coord diff, second pt > first pt */\
  24.       (delta[0] < 0) ?    1 :    /* x coord diff, second pt < first pt */\
  25.       (delta[1] > 0) ? -1 :    /* x coord same, second pt > first pt */\
  26.       (delta[1] < 0) ?    1 :    /* x coord same, second pt > first pt */\
  27.       0 )            /* second pt equals first point */
  28.  
  29. #define ConvexGetPointDelta(delta, pprev, pcur )            \
  30.     /* Given a previous point 'pprev', read a new point into 'pcur' */    \
  31.     /* and return delta in 'delta'.                    */    \
  32.     pcur = pVert[iread++];                        \
  33.     delta[0] = pcur[0] - pprev[0];                    \
  34.     delta[1] = pcur[1] - pprev[1];                    \
  35.  
  36. #define ConvexCross(p, q) p[0] * q[1] - p[1] * q[0];
  37.  
  38. #define ConvexCheckTriple                        \
  39.     if ( (thisDir = ConvexCompare(dcur)) == -curDir ) {            \
  40.       ++dirChanges;                            \
  41.       /* The following line will optimize for polygons that are  */ \
  42.       /* not convex because of classification condition 4,         */ \
  43.       /* otherwise, this will only slow down the classification. */ \
  44.       /* if ( dirChanges > 2 ) return NotConvex;             */ \
  45.     }                                    \
  46.     curDir = thisDir;                            \
  47.     cross = ConvexCross(dprev, dcur);                    \
  48.     if ( cross > 0 ) { if ( angleSign == -1 ) return NotConvex;        \
  49.                angleSign = 1;                    \
  50.              }                            \
  51.     else if (cross < 0) { if (angleSign == 1) return NotConvex;        \
  52.                 angleSign = -1;                \
  53.               }                        \
  54.     pSecond = pThird;        /* Remember ptr to current point. */    \
  55.     dprev[0] = dcur[0];        /* Remember current delta.      */    \
  56.     dprev[1] = dcur[1];                            \
  57.  
  58. classifyPolygon2( nvert, pVert )
  59. int    nvert;
  60. Number    pVert[][2];
  61. /* Determine polygon type. return one of:
  62.  *    NotConvex, NotConvexDegenerate,
  63.  *    ConvexCCW, ConvexCW, ConvexDegenerate
  64.  */
  65. {
  66.     int         curDir, thisDir, dirChanges = 0,
  67.          angleSign = 0, iread ;
  68.     Number   *pSecond, *pThird, *pSaveSecond, dprev[2], dcur[2], cross;
  69.  
  70.     /* if ( nvert <= 0 ) return error;         if you care */
  71.  
  72.     /* Get different point, return if less than 3 diff points. */
  73.     if ( nvert < 3 ) return ConvexDegenerate;
  74.     iread = 1;
  75.     while ( 1 ) {
  76.     ConvexGetPointDelta( dprev, pVert[0], pSecond );
  77.     if ( dprev[0] || dprev[1] ) break;
  78.     /* Check if out of points. Check here to avoid slowing down cases
  79.      * without repeated points.
  80.      */
  81.     if ( iread >= nvert ) return ConvexDegenerate;
  82.     }
  83.  
  84.     pSaveSecond = pSecond;
  85.  
  86.     curDir = ConvexCompare(dprev);    /* Find initial direction */
  87.  
  88.     while ( iread < nvert ) {
  89.     /* Get different point, break if no more points */
  90.     ConvexGetPointDelta(dcur, pSecond, pThird );
  91.     if ( dcur[0] == 0.0  &&     dcur[1] == 0.0 ) continue;
  92.  
  93.     ConvexCheckTriple;        /* Check current three points */
  94.     }
  95.  
  96.     /* Must check for direction changes from last vertex back to first */
  97.     pThird = pVert[0];            /* Prepare for 'ConvexCheckTriple' */
  98.     dcur[0] = pThird[0] - pSecond[0];
  99.     dcur[1] = pThird[1] - pSecond[1];
  100.     if ( ConvexCompare(dcur) ) {
  101.     ConvexCheckTriple;
  102.     }
  103.  
  104.     /* and check for direction changes back to second vertex */
  105.     dcur[0] = pSaveSecond[0] - pSecond[0];
  106.     dcur[1] = pSaveSecond[1] - pSecond[1];
  107.     ConvexCheckTriple;            /* Don't care about 'pThird' now */
  108.  
  109.     /* Decide on polygon type given accumulated status */
  110.     if ( dirChanges > 2 )
  111.     return angleSign ? NotConvex : NotConvexDegenerate;
  112.  
  113.     if ( angleSign > 0 ) return ConvexCCW;
  114.     if ( angleSign < 0 ) return ConvexCW;
  115.     return ConvexDegenerate;
  116. }
  117.