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?