Write a function to tell if two line segments intersect or not.

Question

Hussein · Accepted Answer

This is my approach:

1. Get the slope of the two lines m1, and m2
2. If they are equal means they are parallel and return false
3. else compute b1, and b2 such that the first line equation is y = m1x+b1 and the second line equation y = m2x+b2
4. Compute the intersection point X, Y such that m1x+b1 = m2x+b2 this will lead us to finding x and then y
5. Check in the first line and the second line SEGMENTS that they include this point ..

bool check(line l, point p) {
    double mnX = min(l.p1.x, l.p2.x);
    double mxX = max(l.p1.x, l.p2.x);
    
    if(!(mnX <= p.x && p.x <= mxX)) return false;
    
    return true;
}

bool lines_intersect(line l1, line l2) {
    
    double m1 = (l1.p1.y-l1.p2.y)/(l1.p1.x-l1.p2.x);
    double m2 = (l2.p1.y-l2.p2.y)/(l2.p1.x-l2.p2.x);
    
    if(fabs(m1-m2) <= 1e-9) return false;
	
    double b1 = l1.p1.y-(l1.p1.x)*m1;
    double b2 = l2.p1.y-(l2.p1.x)*m2;
	
    double intersectionX = (b1*-1+b2)/(m1-m2);
    double intersectionY = m1*intersectionX+b1;
	
	cout << intersectionX << " " << intersectionY << endl;

    if(check(l1, point(intersectionX, intersectionY)) && check(l2, point(intersectionX, intersectionY))) return true;
    
    return false;
}

Hussein · Answer

ActiveX answer is wrong.. this case will fail.. line(point(3, 1), point(9, 6)) and line(point(6, 3), point(9, 0)) your approach will return true.. while it should return false.

Tom · Answer

#include #include #include using namespace std; double f(double a0, double b0, double a1, double b1, double x, double y) { return (a1-a0)*y - (b1-b0)*x + a0*b1-a1*b0; } int main() { double x0, x1, y0, y1, x2, x3, y2, y3; cin >> x0 >> y0 >> x1 >> y1 >> x2 >> y2 >> x3 >> y3; if (f(x0, y0, x1, y1, x2, y2)*f(x0, y0, x1, y1, x3, y3) <= 0 && f(x2, y2, x3, y3, x0, y0)*f(x2, y2, x3, y3, x1, y1) <= 0) cout << "yes" << endl; else cout << "no" << endl; return 0; }

activex · Answer

Why all this stuff. .Its asking about two line segments, not two straight lines. ASsume the line segment as an X axis range (X1,X2) and the other one has an x axis rage of (X3,X4). Then if these two ranges do not overlap, then the two line segments don't intersect. If they do overlap, check if the Y axis ranges overlap or not. If they don't overlap, then the two line sgements don't intersect.  

So simply, if either the x axis range or the y axis range of both lines don't overlap, then the two lines don't intersect... otherwise, they intersect.. simple right? No slope or stuff..

@Anonymous · Answer

Wtf  if m1 = m2 the slopes are parallel, then it doesnt work.

Interview Candidate is right..I would just solve for each equation and check where if the equations  ever equal each other ( after seeing if slope is parallel)

donutello · Answer

Calculate formula for each line. Determine intersection point and then determine if each segment overlaps the intersection point. You have to special-case the situations where the slope is infinite (vertical line) and where the slopes of the lines are the same.

PrinceBoroujerdi · Answer

Here's the solution coded up.

bool DoesIntersect(line one, line two)
{
    float slopeOne = GetSlope(one);
    float slopeTwo = GetSlope(two);
    
    if (slopeOne == slopeTwo)
    {
        if (one.x1 == one.x2)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
        
    float yInterceptOne = one.y1 - slopeOne*one.x1;
    float yInterceptTwo = two.y1 - slopOne*two.y1;
    
    float xIntersection = (yInterceptTwo - yInterceptOne)/(slopOne - slopeTwo);
    
    float minPointOne, maxPointOne;
    GetMinAndMax(one.x1, one.x2, &minPointOne, &maxPointOne);
    float minPointTwo, maxPointTwo;
    GetMinAndMax(two.x1, two.x2, &minPointTwo, &maxPointTwo);    
    
    if ((xIntersection >= minPointOne && xInterSection = minPointTwo && xIntersection <= maxPointTwo))
    {
        return true;    
    }
    else
    {
        return false;    
    }
}

float GetSlope(line theLine)
{
    if (theLine.x1 == theLine.x2)
    {
        slope = 0;
    }
    else
    {
        slope = (theLine.y1 - theLine.y2)/(theLine.x1 - theLine.x2);
    }
    return slopeOne;
}

void GetMinAndMax(float one, float two, float* min, float* max)
{
    if (one <= two)
    {
        *min = one;
        *max = two;
    }
    else
    {
        *min = two;
        *max = one;    
    }
}

Anonymous · Answer

I check slope, if parallel then check y-intersect, and see if ends of one line segment are between the ends of the other. If not parallel then check if ends of one line are on different sides of the other.

However later I found that it will be much easier to use vector dot product. Maybe that's why I am rejected.

Anonymous · Answer

A linear line is represented as y=mx+b or just to distinct points in the space.
If the later case, assume the points are (x1, y1) and (x2, y2), then m=(y2-y1)/(x2-x1) and b can calculated easily.
So, to lines y=m1x+b1 and y=m2x+b2 are intersected if m1 equals to m2.

Meta

Meta interview question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches