Line-Line Intersection in C++
I’ve just been tasked with creating a function to get the intersection of two lines.
With the help of equations from Wolfram Mathworld I created this nifty function:
Point* intersection(Point p1, Point p2, Point p3, Point p4) {
// Store the values for fast access and easy
// equations-to-code conversion
float x1 = p1.x, x2 = p2.x, x3 = p3.x, x4 = p4.x;
float y1 = p1.y, y2 = p2.y, y3 = p3.y, y4 = p4.y;
float d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
// If d is zero, there is no intersection
if (d == 0) return NULL;
// Get the x and y
float pre = (x1*y2 - y1*x2), post = (x3*y4 - y3*x4);
float x = ( pre * (x3 - x4) - (x1 - x2) * post ) / d;
float y = ( pre * (y3 - y4) - (y1 - y2) * post ) / d;
// Check if the x and y coordinates are within both lines
if ( x < min(x1, x2) || x > max(x1, x2) ||
x < min(x3, x4) || x > max(x3, x4) ) return NULL;
if ( y < min(y1, y2) || y > max(y1, y2) ||
y < min(y3, y4) || y > max(y3, y4) ) return NULL;
// Return the point of intersection
Point* ret = new Point();
ret->x = x;
ret->y = y;
return ret;
}
Hope it will be to as good use to you as it is to me.
May 25th, 2010 at 14:33
You bloody beauty.
November 3rd, 2010 at 11:40
still learning C++ and this definitely helped me, thanks a bunch!
November 28th, 2010 at 23:55
Here is mycode
bool intersection(float x1,float y1,
float x2,float y2,
float x3,float y3,
float x4,float y4) {
// Store the values for fast access and easy
// equations-to-code conversion
//float x1 = p1.x, x2 = p2.x, x3 = p3.x, x4 = p4.x;
//float y1 = p1.y, y2 = p2.y, y3 = p3.y, y4 = p4.y;
float d = (x1 – x2) * (y3 – y4) – (y1 – y2) * (x3 – x4);
// If d is zero, there is no intersection
if (d == 0) return false;
// Get the x and y
float pre = (x1*y2 – y1*x2), post = (x3*y4 – y3*x4);
float x = ( pre * (x3 – x4) – (x1 – x2) * post ) / d;
float y = ( pre * (y3 – y4) – (y1 – y2) * post ) / d;
// Check if the x and y coordinates are within both lines
if ( x max(x1, x2) ||
x max(x3, x4) ) return false;
if ( y max(y1, y2) ||
y max(y3, y4) ) return false;
// Return the point of intersection
//But I don’t care about “where”, only “if”
//Point* ret = new Point();
//ret->x = x;
//ret->y = y;
return true;
}
void fixCollisions()
{
bigX=true; //Here’s the problem. Not with the hit detection math, but with the display
//of results
for (int i =0;i<wallUbound;i++)
{
if (intersection(FDX-cos(FDA),FDY-sin(FDA), //<–Right here
FDX+cos(FDA)+10,FDY+sin(FDA),
wallX[i]-cos(wallRot[i]),wallY[i]-sin(wallRot[i]),
wallX[i]+cos(wallRot[i]),wallY[i]+sin(wallRot[i])))
bigX=true;
}
}
March 8th, 2011 at 14:01
Your test for x & y being within the lines extent will often fail when one or other of the lines is either horizontal or vertical due to floating point rounding errors.
A better test would be:
if (x (std::max(x1, x2) + epsilon) ||
x (std::max(x3, x4) + epsilon))
return false;
if (y (std::max(y1, y2) + epsilon) ||
y (std::max(y3, y4) + epsilon))
return false;
Where epsilon is say, 1e-5. This has the effect of testing against a line with a thickness of 2*epsilon accommodating any rounding errors.
March 8th, 2011 at 14:17
Lets try that again taking account of HTML :)
if (x < (min(x1, x2) – epsilon) ||
x > (max(x1, x2) + epsilon) ||
x < (min(x3, x4) – epsilon) ||
x > (max(x3, x4) + epsilon))
return false;
if (y < (min(y1, y2) – epsilon) ||
y > (max(y1, y2) + epsilon) ||
y < (min(y3, y4) – epsilon) ||
y > (max(y3, y4) + epsilon))
return false;
March 23rd, 2011 at 05:22
@Brian Washechek
I ahve problen in C
I am trying to find intersection of multilines but failed it only gives 1st two
how should i check for multiple line intersection if I return boolean status i can check but how to reshuffle the end point each time
May 12th, 2011 at 02:55
I don’t get it. Are you making fun of how little I know?
March 22nd, 2012 at 01:57
Don’t return a bool to check multiple line intersections, you MUST return a point. When you have a point from the first two lines check to see if the point is valid for the 3,4,5…n lines if all return true then yes they all intersect.
November 24th, 2012 at 21:36
Thanks! AND Thanks Stephen!
I was writing a path planning algorithm where the obstacles were all up-right rectangles so at least one of the two lines I passed to this function would always be either horizontal or vertical. It would have taken me way too long to figure out what was wrong if I didn’t see your post.