How do you detect where two line segments intersect?

Question

How do I determine whether or not two lines intersect, and if they do, at what x,y point?

Answer 1

There’s a nice approach to this problem that uses vector cross products. Define the 2-dimensional vector cross product v × w to be v_x w_y − v_y w_x.

Suppose the two line segments run from p to p + r and from q to q + s. Then any point on the first line is representable as p + t r (for a scalar parameter t) and any point on the second line as q + u s (for a scalar parameter u).

The two lines intersect if we can find t and u such that:

p + t r = q + u s

Cross both sides with s, getting

(p + t r) × s = (q + u s) × s

And since s × s = 0, this means

t (r × s) = (q − p) × s

And therefore, solving for t:

t = (q − p) × s / (r × s)

In the same way, we can solve for u:

(p + t r) × r = (q + u s) × r

u (s × r) = (p − q) × r

u = (p − q) × r / (s × r)

To reduce the number of computation steps, it's convenient to rewrite this as follows (remembering that s × r = − r × s):

u = (q − p) × r / (r × s)

Now there are four cases:

1. If r × s = 0 and (q − p) × r = 0, then the two lines are collinear.

   In this case, express the endpoints of the second segment (q and q + s) in terms of the equation of the first line segment (p + t r):

   t₀ = (q − p) · r / (r · r)

   t₁ = (q + s − p) · r / (r · r) = t₀ + s · r / (r · r)

   If the interval between t₀ and t₁ intersects the interval [0, 1] then the line segments are collinear and overlapping; otherwise they are collinear and disjoint.

   Note that if s and r point in opposite directions, then s · r < 0 and so the interval to be checked is [t₁, t₀] rather than [t₀, t₁].

2. If r × s = 0 and (q − p) × r ≠ 0, then the two lines are parallel and non-intersecting.

3. If r × s ≠ 0 and 0 ≤ t ≤ 1 and 0 ≤ u ≤ 1, the two line segments meet at the point p + t r = q + u s.

4. Otherwise, the two line segments are not parallel but do not intersect.

Credit: this method is the 2-dimensional specialization of the 3D line intersection algorithm from the article "Intersection of two lines in three-space" by Ronald Goldman, published in Graphics Gems, page 304. In three dimensions, the usual case is that the lines are skew (neither parallel nor intersecting) in which case the method gives the points of closest approach of the two lines.