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?
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?