How to Check If Two Segments Intersect

How can I check if two segments intersect?

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) )) or
     (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.

How to check whether 2 lines segments intersect?

To test whether two line segments intersect, you can use Java's 2D API, specifically the methods of Line2D.

Line2D line1 = new Line2D.Float(100, 100, 200, 200);
Line2D line2 = new Line2D.Float(150, 150, 150, 200);
boolean result = line2.intersectsLine(line1);
System.out.println(result); // => true

// Also check out linesIntersect() if you do not need to construct the line objects
// It will probably be faster due to putting less pressure on the garbage collector
// if running it in a loop
System.out.println(Line2D.linesIntersect(100,100,200,200,150,150,150,200));

If you are interested in finding out how the code works, in order to see if you can make it faster in your specific domain, you can check out the code for OpenJDK implementation.
But remember, always profile before you optimize; it is probably plenty fast enough as it is.

Find out if 2 lines intersect

This is possible. We want to check whether both endpoins of l1 are on different sides of l2, and both endpoints of l2 are on opposite sides of l1.

To check on which side of l1=((A0, B0), (A1, B1)) a point (A, B) lies, we take:

• an arbitrary normal vector N perpendicular to the line; one such vector is (B1-B0, A1-A0)
• the vector P from the start of the line to the point (A, B), which is (A-A0, B-B0)

We then compute the dot product:

N · P = (A-A0, B-B0) · (B1-B0, A1-A0) = (A-A0) * (B1-B0) + (B-B0) * (A1-A0)

We're only interested in the sign: if it's positive, the point is on one side of the line; if it's negative, it's on the other. As you see, no floating point arithmetic required.

We can take advantage of the fact that numbers with opposite signs, when multiplied, always yield negative. So the full expression to determine whether two line segments ((A0, B0), (A1, B1)) and ((A2, B2), (A3, B3)) intersect is:

((A2-A0)*(B1-B0) - (B2-B0)*(A1-A0)) * ((A3-A0)*(B1-B0) - (B3-B0)*(A1-A0)) < 0
&&
((A0-A2)*(B3-B2) - (B0-B2)*(A3-A2)) * ((A1-A2)*(B3-B2) - (B1-B2)*(A3-A2)) < 0

Test Code

Some C++ code to test the above calculation:

#include <iostream>
#include <cstdlib>

struct Point {
    int x,y;
};

bool isIntersecting(Point& p1, Point& p2, Point& q1, Point& q2) {
    return (((q1.x-p1.x)*(p2.y-p1.y) - (q1.y-p1.y)*(p2.x-p1.x))
            * ((q2.x-p1.x)*(p2.y-p1.y) - (q2.y-p1.y)*(p2.x-p1.x)) < 0)
            &&
           (((p1.x-q1.x)*(q2.y-q1.y) - (p1.y-q1.y)*(q2.x-q1.x))
            * ((p2.x-q1.x)*(q2.y-q1.y) - (p2.y-q1.y)*(q2.x-q1.x)) < 0);
}

int main(int argc, char* argv[]) {
    if(argc != 9) {
        std::cout << "Call as " << argv[0] << " <p1.x> <p1.y> <p2.x> "
                  << "<p2.y> <q1.x> <q1.y> <q2.x> <q2.y>" << std::endl;
        return -1;
    }

    Point p1 = {.x = atoi(argv[1]), .y = atoi(argv[2])};
    Point p2 = {.x = atoi(argv[3]), .y = atoi(argv[4])};
    Point q1 = {.x = atoi(argv[5]), .y = atoi(argv[6])};
    Point q2 = {.x = atoi(argv[7]), .y = atoi(argv[8])};

    if(isIntersecting(p1,p2,q1,q2)) {
        std::cout << "Segments intersect" << std::endl;
        return 1;
    }
    else {
        std::cout << "Segments do not intersect" << std::endl;
        return 0;
    }
}

Results:

$ ./intersection_test 0 0 10 10 0 10 10 0 # example from the comments
Segments intersect
$ ./intersection_test 0 1 2 1 1 2 1 0
Segments intersect
$ ./intersection_test 0 0 0 1 1 1 1 0
Segments do not intersect
$ ./intersection_test 1 1 5 3 3 4 7 2 # q touches but not intersects at p2
Segments do not intersect                             
$ ./intersection_test 1 1 5 3 3 4 6 2
Segments intersect

---

Related Topics