home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 3 / RISC_DISC_3.iso / resources / etexts / gems / gemsi / 2dclip / cross.c < prev    next >
C/C++ Source or Header  |  1992-09-15  |  7KB  |  302 lines
  1.  
  2. /*
  3.  * file cross.c:
  4.  *    calculate the intersections
  5.  */
  6. #include    <math.h>
  7. #include    "GraphicsGems.h"
  8. #include    "line.h"
  9. #include    "box.h"
  10. /*
  11.  * cross_calc:
  12.  *
  13.  *    PURPOSE
  14.  *    calculate the intersections between the polygon
  15.  *    stored in poly and the linesegment stored in l
  16.  *    and put the intersections into psol.
  17.  *
  18.  *    poly    pointer to the structure containing the polygon
  19.  *    l    pointer to the structure containing the linesegment
  20.  *    psol    pointer to the pointer where intersections are stored
  21.  *    nsol    current number of intersections stored
  22.  *    nsmax    maximum storage in psol for intersections
  23.  *        if nsol exceeds nsmax additional storage is allocated
  24.  *
  25.  */
  26. cross_calc(poly, l, psol, nsol, nsmax)
  27. CONTOUR    *poly;
  28. SEGMENT    *l;
  29. CLIST    **psol;
  30. short    *nsol, nsmax;
  31. {
  32.     SEGMENT    *p;
  33.     CLIST    *sol;
  34.     double    s;
  35.     long    x, y, a, b, c;
  36.     int    psort(), type;
  37.  
  38.     sol = *psol;
  39.     p = poly->_s;
  40.     do {
  41. /*
  42.  * calculate the a, b and c coefficients and determine the
  43.  * type of intersection
  44.  */
  45.  
  46.         a = (p->_to._y - p->_from._y)*(l->_to._x - l->_from._x) -
  47.             (p->_to._x - p->_from._x)*(l->_to._y - l->_from._y);
  48.         b = (p->_from._x - l->_from._x)*(l->_to._y - l->_from._y) -
  49.             (p->_from._y - l->_from._y)*(l->_to._x - l->_from._x);
  50.         c = (p->_from._x - l->_from._x)*(p->_to._y - p->_from._y) -
  51.             (p->_from._y - l->_from._y)*(p->_to._x - p->_from._x);
  52.         if(a == 0)
  53.             type = (b == 0) ? COINCIDE : PARALLEL;
  54.         else {
  55.             if(a > 0) {
  56.                 if((b >= 0 && b <= a) &&
  57.                    (c >= 0 && c <= a))
  58.                     type = CROSS;
  59.                 else
  60.                     type = NO_CROSS;
  61.             }
  62.             else {
  63.                 if((b <= 0 && b >= a) &&
  64.                    (c <= 0 && c >= a))
  65.                     type = CROSS;
  66.                 else
  67.                     type = NO_CROSS;
  68.             }
  69.         }
  70. /*
  71.  * process the intersection found
  72.  */
  73.         switch(type) {
  74.             case NO_CROSS: case PARALLEL:
  75.                 break;
  76.  
  77.             case CROSS:
  78.                 if(b == a || c == a || c == 0)
  79.                     break;
  80.                 if(b == 0 && 
  81.                    p_where(&(p->_prev->_from), &(p->_to), l) >= 0)
  82.                     break;
  83.                 s = (double)b/(double)a;
  84.                 if(l->_from._x == l->_to._x)
  85.                     x = l->_from._x;
  86.                 else
  87.                     x = p->_from._x + 
  88.                        (int)((p->_to._x - p->_from._x)*s);
  89.                 if(l->_from._y == l->_to._y)
  90.                     y = l->_from._y;
  91.                 else
  92.                     y = p->_from._y + 
  93.                        (int)((p->_to._y - p->_from._y)*s);
  94.  
  95.                 if(*nsol == nsmax) {
  96.                     nsmax *= 2;
  97.                     *psol = sol = (CLIST *) realloc(sol,                             nsmax*sizeof(CLIST)); 
  98.                 }
  99.                 sol[*nsol]._p._x = x;
  100.                 sol[*nsol]._p._y = y;
  101.                 sol[*nsol]._type = STD;
  102.                 *nsol += 1;
  103.                 break;
  104.  
  105.             case COINCIDE:
  106.                 if(p_where(&(p->_prev->_from),
  107.                      &(p->_next->_to), l) > 0)
  108.                     break;
  109.                 if(l->_from._x != l->_to._x) {
  110.                     if((MAX(l->_from._x, l->_to._x) <
  111.                         MIN(p->_from._x, p->_to._x)  ) ||
  112.                        (MIN(l->_from._x, l->_to._x) >
  113.                         MAX(p->_from._x, p->_to._x))   )
  114.                         break;
  115.                     if(MIN(l->_from._x, l->_to._x) <
  116.                        MIN(p->_from._x, p->_to._x) ) {
  117.                         if(*nsol == nsmax) {
  118.                             nsmax *= 2;
  119.                             *psol = sol = (CLIST *) realloc(sol,                                 nsmax*sizeof(CLIST));
  120.                         }
  121.                         sol[*nsol]._p._x = p->_from._x;
  122.                         sol[*nsol]._p._y = p->_from._y;
  123.                         sol[*nsol]._type = DELAY;
  124.                         *nsol += 1;
  125.                     }
  126.                     if(MAX(l->_from._x, l->_to._x) >
  127.                        MAX(p->_from._x, p->_to._x) ) {
  128.                         if(*nsol == nsmax) {
  129.                             nsmax *= 2;
  130.                             *psol = sol = (CLIST *) realloc(sol,                                 nsmax*sizeof(CLIST));
  131.                         }
  132.                         sol[*nsol]._p._x = p->_to._x;
  133.                         sol[*nsol]._p._y = p->_to._y;
  134.                         sol[*nsol]._type = DELAY;
  135.                         *nsol += 1;
  136.                     }
  137.                 }
  138.                 else {
  139.  
  140.                     if((MAX(l->_from._y, l->_to._y) <
  141.                         MIN(p->_from._y, p->_to._y)  ) ||
  142.                        (MIN(l->_from._y, l->_to._y) >
  143.                         MAX(p->_from._y, p->_to._y)) )
  144.                         break;
  145.                     if(MIN(l->_from._y, l->_to._y) <
  146.                        MIN(p->_from._y, p->_to._y) ) {
  147.                         if(*nsol == nsmax) {
  148.                             nsmax *= 2;
  149.                             *psol = sol = (CLIST *) realloc(sol,                                 nsmax*sizeof(CLIST));
  150.                         }
  151.                         sol[*nsol]._p._x = p->_from._x;
  152.                         sol[*nsol]._p._y = p->_from._y;
  153.                         sol[*nsol]._type = DELAY;
  154.                         *nsol += 1;
  155.                     }
  156.                     if(MAX(l->_from._y, l->_to._y) >
  157.                        MAX(p->_from._y, p->_to._y) ) {
  158.                         if(*nsol == nsmax) {
  159.                             nsmax *= 2;
  160.                             *psol = sol = (CLIST *) realloc(sol,                                 nsmax*sizeof(CLIST));
  161.                         }
  162.                         sol[*nsol]._p._x = p->_to._x;
  163.                         sol[*nsol]._p._y = p->_to._y;
  164.                         sol[*nsol]._type = DELAY;
  165.                         *nsol += 1;
  166.                     }
  167.                 }
  168.                 break;
  169.         }
  170.         p = p->_next;
  171.     } while(p != poly->_s);
  172.     qsort(sol, *nsol, sizeof(CLIST), psort);
  173. }
  174.  
  175.  
  176. /*
  177.  * p_where
  178.  *
  179.  *    PURPOSE
  180.  *    determine position of point p1 and p2 relative to
  181.  *    linesegment l. 
  182.  *    Return value
  183.  *    < 0    p1 and p2 lie at different sides of l
  184.  *    = 0    one of both points lie on l
  185.  *    > 0    p1 and p2 lie at same side of l
  186.  *
  187.  *    p1    pointer to coordinates of point
  188.  *    p2    pointer to coordinates of point
  189.  *    l    pointer to linesegment
  190.  * 
  191.  */
  192. p_where(p1, p2, l)
  193. POINT    *p1, *p2;
  194. SEGMENT    *l;
  195. {
  196.     long    dx, dy, dx1, dx2, dy1, dy2, p_1, p_2;
  197.  
  198.     dx  = l->_to._x - l->_from._x;
  199.     dy  = l->_to._y - l->_from._y;
  200.     dx1 = p1->_x - l->_from._x;
  201.     dy1 = p1->_y - l->_from._y;
  202.     dx2 = p2->_x - l->_to._x;
  203.     dy2 = p2->_y - l->_to._y;
  204.     p_1 = (dx*dy1 - dy*dx1);
  205.     p_2 = (dx*dy2 - dy*dx2);
  206.     if(p_1 == 0 || p_2 == 0)
  207.         return(0);
  208.     else {
  209.         if((p_1 > 0 && p_2 < 0) || (p_1 < 0 && p_2 > 0))
  210.             return(-1);
  211.         else
  212.             return(1);
  213.     }
  214. }
  215.  
  216.  
  217. /*
  218.  * p_inside
  219.  *
  220.  *    PURPOSE
  221.  *    determine if the point stored in pt lies inside
  222.  *    the polygon stored in p
  223.  *    Return value:
  224.  *    FALSE    pt lies outside p
  225.  *    TRUE    pt lies inside  p
  226.  *
  227.  *    p    pointer to the polygon
  228.  *    pt    pointer to the point
  229.  */    
  230. boolean    p_inside(p, pt)
  231. CONTOUR    *p;
  232. POINT    *pt;
  233. {
  234.     SEGMENT    l;
  235.     CLIST    *sol;
  236.     short    nsol = 0, nsmax = 2, reduce = 0, i;
  237.     boolean    on_contour(), odd;
  238.     
  239.     l._from._x = p->_minx-2;
  240.     l._from._y = pt->_y;
  241.     l._to._x   = pt->_x;
  242.     l._to._y   = pt->_y;
  243.     sol = (CLIST *) calloc(2, sizeof(CLIST));
  244.     cross_calc(p, &l, &sol, &nsol, nsmax);
  245.     for(i=0; i<nsol-1; i++)
  246.         if(sol[i]._type == DELAY && sol[i+1]._type == DELAY)
  247.             reduce++;
  248.     free(sol);
  249.     odd = (nsol - reduce) & 0x01;
  250.     return(odd ? !on_contour(p, pt) : FALSE);
  251. }
  252.  
  253. /*
  254.  * function used for sorting
  255.  */
  256. psort(p1, p2)
  257. CLIST    *p1, *p2;
  258. {
  259.     if(p1->_p._x != p2->_p._x)
  260.         return(p1->_p._x - p2->_p._x);
  261.     else 
  262.         return(p1->_p._y - p2->_p._y);
  263. }
  264.  
  265.  
  266. /*
  267.  * on_contour
  268.  *
  269.  *    PURPOSE
  270.  *    determine if the point pt lies on the
  271.  *    contour p.
  272.  *    Return value
  273.  *    TRUE     point lies on contour
  274.  *    FALSE    point lies not on contour
  275.  *
  276.  *    p    pointer to the polygon structure
  277.  *    pt    pointer to the point
  278.  */
  279. boolean    on_contour(p, pt)
  280. CONTOUR    *p;
  281. POINT    *pt;
  282. {
  283.     SEGMENT    *sp;
  284.     long    dx1, dy1, dx2, dy2;
  285.  
  286.     sp = p->_s;
  287.     do {
  288.         if((pt->_x >= MIN(sp->_from._x, sp->_to._x)) &&
  289.            (pt->_x <= MAX(sp->_from._x, sp->_to._x))    ) { 
  290.             dx1 = pt->_x - sp->_from._x;
  291.             dx2 = sp->_to._x - pt->_x;
  292.             dy1 = pt->_y - sp->_from._y;
  293.             dy2 = sp->_to._y - pt->_y;
  294.             if(dy1*dx2 == dy2*dx1)
  295.                 return(TRUE);
  296.         }
  297.         sp = sp->_next;
  298.     } while(sp != p->_s);
  299.     return(FALSE);
  300. }
  301.  
  302.