Line and a Line segment intersection

Question

0 个投票

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)?

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

Answer 1

Teja Muppirala 2011-9-29

2 个投票

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 2011-9-29

Thanks a lot