Line and a Line segment intersection

Does anybody know how to check whether a given line (y=mx+c) intersects with a line segment denoted by end points P1 (x1, y1) and P2(x2, y2)?

Answer 1

[Teja Muppirala]

Define

t = (c - y1 + m*x1)/(y2 - y1 + m*(x1 - x2))

• If 0 <= t <= 1, then they intersect at exactly one point.
• If t < 0 or t > 1, they do not intersect.
• If t is NaN, then the line segment is right on top of line and they intersect at an infinite number of points.

How can you derive this result?

Well, first parameterize the line segment by a parameter T.

x = x1+(x2-x1)*T

y = y1+(y2-y1)*T

The line segment goes from T = 0 --> 1. Assume the line segment intersects the line y=mx+c as some time t.

Then [y1+(y2-y1)*t] = m*[x1+(x2-x1)*t] + c

Solving for t (using MATLAB to do the symbolic math of course)

t = solve('(y1+(y2-y1)*t) - m*(x1+(x2-x1)*t) + c','t')

you obtain the expression above. If t is outside the range [0, 1] then the lines do not intersect.

[Devinya Herath]

Thanks a lot