I need to find the intersection point of 2 line segments (lines are finite, i.e., they have end points).

e.g. segment 1 from $(x_1, y_1)$ to $(x_2, y_2)$ -- segment 2 from $(x_3, y_3)$ to $(x_4, y_4)$

you can assume $m_1$ and $m_2$ are the gradients of segment 1 and segment 2 respectively

similarly, $c_1$ and $c_2$ being the y-intercepts of segment 1 and segment 2 respectively

Using $y=mx+c$ I can easily find the equations of both lines and then derive the intersection point from those equations and check if that point actually lies on both the line segments (intersection point may not lie between the end points).

My problem is when I calculate the gradients $m_1$ and $m_2$ I do $\frac{y_2-y_1}{x_2-x_1}$ there for if one of the lines is vertical then I am going to have problems. How can I deal with this?

Another problem is that if the two segments intersect at a point which is also the same as one of the end points then I want to assume that they are not intersecting.

e.g. if segment 1 is from $(2, 3)$ to $(3, 7)$ and segment 2 is from $(3, 7)$ to $(7, 3)$ then I want to assume they don't intersect.


migrated from stackoverflow.com Dec 9 '11 at 0:15

This question came from our site for professional and enthusiast programmers.


Instead of taking $x,y$ as the variables to solve for, write $(x,y)$ $= (x_1,y_1)+t(x_2-x_1,y_2-y_1) $ $= (x_3,y_3)+u(x_4-x_3,y_4-y_3)$ and solve for $t$ and $u$. Then it doesn't matter a bit whether your line segments are horizontal or vertical or whatever, and you can check for being within the segments just by looking at whether $0 < t < 1$ and $0 < u < 1$.

Note that if the line segments are parallel you'll get zero in your denominator, and if they're almost parallel you'll get something very small there; you may want to take care about that unless something in your setup guarantees that the line segments aren't close to being parallel.

  • $\begingroup$ I don't really understand what is actually being calculated by doing "(x,y) = (x1,y1)+t(x2-x1,y2-y1) = (x3,y3)+u(x4-x3,y4-y3)". Could you explain a bit more please? $\endgroup$ – temelm Mar 9 '11 at 20:34
  • $\begingroup$ Sure. (And I'm sorry I was too terse.) An arbitrary point on (x1,y1)..(x2,y2) is (x1,y1) plus some multiple of (x2-x1,y2-y1), the vector between them. That is, it has the form (x1,y1) + t(x2-x1,y2-y1). Or, if you prefer, (x1+t(x2-x1),y1+t(y2-y1)). t=0 is the point (x1,y1); t=1 is the point (x2,y2); the line segment (as opposed to the whole line) consists of all such points with 0 <= t <= 1. Similarly for the other line segment. Similarly for the other line segment, but I gave the parameter another name. [... to be continued] $\endgroup$ – Gareth McCaughan Mar 9 '11 at 22:33
  • $\begingroup$ [continuation of previous comment:] The point we're looking for is on both line segments, so it's equal to (x1,y1) + t(x2-x1,y2-y1) for some t and to (x3,y3) + u(x4-x3,y4-y3) for some u. Equating the two gives us two simultaneous equations in the variables t,u. Solving those gives us the intersection point. If the two line segments are parallel then the equations aren't independent and we either get no solutions (the lines are parallel) or infinitely many (they're actually the same line). $\endgroup$ – Gareth McCaughan Mar 9 '11 at 22:34
  • $\begingroup$ i see now, thanks a lot :) $\endgroup$ – temelm Mar 9 '11 at 22:58
  • $\begingroup$ How exactly do you solve for t & u in this equation? $\endgroup$ – imkendal Sep 27 '15 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy