geometry - How do you detect where two line segments intersect?

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

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.