How can I check if two segments intersect?

Question

How can I check if 2 segments intersect?

I've the following data:

Segment1 [ {x1,y1}, {x2,y2} ]
Segment2 [ {x1,y1}, {x2,y2} ] 

I need to write a small algorithm in python to detect if the 2 lines are intersecting.

Update:

Answer 1

Calculate the intersection point of the lines laying on your segments (it means basically to solve a linear equation system), then check whether is it between the starting and ending points of your segments.

Answer 2

The equation of a line is:

f(x) = A*x + b = y

For a segment, it is exactly the same, except that x is included on an interval I.

If you have two segments, defined as follow:

Segment1 = {(X1, Y1), (X2, Y2)}
Segment2 = {(X3, Y3), (X4, Y4)}

The abcisse Xa of the potential point of intersection (Xa,Ya) must be contained in both interval I1 and I2, defined as follow :

I1 = [min(X1,X2), max(X1,X2)]
I2 = [min(X3,X4), max(X3,X4)]

And we could say that Xa is included into :

Ia = [max( min(X1,X2), min(X3,X4) ),
      min( max(X1,X2), max(X3,X4) )]

Now, we need to check that this interval Ia exists :

if (max(X1,X2) < min(X3,X4))
    return false; // There is no mutual abcisses

So, we have two line formula, and a mutual interval. Your line formulas are:

f1(x) = A1*x + b1 = y
f2(x) = A2*x + b2 = y

As we got two points by segment, we are able to determine A1, A2, b1 and b2:

A1 = (Y1-Y2)/(X1-X2) // Pay attention to not dividing by zero
A2 = (Y3-Y4)/(X3-X4) // Pay attention to not dividing by zero
b1 = Y1-A1*X1 = Y2-A1*X2
b2 = Y3-A2*X3 = Y4-A2*X4

If the segments are parallel, then A1 == A2 :

if (A1 == A2)
    return false; // Parallel segments

A point (Xa,Ya) standing on both line must verify both formulas f1 and f2:

Ya = A1 * Xa + b1
Ya = A2 * Xa + b2
A1 * Xa + b1 = A2 * Xa + b2
Xa = (b2 - b1) / (A1 - A2) // Once again, pay attention to not dividing by zero

The last thing to do is check that Xa is included into Ia:

if ( (Xa < max( min(X1,X2), min(X3,X4) )) ||
     (Xa > min( max(X1,X2), max(X3,X4) )) )
    return false; // intersection is out of bound
else
    return true;

In addition to this, you may check at startup that two of the four provided points are not equals to avoid all that testing.

Answer 3

if your data define line you just have to prove that they are not parallel. To do this you can compute

alpha = float(y2 - y1) / (x2 - x1).

If this coefficient is equal for both Line1 and Line2, it means the line are parallel. If not, it means they will intersect.

If they are parallel you then have to prove that they are not the same. For that, you compute

beta = y1 - alpha*x1

If beta is the same for Line1 and Line2,it means you line intersect as they are equal

If they are segment, you still have to compute alpha and beta as described above for each Line. Then you have to check that (beta1 - beta2) / (alpha1 - alpha2) is greater than Min(x1_line1, x2_line1) and less than Max(x1_line1, x2_line1)

Answer 4

I thought I'd contribute a nice Swift solution:

struct Pt {
    var x: Double
    var y: Double
}

struct LineSegment {
    var p1: Pt
    var p2: Pt
}

func doLineSegmentsIntersect(ls1: LineSegment, ls2: LineSegment) -> Bool {

    if (ls1.p2.x-ls1.p1.x == 0) { //handle vertical segment1
        if (ls2.p2.x-ls2.p1.x == 0) {
            //both lines are vertical and parallel
            return false
        }

        let x = ls1.p1.x

        let slope2 = (ls2.p2.y-ls2.p1.y)/(ls2.p2.x-ls2.p1.x)
        let c2 = ls2.p1.y-slope2*ls2.p1.x

        let y = x*slope2+c2 // y intersection point

        return (y > ls1.p1.y && x < ls1.p2.y) || (y > ls1.p2.y && y < ls1.p1.y) // check if y is between y1,y2 in segment1
    }

    if (ls2.p2.x-ls2.p1.x == 0) { //handle vertical segment2

        let x = ls2.p1.x

        let slope1 = (ls1.p2.y-ls1.p1.y)/(ls1.p2.x-ls1.p1.x)
        let c1 = ls1.p1.y-slope1*ls1.p1.x

        let y = x*slope1+c1 // y intersection point

        return (y > ls2.p1.y && x < ls2.p2.y) || (y > ls2.p2.y && y < ls2.p1.y) // validate that y is between y1,y2 in segment2

    }

    let slope1 = (ls1.p2.y-ls1.p1.y)/(ls1.p2.x-ls1.p1.x)
    let slope2 = (ls2.p2.y-ls2.p1.y)/(ls2.p2.x-ls2.p1.x)

    if (slope1 == slope2) { //segments are parallel
        return false
    }

    let c1 = ls1.p1.y-slope1*ls1.p1.x
    let c2 = ls2.p1.y-slope2*ls2.p1.x

    let x = (c2-c1)/(slope1-slope2)

    return (((x > ls1.p1.x && x < ls1.p2.x) || (x > ls1.p2.x && x < ls1.p1.x)) &&
        ((x > ls2.p1.x && x < ls2.p2.x) || (x > ls2.p2.x && x < ls2.p1.x)))
    //validate that x is between x1,x2 in both segments

}

Answer 5

Here is C code to check if two points are on the opposite sides of the line segment. Using this code you can check if two segments intersect as well.

// true if points p1, p2 lie on the opposite sides of segment s1--s2
bool oppositeSide (Point2f s1, Point2f s2, Point2f p1, Point2f p2) {

//calculate normal to the segment
Point2f vec = s1-s2;
Point2f normal(vec.y, -vec.x); // no need to normalize

// vectors to the points
Point2f v1 = p1-s1;
Point2f v2 = p2-s1;

// compare signs of the projections of v1, v2 onto the normal
float proj1 = v1.dot(normal);
float proj2 = v2.dot(normal);
if (proj1==0 || proj2==0)
        cout<<"collinear points"<<endl;

return(SIGN(proj1) != SIGN(proj2));

}

Answer 6

Resolved but still why not with python... :)

def islineintersect(line1, line2):
    i1 = [min(line1[0][0], line1[1][0]), max(line1[0][0], line1[1][0])]
    i2 = [min(line2[0][0], line2[1][0]), max(line2[0][0], line2[1][0])]
    ia = [max(i1[0], i2[0]), min(i1[1], i2[1])]
    if max(line1[0][0], line1[1][0]) < min(line2[0][0], line2[1][0]):
        return False
    m1 = (line1[1][1] - line1[0][1]) * 1. / (line1[1][0] - line1[0][0]) * 1.
    m2 = (line2[1][1] - line2[0][1]) * 1. / (line2[1][0] - line2[0][0]) * 1.
    if m1 == m2:
        return False
    b1 = line1[0][1] - m1 * line1[0][0]
    b2 = line2[0][1] - m2 * line2[0][0]
    x1 = (b2 - b1) / (m1 - m2)
    if (x1 < max(i1[0], i2[0])) or (x1 > min(i1[1], i2[1])):
        return False
    return True

This:

print islineintersect([(15, 20), (100, 200)], [(210, 5), (23, 119)])

Output:

True

And this:

print islineintersect([(15, 20), (100, 200)], [(-1, -5), (-5, -5)])

Output:

False