home *** CD-ROM | disk | FTP | other *** search
/ Photo CD Demo 1 / Demo.bin / gems / gemsiii / circlexc.c < prev    next >
C/C++ Source or Header  |  1992-03-16  |  4KB  |  186 lines
  1. #include <math.h>
  2. #include <stdlib.h>             /* for qsort */
  3.  
  4. #define START 0
  5. #define END 1
  6.  
  7. #define QUAD1  90.0
  8. #define QUAD2 180.0
  9. #define QUAD3 270.0
  10. #define QUAD4 360.0
  11. #define FACTOR 57.29577951
  12.  
  13. typedef struct {
  14.    float angle;
  15.    int type;
  16. } intsct_st;
  17.  
  18. int compare(intsct_st *, intsct_st *);  /* used by qsort */
  19.  
  20. /*
  21.  * clip_circle:
  22.  *   clips a circle with center (Xc,Yc) and radius R to the box
  23.  *   given by clip_bnds.
  24.  *   the function return value indicates the number of segments
  25.  *   after clipping.
  26.  *   the start and end angle values of the visible segments are
  27.  *   returned in ang_st and ang_en.
  28.  */
  29.  
  30. int clip_circle( float Xc, float Yc,  /* center of the circle */
  31.                  float R,             /* radius of the circle */
  32.                  float clip_bnds[],   /* clip boundary: 
  33.                                          [left, upper, right, lower] */
  34.                  float ang_st[],      /* start angles for visible arcs */
  35.                  float ang_en[] )     /* end angles for visible arcs */
  36. {
  37.    float alpha, beta, gamma, delta;
  38.    float circle_bnds[4];
  39.    int i, n, num_sector; 
  40.    int overlap;
  41.    float d;
  42.    intsct_st intsct[20];
  43.    float prev;
  44.  
  45.    /*
  46.     * find the bounding box of the circle
  47.     */
  48.    circle_bnds[0] = Xc + R;
  49.    circle_bnds[1] = Yc + R;
  50.    circle_bnds[2] = Xc - R;
  51.    circle_bnds[3] = Yc - R;
  52.  
  53.    /*
  54.     * do a bounding box check to see if the circle is completely 
  55.     * clipped out
  56.     */
  57.    if (circle_bnds[2] > clip_bnds[0] ||
  58.        circle_bnds[0] < clip_bnds[2] ||
  59.        circle_bnds[3] > clip_bnds[1] ||
  60.        circle_bnds[1] < clip_bnds[3])
  61.       return 0;
  62.  
  63.    alpha=beta=gamma=delta=0;
  64.    n = 0;
  65.  
  66.    if( circle_bnds[0] > clip_bnds[0] )
  67.    /*
  68.     * the right boundary is crossed
  69.     */
  70.    {
  71.       d = (float) ( clip_bnds[0] - Xc );
  72.       alpha = (int) FACTOR*acos(d/R);
  73.  
  74.       intsct[n].angle = 0; intsct[n++].type = START;
  75.       intsct[n].angle = alpha; intsct[n++].type = END;
  76.       intsct[n].angle = QUAD4-alpha; intsct[n++].type = START;
  77.       intsct[n].angle = QUAD4; intsct[n++].type = END;
  78.    }
  79.  
  80.    if( circle_bnds[1] > clip_bnds[1] )
  81.    /*
  82.     * the upper boundary is crossed
  83.     */
  84.    {
  85.       d = (float) ( clip_bnds[1] - Yc);
  86.       beta = (int) FACTOR*acos(d/R);
  87.  
  88.       if ( (QUAD1-beta) < 0 )
  89.       {
  90.          intsct[n].angle = QUAD4+QUAD1-beta; intsct[n++].type = START;
  91.          intsct[n].angle = QUAD4; intsct[n++].type = END;
  92.          intsct[n].angle = 0; intsct[n++].type = START;
  93.       }
  94.       else
  95.       {
  96.          intsct[n].angle = QUAD1-beta; intsct[n++].type = START;
  97.       }
  98.       intsct[n].angle = QUAD1+beta; intsct[n++].type = END;
  99.    }
  100.  
  101.    if( circle_bnds[2] < clip_bnds[2] )
  102.    /*
  103.     * the left boundary is crossed
  104.     */
  105.    {
  106.       d = (float) ( Xc - clip_bnds[2] );
  107.       gamma = (int) FACTOR*acos(d/R);
  108.  
  109.       intsct[n].angle = QUAD2-gamma; intsct[n++].type = START;
  110.       intsct[n].angle = QUAD2+gamma; intsct[n++].type = END;
  111.    }
  112.  
  113.    if( circle_bnds[3] < clip_bnds[3] )
  114.    /*
  115.     * the lower boundary is crossed
  116.     */
  117.    {
  118.       d = (float) ( Yc - clip_bnds[3] );
  119.       delta = (int) FACTOR*acos(d/R);
  120.  
  121.       intsct[n].angle = QUAD3-delta; intsct[n++].type = START;
  122.       if ( (QUAD3+delta) > QUAD4 )
  123.       {
  124.          intsct[n].angle = QUAD4; intsct[n++].type = END;
  125.          intsct[n].angle = 0; intsct[n++].type = START;
  126.          intsct[n].angle = QUAD3+delta-QUAD4; intsct[n++].type = END;
  127.       }
  128.       else
  129.       {
  130.          intsct[n].angle = QUAD3+delta; intsct[n++].type = END;
  131.       }
  132.    }
  133.    /*
  134.     * the complete circle is visible if n = 0
  135.     */
  136.    if (n == 0 )
  137.    {
  138.       ang_st[0] = 0;
  139.       ang_en[0] = QUAD4;
  140.       return 1;
  141.    }
  142.    /*
  143.     * Sort all events in increasing order of angles
  144.     */
  145.    qsort (intsct, (size_t) n, sizeof(intsct_st), compare);
  146.  
  147.    /*
  148.     * Extract the visible sectors
  149.     */
  150.    num_sector = 0; overlap = 0; prev = 0;
  151.  
  152.    for (i=0; i<n; i++)
  153.    {
  154.       if (overlap == 0)
  155.          if (intsct[i].angle > prev)
  156.          {
  157.             ang_st[num_sector] = prev;
  158.             ang_en[num_sector++] = intsct[i].angle;
  159.          }
  160.  
  161.       if (intsct[i].type == START)
  162.          overlap++;
  163.       else
  164.          overlap--;
  165.  
  166.       prev = intsct[i].angle;
  167.    }
  168.  
  169.    if (prev < QUAD4)
  170.    {
  171.       ang_st[num_sector] = prev;
  172.       ang_en[num_sector++] = QUAD4;
  173.    }
  174.    return num_sector;
  175. }
  176.  
  177. int compare(intsct_st *a, intsct_st *b)
  178. {
  179.    if (a->angle < b->angle)
  180.       return -1;
  181.    else if (a->angle == b->angle)
  182.       return 0;
  183.    else
  184.       return 1;
  185. }
  186.