Skip to main content
GameDev.net gamedev.net

PRO Tired of ads? Read GameDev.net ad-free and help keep the community independent with GameDev Pro — $3/month.

Article

Fast 2D Line Intersection Algorithm

Scott
July 16, 1999 20.4k views
Share on X LinkedIn Facebook Reddit
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
License: gdol

Related Tutorials

Discussion

Discussion

Loading comments...

More from Scott