Line and Line Segment intersection

Question

How can I detect whether a line (direction d and -d from point p) and a line segment (between points p1 and p2) intersects in 2D? If they do, how can I get their intersection point.

There are lots of example how to detect whether two line segments intersects but this should be even simpler case.

I found this but I do not understand what is a side-operator: http://www.loria.fr/~lazard//ARC-Visi3D/Pant-project/files/Line_Segment_Line.html

Answer 1

If this is a 2D task (the line and the segment lie in the same plane and they are specified by 2-dimensional coordinates), it's easy.

Construct a vector that is normal to d (the direction of the line) called n.

Compute dot products n.(p1-p) and n.(p2-p). If they have the same sign, there's no intersection. If they have opposite signs, there is an intersection. With a little bit of thought, you can figure out how to compute the location of the intersection in terms of p, p1-p and p2-p.

Answer 2

You can simply check if two lines (your line, and a line segment line) intersects and evaluate the intersection point.

line 1: (x,y)(t) = p + t*d; line 2: (x,y)(t) = p1 + k*(p2 - p1)

At the intersection point: p + t*d = p1 + k*(p2 - p1) - two equations (per x and per y)

From that equations you can simply find k and t parameters. If 0 < k < 1 the intersection point is in (p1, p2)

If you know k or t you can simply compute the intersection point from (x,y)(t) = p + t*d or (x,y)(t) = p1 + k*(p2 - p1)