home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / intrvews / xgrab.lha / xgrab / ui / intersect.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-03-07  |  1.4 KB  |  86 lines
  1. /**
  2.    GRAB Graph Layout and Browser System
  3.  
  4.    Copyright (c) 1986, 1988 Regents of the University of California
  5.    Copyright (c) 1989, Tera Computer Company
  6.  **/
  7.  
  8.   /**
  9.      Algorithm for detecting if a line passes through a rectangle. Adapted
  10.      from the intersection algorithm in Bowyer & Woodwark's "A Programmer's
  11.      Geometry" (p. 133), in turn due to Cohen and Sutherland.
  12.    **/
  13.  
  14. #include "attribute.h"
  15. #include "digraph.h"
  16. #include "screen.h"
  17.  
  18. BOOL Intersect();
  19.  
  20. Abs(x) 
  21. {
  22.     if (x < 0)
  23.     {
  24.     return -x;
  25.     }
  26.     else
  27.     {
  28.     return x;
  29.     }
  30. }
  31.  
  32. Quadrant(x, y, box)
  33. int x, y;
  34. BOX *box;
  35. {
  36.     return (
  37.     1 * (x < box->min_x) +
  38.     2 * (x > box->max_x) +
  39.     4 * (y < box->min_y) +
  40.     8 * (y > box->max_y)
  41.     );
  42. }
  43.  
  44.  
  45. BOOL Intersect(x1, y1, x2, y2, bx1, by1, bx2, by2)
  46. int x1, y1, x2, y2, bx1, by1, bx2, by2;
  47. {
  48.     BOX *b;
  49.     int midX, midY, midQuad;
  50.  
  51.     b = (BOX *) malloc (sizeof(BOX));
  52.     b->min_x = MIN(bx1, bx2);
  53.     b->max_x = MAX(bx1, bx2);
  54.     b->min_y = MIN(by1, by2);
  55.     b->max_y = MAX(by1, by2);
  56.  
  57.     if ((Quadrant(x1, y1, b) & Quadrant(x2, y2, b)) != 0)
  58.     {
  59.     return FALSE;
  60.     }
  61.     
  62.     do 
  63.     {
  64.     midX = (x1 + x2)/2;
  65.     midY = (y1 + y2)/2;
  66.     midQuad = Quadrant(midX, midY, b);
  67.  
  68.     if (midQuad == 0)
  69.     {
  70.         return TRUE;
  71.     }
  72.     else if ((Quadrant(x1, y1, b) & midQuad) != 0) 
  73.     {
  74.         x1 = midX;
  75.         y1 = midY;
  76.     }
  77.     else 
  78.     {
  79.         x2 = midX;
  80.         y2 = midY;
  81.     }
  82.     } while (MAX(Abs(x1-x2), Abs(y1-y2)) > 1);
  83.  
  84.     return FALSE;
  85. }
  86.