PDA

View Full Version : Line x Line intersection



Moon Rabbits
12-23-2009, 08:19 PM
Hey, so I'm trying to program a line x line intersection algorithm. I've worked out some code that does what I'm looking for, except it only works for lines of infinite length. Here's the code:


bool Intersects( float x0, float y0, float x1, float y1,
float x2, float y2, float x3, float y3, float &xint, float &yint)

// line 1 is defined by (x0, y0) and (x1, y1); line two is defined by
// (x2, y2) and (x3, y3). coordinate of intersection returned via
// reference in xint and yint
{
//Store our Intersection point
xint = 0; yint = 0;

//This Line
double a1 = (y1 - y0);
double b1 = (x0 - x1);
double c1 = (x1*y0 - x0*y1);

//Line to test against
double a2 = (y3 - y2);
double b2 = (x2 - x3);
double c2 = (x3*y2 - x2*y3);

double denom = a1*b2 - a2*b1;

//Check for parallel lines
if(denom == 0) { return false; }

//Get the intersection point
xint = (b1*c2 - b2*c1)/denom;
yint = (a2*c1 - a1*c2)/denom;

return true;
}

I want to make it so it checks intersections on only the line segments defined by the coordinates passed (as opposed to the infinite lines defined the coordinates). I thought this would be easy by simply adding an if statement that checks if the intersection point lies upon both lines but I haven't been able to make it work properly :(

Any ideaassssss?

Endless
12-24-2009, 09:13 AM
xint must be greater than max(min(x0,x1),min(x2,x3)) and lower than min(max(x0,x1),max(x2,x3)) and yint must be greater than max(min(y0,y1),min(y2,y3)) and lower than min(max(y0,y1),max(y2,y3))