•      Sign In
• Create Account

Banner advertising on our site currently available from just \$5!

Like
1Likes
Dislike

# Fast 2D Line Intersection Algorithm

By Scott | Published Jul 16 1999 11:58 AM in Math and Physics

float function lines note infinity intersection slopes determinant coefficient
 If you find this article contains errors or problems rendering it unreadable (missing images or files, mangled code, improper text formatting, etc) please contact the editor so corrections can be made. Thank you for helping us improve this resource

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
a2,b2,c2,
det_inv,  // the inverse of the determinant of the coefficient
matrix
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);
else
m1 = (float)1e+10;   // close enough to infinity

if ((x3-x2)!=0)
m2 = (y3-y2)/(x3-x2);
else
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
Scott

Comments
Fantastic for people who needs those "long projectiles" like fast bullets.
Missing only the line versus rectangle collision!

Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.

PARTNERS