Intersection of Line and Segment in Java

Question

Essentially I need to return a boolean if a line and a line segment intersect. For the line the information I have is the slope, xy coords for a random point, and xy for a y intercept. For the line segment I have the line segment and the two end point xy coordinates. Any ideas?

Answer 1

The line through (Xr, Yr) with slope S has equation D(X, Y):= (Y - Yr) - S (X - Xr) = 0.

Just check that D(Xa, Ya) and D(Xb, Yb) have opposite signs.

Answer 2

Implementing this is not terribly difficult, it's the conceptual part that seems the most difficult. I might code something up for this for fun later but this should be enough to get you started. Also, note that this is might be a really bad way to solve it (time/space wise) but it will definitely work.

If you want to find a good solution, use convert the line to vectors and use the implementation in the answer in the link below all my text.

1. Calculate the slope of the second line. If it's equal to the first, they're parallel and never intersect.
2. Calculate where the two lines would intersect if they do intersect. They can only intersect at one point. This is how you would check if they will intersect:
   • Find 2 distinct coordinates for each line at some arbitrary point.
   • Determine the distance between the two lines at each point.
   • Whichever point results in a smaller distance between the lines represents the direction you need to travel in to move closer to the intersection.
   • Keep checking the distance between the two lines until they start increasing (which means you need to reverse the direction again) or until the distance is 0. The xy coord at distance = 0 is the intersection.
3. If the x-value of the point where the two lines intersect is in between the two x-values for your line segment, the line and line fragment intersect.

This should be easier for you because you already have two xy coords for the first line and two end point coordinates for the line segment.

Check this answer out for a really nice solution with some examples in the comments: https://stackoverflow.com/a/565282/2142219