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

how determine whether or not 2 lines intersect, , if do, @ x,y point?

there’s nice approach problem uses vector cross products. define 2-dimensional vector cross product v × w v_x w_y − v_y w_x.

suppose 2 line segments run p p + r , q q + s. point on first line representable p + t r (for scalar parameter t) , point on second line q + u s (for scalar parameter u).

the 2 lines intersect if can find t , u such that:

p + t r = q + u s

cross both sides s, getting

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

and since s × s = 0, means

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

and therefore, solving t:

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

in same way, can solve u:

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

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

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

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

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

now there 4 cases:

1. if r × s = 0 , (q − p) × r = 0, 2 lines collinear.

   in case, express endpoints of second segment (q , q + s) in terms of equation of 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 interval between t₀ , t₁ intersects interval [0, 1] line segments collinear , overlapping; otherwise collinear , disjoint.

   note if s , r point in opposite directions, s · r < 0 , interval checked [t₁, t₀] rather [t₀, t₁].

2. if r × s = 0 , (q − p) × r ≠ 0, 2 lines parallel , non-intersecting.

3. if r × s ≠ 0 , 0 ≤ t ≤ 1 , 0 ≤ u ≤ 1, 2 line segments meet @ point p + t r = q + u s.

4. otherwise, 2 line segments not parallel not intersect.

credit: method 2-dimensional specialization of 3d line intersection algorithm article "intersection of 2 lines in three-space" ronald goldman, published in graphics gems, page 304. in 3 dimensions, usual case lines skew (neither parallel nor intersecting) in case method gives points of closest approach of 2 lines.