19

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

oligofren
  • 20,744
  • 16
  • 93
  • 180
trrrrrrm
  • 11,362
  • 25
  • 85
  • 130
  • 1
    are you referrring to geometric lines (which extend infinitely)? – likeitlikeit May 02 '13 at 08:41
  • @ra_htial: we are having a discussion about what you are really asking. please see the discussion under Andreas Wederbrand's answer. If my edit does not reflect your intentions, please re-edit it. Is your question about Java's java.awt.geom.Line2D (which according to the docs "represents a line segment in (x,y) coordinate space") or geometrical lines extending into infinity? – oligofren May 02 '13 at 09:37
  • @ra_htial: could you accept an answer or bring something to the discussion on what you are asking? – oligofren Jun 07 '13 at 07:49

2 Answers2

27

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.

oligofren
  • 20,744
  • 16
  • 93
  • 180
  • Sorry, I don't get what you are asking. What is after the intersection point? – oligofren Sep 06 '13 at 12:37
  • 2
    I assume he means he also wanted to know where the segments intersected. Btw, is there a way I can exclude the endpoints of the lines, st. `(0,0,1,1)` and `(1,1,2,2)` don't intersect? – Thomas Ahle Oct 10 '13 at 14:24
  • @AlessioMTX That is another question. I would start by trying to read the API methods ... – oligofren Sep 26 '16 at 14:43
  • I didn't find in Line2D and since I didn't know this API, I took a look, but I found no solution, so asked here, maybe I missed. – Mitro Sep 26 '16 at 14:44
  • 1
    @AlessioMTX First hit on google: http://stackoverflow.com/questions/16314069/calculation-of-intersections-between-line-segments – oligofren Sep 26 '16 at 14:45
  • What if I want to find out if a line segment cuts infinite line? For instance I have line y = x and a point (2,3) and want to find out whether they intersect or not. Line y = x is not defined with two points, instead, it's defined with a formula – Strahinja Jan 10 '18 at 12:18
  • That's another question worthy of a separate post, but you can probably make it work by converting the line into a segment using the max and min values of Long or something like that. – oligofren Jan 10 '18 at 14:34
9

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

JB Nizet
  • 678,734
  • 91
  • 1,224
  • 1,255
  • the same goes here, linesIntersect checks the lines not the segments. And there are a lot of cases where lines intersect but not the segments – anvarik May 02 '13 at 09:42
  • 5
    The javadoc says: Tests if the line **segment** from (x1,y1) to (x2,y2) intersects the line **segment** from (x3,y3) to (x4,y4) (emphasis mine). – JB Nizet May 02 '13 at 09:44
  • holy mother of potato :) my bad, one up vote is going for you guys – anvarik May 02 '13 at 09:46