Line-Line Intersection in C++

Line line intersection function explanation

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.

9 Responses to “Line-Line Intersection in C++”

  1. Phloxi Says:

    You bloody beauty.

  2. BNelsey Says:

    still learning C++ and this definitely helped me, thanks a bunch!

  3. Brian Washechek Says:

    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;

    }

    }

  4. Stephen Says:

    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.

  5. Stephen Says:

    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;

  6. varsha Says:

    @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

  7. Brian Washechek Says:

    I don’t get it. Are you making fun of how little I know?

  8. David Sopala Says:

    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.

  9. Niko Says:

    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.