Jump to content

Fast 2D Line Intersection Algorithm

float function lines note infinity intersection slopes determinant coefficient

4: Adsense

Perhaps something like this may help. Though it may not be fast enough

void Intersect_Lines(float x0,float y0,float x1,float y1,
                     float x2,float y2,float x3,float y3,
                     float *xi,float *yi)
// this function computes the intersection of the sent lines
// and returns the intersection point, note that the function assumes
// the lines intersect. the function can handle vertical as well
// as horizontal lines. note the function isn't very clever, it simply
//applies the math, but we don't need speed since this is a
//pre-processing step

float a1,b1,c1, // constants of linear equations
      det_inv,  // the inverse of the determinant of the coefficient
      m1,m2;    // the slopes of each line

// compute slopes, note the cludge for infinity, however, this will
// be close enough

if ((x1-x0)!=0)
   m1 = (y1-y0)/(x1-x0);
   m1 = (float)1e+10;   // close enough to infinity

if ((x3-x2)!=0)
   m2 = (y3-y2)/(x3-x2);
   m2 = (float)1e+10;   // close enough to infinity

// compute constants

a1 = m1;
a2 = m2;

b1 = -1;
b2 = -1;

c1 = (y0-m1*x0);
c2 = (y2-m2*x2);

// compute the inverse of the determinate

det_inv = 1/(a1*b2 - a2*b1);

// use Kramers rule to compute xi and yi

*xi=((b1*c2 - b2*c1)*det_inv);
*yi=((a2*c1 - a1*c2)*det_inv);

} // end Intersect_Lines


Dec 06 2011 03:01 PM
Fantastic for people who needs those "long projectiles" like fast bullets.
Missing only the line versus rectangle collision!

Note: GameDev.net moderates article comments.