How to check whether 2 lines segments intersect?

Question

How do I check whether 2 line segments, L1(p1,p2) and L2(p3,p4), intersect with each other? I do not need the intersection point, I just need to know whether they intersect or not. Since my application calculating this a lot, I need to find a fast solution.

Thanks

Answer 1

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.

Answer 2

I would simply use the method that does it for you, or look at its source code if you want to reimplement it: Line2D.linesIntersect()