Calculation of intersections between line segments

Question

There's a lot of questions about intersections between line segments here at stackowerflow and here is one more! Sorry, but I need help to understand how to calculate intersections. I have read several of the questions here and looked at several examples on other websites, but I'm still confused and don't get it! I don't like to copy and paste code without how things work.

So far I know that I'm going to compare the points of each line segments like Ax, Ay, Bx, By, Cx, Cy, Dx, Dy. Could someone explain for me what I'm going to calculate, what would the result of the calculating be if there is an intersection?

This is one of the example code I seen. I guess I don't need the intersecting point, just to know if the lines intersect or not.

   public static Point lineIntersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
  double denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
  if (denom == 0.0) { // Lines are parallel.
     return null;
  }
  double ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3))/denom;
  double ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3))/denom;
    if (ua >= 0.0f && ua <= 1.0f && ub >= 0.0f && ub <= 1.0f) {
        // Get the intersection point.
        return new Point((int) (x1 + ua*(x2 - x1)), (int) (y1 + ua*(y2 - y1)));
    }

  return null;
  }

Do I also need to calculate some median value like in this code example?

For lines through points (x0,y0) and (x1,y1), let xm = (x0+x1)/2, ym = (y0+y1)/2 (median of line segment). 
Then a = (y1-y0) and b = (x0-x1). 
If you evaluate c = a(x-xm)+b(y-ym), c=0 for (x,y) on the line, and the sign(c) tells you which side a point is on

Solution 1

The first piece of code you show is based on vector cross-product, which has been explained here How do you detect where two line segments intersect? in a great detail.

IMO, an easier way of understanding it is through solving a system of equations. Firstly look at lines generally and then cut segments from them. Below I use notations for given segments ((x1, x2), (y1, y2)) and ((x3, x4), (y3, y4)).

1. Check if any of the lines is vertical (x1 == x2 or x3 == x4).

   a. If both are vertical and x1 != x3, then no intersection.

   b. If both are vertical and x1 == x3, check if (y1, y2) and (y3, y4) overlap.

   c. If only one is vertical (say, first one), then build the equation of the second line (as outlined below), find the point where two lines intersect (by substituting x1 into the equation of the second line) and check if this point is within both segments (similar to step 5).

   d. If not, proceed.

2. Use the points coordinates to build lines equations in form y = a*x + b (like here).

   a1 = (y2-y1)/(x2-x1)
   b1 = y1 - a1*x1 
   a2 = (y4-y3)/(x4-x3)
   b2 = y3 - a2*x3
   

3. Check if lines are parallel (same slope a). If yes, check if they have same intercept b. If yes, check if 1D segments (x1, x2) and (x3, x4) overlap. If yes, your segments do overlap. The case when lines are parallel can be ambiguous. If they overlap, you can consider it as an intersection (it even can be one point if their ends are touching), or not. Note: if you are working with floats it would be a bit trickier, I reckon you would want to ignore this. In case you have only integers checking if a1 = a2 is equivalent to:

   if((y2-y1)*(x4-x3) == (x2-x1)*(y4-y3))
   

4. If lines are not parallel. The point of intersection is equivalent to a solution of a system of equations representing the two lines. Really, y = a1*x + b1 and y = a2*x + b2 intersecting basically means that both of these equations hold. Solve this system by equating the two right sides and it will give you the intersection point. In fact, you need only x coordinate of the intersection (draw it and you'll see why):

   x0 = -(b1-b2)/(a1-a2)
   

5. Last step is to check if the intersection point x0 lies within both segments. That is, min(x1, x2) < x0 < max(x1, x2) and min(x3, x4) < x0 < max(x3, x4). If yes, your lines do intersect!

Solution 2

I really @sashkello's answer and find it to be more intuitive and easier to explain than the vector implementation. Particularly when adding this kind of code to a code base.

I'll caveat that with saying that you can make use of Java's Line2D helper method.

Line2D.linesIntersect(double x1, double y1,
                      double x2, double y2,
                      double x3, double y3,
                      double x4, double y4)

The only draw back is that it requires you to consider the segments to be intersecting even when they are just touching (on both end points and the line itself).

For example, the below lines are considered intersecting because they share point (1,1).

L1 = [(0,0),(1,1)]
L2 = [(1,1),(2,3)]

If that is a problem you can add 4 checks to see if the points are equal.

If you have concerns about a point falling on a point within the line, that takes a bit more work and you're maybe better off implementing it yourself so you can do the checks in the algorithm itself.

If none of those edge cases affect you, then Line2D.linesIntersectis for you. :)

Solution 3

public void fixData()
{
    slope = (p2.getY() - p1.getY()) / (p2.getX() - p1.getX());
    yInt = p1.getY() - slope * p1.getX();
    xInt = (-yInt) / slope;
}

Comments

[3D-kreativ]

Hmm, just another example. I have seen that before, but as with all other examples it's just like a foreign language! I guess my skill in math are a little bit limited, but I don't want that stop me from learning.

[3D-kreativ]

I have all my positions stored as points in an arraylist, and I need to pass them to a method that check if there is an intersection. But I don't know how to start? I guess I only need to check if the overlap!?

[3D-kreativ]

Some example code along with some explanation would be really preciated.

[3D-kreativ]

Thanks for the explanation and code example! I will try it later.

[tofarr]

A caveat with this - You need to check for the special case of vertical lines at the start of this method.

[sashkello]

@tofarr Thanks for spotting it. Edited answer to fix this.

[Atte Juvonen]

Here is a complete Java implementation of this solution: github.com/baobabKoodaa/CodeForcesLibrary/blob/…

[Jorrick Sleijster]

Because this does not solve the question. linesIntersect only returns whether they intersect and not the actual intersection point.

[Kenny Cason]

@JorrickSleijster thanks for the response! I did indeed misread the question.