gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Beginners > coordinate of two segments crossing.

#67491 - deltree - Wed Jan 18, 2006 4:20 pm

I need a function that take 4 coordinates (two segments) and return 2 coordinate and wether the segment cross or not....
I can't find a good code for this. do you have a good and speed function for that ?

#67494 - Mucca - Wed Jan 18, 2006 5:02 pm

From Graphics Gems 2:

Code:
/* lines_intersect:  AUTHOR: Mukesh Prasad
 *
 *   This function computes whether two line segments,
 *   respectively joining the input points (x1,y1) -- (x2,y2)
 *   and the input points (x3,y3) -- (x4,y4) intersect.
 *   If the lines intersect, the output variables x, y are
 *   set to coordinates of the point of intersection.
 *
 *   All values are in integers.  The returned value is rounded
 *   to the nearest integer point.
 *
 *   If non-integral grid points are relevant, the function
 *   can easily be transformed by substituting floating point
 *   calculations instead of integer calculations.
 *
 *   Entry
 *        x1, y1,  x2, y2   Coordinates of endpoints of one segment.
 *        x3, y3,  x4, y4   Coordinates of endpoints of other segment.
 *
 *   Exit
 *        x, y              Coordinates of intersection point.
 *
 *   The value returned by the function is one of:
 *
 *        DONT_INTERSECT    0
 *        DO_INTERSECT      1
 *        COLLINEAR         2
 *
 * Error conditions:
 *
 *     Depending upon the possible ranges, and particularly on 16-bit
 *     computers, care should be taken to protect from overflow.
 *
 *     In the following code, 'long' values have been used for this
 *     purpose, instead of 'int'.
 *
 */

#define   DONT_INTERSECT    0
#define   DO_INTERSECT      1
#define COLLINEAR         2

/**************************************************************
 *                                                            *
 *    NOTE:  The following macro to determine if two numbers  *
 *    have the same sign, is for 2's complement number        *
 *    representation.  It will need to be modified for other  *
 *    number systems.                                         *
 *                                                            *
 **************************************************************/

#define SAME_SIGNS( a, b )   \
      (((long) ((unsigned long) a ^ (unsigned long) b)) >= 0 )

int lines_intersect( x1, y1,   /* First line segment */
           x2, y2,

           x3, y3,   /* Second line segment */
           x4, y4,

           x,
           y         /* Output value:
                      * point of intersection */
               )
long
    x1, y1, x2, y2, x3, y3, x4, y4,
    *x, *y;
{
    long a1, a2, b1, b2, c1, c2; /* Coefficients of line eqns. */
    long r1, r2, r3, r4;         /* 'Sign' values */
    long denom, offset, num;     /* Intermediate values */

    /* Compute a1, b1, c1, where line joining points 1 and 2
     * is "a1 x  +  b1 y  +  c1  =  0".
     */

    a1 = y2 - y1;
    b1 = x1 - x2;
    c1 = x2 * y1 - x1 * y2;

    /* Compute r3 and r4.
     */


    r3 = a1 * x3 + b1 * y3 + c1;
    r4 = a1 * x4 + b1 * y4 + c1;

    /* Check signs of r3 and r4.  If both point 3 and point 4 lie on
     * same side of line 1, the line segments do not intersect.
     */

    if ( r3 != 0 &&
         r4 != 0 &&
         SAME_SIGNS( r3, r4 ))
        return ( DONT_INTERSECT );

    /* Compute a2, b2, c2 */

    a2 = y4 - y3;
    b2 = x3 - x4;
    c2 = x4 * y3 - x3 * y4;

    /* Compute r1 and r2 */

    r1 = a2 * x1 + b2 * y1 + c2;
    r2 = a2 * x2 + b2 * y2 + c2;

    /* Check signs of r1 and r2.  If both point 1 and point 2 lie
     * on same side of second line segment, the line segments do
     * not intersect.
     */

    if ( r1 != 0 &&
         r2 != 0 &&
         SAME_SIGNS( r1, r2 ))
        return ( DONT_INTERSECT );

    /* Line segments intersect: compute intersection point.
     */

    denom = a1 * b2 - a2 * b1;
    if ( denom == 0 )
        return ( COLLINEAR );
    offset = denom < 0 ? - denom / 2 : denom / 2;

    /* The denom/2 is to get rounding instead of truncating.  It
     * is added or subtracted to the numerator, depending upon the
     * sign of the numerator.
     */

    num = b1 * c2 - b2 * c1;
    *x = ( num < 0 ? num - offset : num + offset ) / denom;

    num = a2 * c1 - a1 * c2;
    *y = ( num < 0 ? num - offset : num + offset ) / denom;

    return ( DO_INTERSECT );
    } /* lines_intersect */

/* A main program to test the function.
 */

main()
{
    long x1, x2, x3, x4, y1, y2, y3, y4;
    long x, y;

    for (;;) {
        printf( "X1, Y1: " );
   scanf( "%ld %ld", &x1, &y1 );
        printf( "X2, Y2: " );
   scanf( "%ld %ld", &x2, &y2 );
        printf( "X3, Y3: " );
   scanf( "%ld %ld", &x3, &y3 );
        printf( "X4, Y4: " );
   scanf( "%ld %ld", &x4, &y4 );

        switch ( lines_intersect( x1, y1, x2, y2, x3, y3, x4, y4, &x, &y )) {
            case DONT_INTERSECT:
          printf( "Lines don't intersect\n" );
          break;
            case COLLINEAR:
                         printf( "Lines are collinear\n" );
                         break;
            case DO_INTERSECT:
          printf( "Lines intersect at %ld,%ld\n", x, y );
                         break;
            }
        }
    } /* main */



Strength here is that no 'real' divides are required until it is known that segments intersect, and point is calculated. Its also pretty trivial to alter the last stage of the algorithm to output a point in fixed point or float, if you require more accuracy. If going for fixed point, be very careful with overflows.

There are other ways of doing this algorithm, the most important thing is what input you have. For segments described by their end points, this algorithm is pretty good, but if, for example, you already have a slope, or cartesian equation or something, another algorithm might be better.

#67592 - LOst? - Thu Jan 19, 2006 5:37 am

Is that function above using vector math? Is any of those formulas dot or cross products?
_________________
Exceptions are fun

#67605 - Mucca - Thu Jan 19, 2006 11:25 am

Not really. Its a way of solving simultaneous equations, to find the intersection point of a line. Actually I lie, the checks on r1,r2 and r3,r4 are essentially finding the cross product (known as perproduct in 2D) of each point of a segment relative to the other segment. If they are both the same sign, then they both lie on the same side of the other segment, and thus the segments do not intersect. Then the algorithm solves simultaneously to find the intersection point.

Look at http://www.harveycartel.org/metanet/tutorials/tutorialA.html on seperating axis theorem for collision detection, for clues as to the theory behind basic vector math.

#67687 - crossraleigh - Thu Jan 19, 2006 10:11 pm

If you just want to know if the segments intersect (and not where they intersect), Miked0801 has explained how to remove divides altogether. Just think of "current tic position" and "last tic position" as the points that define the second segment.

#67791 - Mucca - Fri Jan 20, 2006 11:17 am

Well thats exactly what the first half of the algorithm does, like I said r1-r4 are perproducts representing what side of the other segment the endpoint of a segment lie. You can just remove code from where COLINEAR is returned, and return intersection instead.

If its for collision detection and response purposes, the intersection point can be used to reflect the ball. Alternatively, with the point, you could solve for time to get the time of collision.

#67863 - Miked0801 - Fri Jan 20, 2006 11:21 pm

Sigh - all that work to figure out the math on my own and here's a nice gem book to do it for you :)

#67884 - Ultima2876 - Sat Jan 21, 2006 2:11 am

Miked0801 wrote:
Sigh - all that work to figure out the math on my own and here's a nice gem book to do it for you :)


Hate when that stuff happens =/