home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / source / graphicgems4.lha / GemsIV / convex_test / convex_opt.c next >
Encoding:
C/C++ Source or Header  |  1995-02-06  |  3.7 KB  |  114 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 double    Number;        /* float or double */
  18.  
  19. #define ConvexCompare(delta)                        \
  20.     ( (delta[0] > 0) ? -1 :    /* x coord diff, second pt > first pt */\
  21.       (delta[0] < 0) ?    1 :    /* x coord diff, second pt < first pt */\
  22.       (delta[1] > 0) ? -1 :    /* x coord same, second pt > first pt */\
  23.       (delta[1] < 0) ?    1 :    /* x coord same, second pt > first pt */\
  24.       0 )            /* second pt equals first point */
  25.  
  26. #define ConvexGetPointDelta(delta, pprev, pcur )            \
  27.     /* Given a previous point 'pprev', read a new point into 'pcur' */    \
  28.     /* and return delta in 'delta'.                    */    \
  29.     pcur = pVert[iread++];                        \
  30.     delta[0] = pcur[0] - pprev[0];                    \
  31.     delta[1] = pcur[1] - pprev[1];                    \
  32.  
  33. #define ConvexCross(p, q) p[0] * q[1] - p[1] * q[0];
  34.  
  35. #define ConvexCheckTriple                        \
  36.     if ( (thisDir = ConvexCompare(dcur)) == -curDir ) {            \
  37.       ++dirChanges;                            \
  38.       /* The following line will optimize for polygons that are  */ \
  39.       /* not convex because of classification condition 4,         */ \
  40.       /* otherwise, this will only slow down the classification. */ \
  41.       /* if ( dirChanges > 2 ) return NotConvex;             */ \
  42.     }                                    \
  43.     curDir = thisDir;                            \
  44.     cross = ConvexCross(dprev, dcur);                    \
  45.     if ( cross > 0 ) { if ( angleSign == -1 ) return NotConvex;        \
  46.                angleSign = 1;                    \
  47.              }                            \
  48.     else if (cross < 0) { if (angleSign == 1) return NotConvex;        \
  49.                 angleSign = -1;                \
  50.               }                        \
  51.     pSecond = pThird;        /* Remember ptr to current point. */    \
  52.     dprev[0] = dcur[0];        /* Remember current delta.      */    \
  53.     dprev[1] = dcur[1];                            \
  54.  
  55. classifyPolygon2( nvert, pVert )
  56. int    nvert;
  57. Number    pVert[][2];
  58. /* Determine polygon type. return one of:
  59.  *    NotConvex, NotConvexDegenerate,
  60.  *    ConvexCCW, ConvexCW, ConvexDegenerate
  61.  */
  62. {
  63.     int         curDir, thisDir, dirChanges = 0,
  64.          angleSign = 0, iread, endOfData;
  65.     Number   *pSecond, *pThird, *pSaveSecond, dprev[2], dcur[2], cross;
  66.  
  67.     /* if ( nvert <= 0 ) return error;         if you care */
  68.  
  69.     /* Get different point, return if less than 3 diff points. */
  70.     if ( nvert < 3 ) return ConvexDegenerate;
  71.     iread = 1;
  72.     while ( 1 ) {
  73.     ConvexGetPointDelta( dprev, pVert[0], pSecond );
  74.     if ( dprev[0] || dprev[1] ) break;
  75.     /* Check if out of points. Check here to avoid slowing down cases
  76.      * without repeated points.
  77.      */
  78.     if ( iread >= nvert ) return ConvexDegenerate;
  79.     }
  80.  
  81.     pSaveSecond = pSecond;
  82.  
  83.     curDir = ConvexCompare(dprev);    /* Find initial direction */
  84.  
  85.     while ( iread < nvert ) {
  86.     /* Get different point, break if no more points */
  87.     ConvexGetPointDelta(dcur, pSecond, pThird );
  88.     if ( dcur[0] == 0.0  &&     dcur[1] == 0.0 ) continue;
  89.  
  90.     ConvexCheckTriple;        /* Check current three points */
  91.     }
  92.  
  93.     /* Must check for direction changes from last vertex back to first */
  94.     pThird = pVert[0];            /* Prepare for 'ConvexCheckTriple' */
  95.     dcur[0] = pThird[0] - pSecond[0];
  96.     dcur[1] = pThird[1] - pSecond[1];
  97.     if ( ConvexCompare(dcur) ) {
  98.     ConvexCheckTriple;
  99.     }
  100.  
  101.     /* and check for direction changes back to second vertex */
  102.     dcur[0] = pSaveSecond[0] - pSecond[0];
  103.     dcur[1] = pSaveSecond[1] - pSecond[1];
  104.     ConvexCheckTriple;            /* Don't care about 'pThird' now */
  105.  
  106.     /* Decide on polygon type given accumulated status */
  107.     if ( dirChanges > 2 )
  108.     return angleSign ? NotConvex : NotConvexDegenerate;
  109.  
  110.     if ( angleSign > 0 ) return ConvexCCW;
  111.     if ( angleSign < 0 ) return ConvexCW;
  112.     return ConvexDegenerate;
  113. }
  114.