home *** CD-ROM | disk | FTP | other *** search
/ Photo CD Demo 1 / Demo.bin / gems / gemsii / xlines.c < prev   
C/C++ Source or Header  |  1991-08-26  |  5KB  |  174 lines
  1. /* lines_intersect:  AUTHOR: Mukesh Prasad
  2.  *
  3.  *   This function computes whether two line segments,
  4.  *   respectively joining the input points (x1,y1) -- (x2,y2)
  5.  *   and the input points (x3,y3) -- (x4,y4) intersect.
  6.  *   If the lines intersect, the output variables x, y are
  7.  *   set to coordinates of the point of intersection.
  8.  *
  9.  *   All values are in integers.  The returned value is rounded
  10.  *   to the nearest integer point.
  11.  *
  12.  *   If non-integral grid points are relevant, the function
  13.  *   can easily be transformed by substituting floating point
  14.  *   calculations instead of integer calculations.
  15.  *
  16.  *   Entry
  17.  *        x1, y1,  x2, y2   Coordinates of endpoints of one segment.
  18.  *        x3, y3,  x4, y4   Coordinates of endpoints of other segment.
  19.  *
  20.  *   Exit
  21.  *        x, y              Coordinates of intersection point.
  22.  *
  23.  *   The value returned by the function is one of:
  24.  *
  25.  *        DONT_INTERSECT    0
  26.  *        DO_INTERSECT      1
  27.  *        COLLINEAR         2
  28.  *
  29.  * Error condititions:
  30.  *
  31.  *     Depending upon the possible ranges, and particularly on 16-bit
  32.  *     computers, care should be taken to protect from overflow.
  33.  *
  34.  *     In the following code, 'long' values have been used for this
  35.  *     purpose, instead of 'int'.
  36.  *
  37.  */
  38.  
  39. #define    DONT_INTERSECT    0
  40. #define    DO_INTERSECT      1
  41. #define COLLINEAR         2
  42.  
  43. /**************************************************************
  44.  *                                                            *
  45.  *    NOTE:  The following macro to determine if two numbers  *
  46.  *    have the same sign, is for 2's complement number        *
  47.  *    representation.  It will need to be modified for other  *
  48.  *    number systems.                                         *
  49.  *                                                            *
  50.  **************************************************************/
  51.  
  52. #define SAME_SIGNS( a, b )    \
  53.         (((long) ((unsigned long) a ^ (unsigned long) b)) >= 0 )
  54.  
  55. int lines_intersect( x1, y1,   /* First line segment */
  56.              x2, y2,
  57.  
  58.              x3, y3,   /* Second line segment */
  59.              x4, y4,
  60.  
  61.              x,
  62.              y         /* Output value:
  63.                         * point of intersection */
  64.                )
  65. long
  66.     x1, y1, x2, y2, x3, y3, x4, y4,
  67.     *x, *y;
  68. {
  69.     long a1, a2, b1, b2, c1, c2; /* Coefficients of line eqns. */
  70.     long r1, r2, r3, r4;         /* 'Sign' values */
  71.     long denom, offset, num;     /* Intermediate values */
  72.  
  73.     /* Compute a1, b1, c1, where line joining points 1 and 2
  74.      * is "a1 x  +  b1 y  +  c1  =  0".
  75.      */
  76.  
  77.     a1 = y2 - y1;
  78.     b1 = x1 - x2;
  79.     c1 = x2 * y1 - x1 * y2;
  80.  
  81.     /* Compute r3 and r4.
  82.      */
  83.  
  84.  
  85.     r3 = a1 * x3 + b1 * y3 + c1;
  86.     r4 = a1 * x4 + b1 * y4 + c1;
  87.  
  88.     /* Check signs of r3 and r4.  If both point 3 and point 4 lie on
  89.      * same side of line 1, the line segments do not intersect.
  90.      */
  91.  
  92.     if ( r3 != 0 &&
  93.          r4 != 0 &&
  94.          SAME_SIGNS( r3, r4 ))
  95.         return ( DONT_INTERSECT );
  96.  
  97.     /* Compute a2, b2, c2 */
  98.  
  99.     a2 = y4 - y3;
  100.     b2 = x3 - x4;
  101.     c2 = x4 * y3 - x3 * y4;
  102.  
  103.     /* Compute r1 and r2 */
  104.  
  105.     r1 = a2 * x1 + b2 * y1 + c2;
  106.     r2 = a2 * x2 + b2 * y2 + c2;
  107.  
  108.     /* Check signs of r1 and r2.  If both point 1 and point 2 lie
  109.      * on same side of second line segment, the line segments do
  110.      * not intersect.
  111.      */
  112.  
  113.     if ( r1 != 0 &&
  114.          r2 != 0 &&
  115.          SAME_SIGNS( r1, r2 ))
  116.         return ( DONT_INTERSECT );
  117.  
  118.     /* Line segments intersect: compute intersection point. 
  119.      */
  120.  
  121.     denom = a1 * b2 - a2 * b1;
  122.     if ( denom == 0 )
  123.         return ( COLLINEAR );
  124.     offset = denom < 0 ? - denom / 2 : denom / 2;
  125.  
  126.     /* The denom/2 is to get rounding instead of truncating.  It
  127.      * is added or subtracted to the numerator, depending upon the
  128.      * sign of the numerator.
  129.      */
  130.  
  131.     num = b1 * c2 - b2 * c1;
  132.     *x = ( num < 0 ? num - offset : num + offset ) / denom;
  133.  
  134.     num = a2 * c1 - a1 * c2;
  135.     *y = ( num < 0 ? num - offset : num + offset ) / denom;
  136.  
  137.     return ( DO_INTERSECT );
  138.     } /* lines_intersect */
  139.  
  140. /* A main program to test the function.
  141.  */
  142.  
  143. main()
  144. {
  145.     long x1, x2, x3, x4, y1, y2, y3, y4;
  146.     long x, y;
  147.  
  148.     for (;;) {
  149.         printf( "X1, Y1: " );
  150.     scanf( "%ld %ld", &x1, &y1 );
  151.         printf( "X2, Y2: " );
  152.     scanf( "%ld %ld", &x2, &y2 );
  153.         printf( "X3, Y3: " );
  154.     scanf( "%ld %ld", &x3, &y3 );
  155.         printf( "X4, Y4: " );
  156.     scanf( "%ld %ld", &x4, &y4 );
  157.  
  158.         switch ( lines_intersect( x1, y1, x2, y2, x3, y3, x4, y4, &x, &y )) {
  159.             case DONT_INTERSECT:
  160.              printf( "Lines don't intersect\n" );
  161.              break;
  162.             case COLLINEAR:
  163.                          printf( "Lines are collinear\n" );
  164.                          break;
  165.             case DO_INTERSECT:
  166.              printf( "Lines intersect at %ld,%ld\n", x, y );
  167.                          break;
  168.             }
  169.         }
  170.     } /* main */
  171.  
  172.  
  173.  
  174.