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

Compute dot products d*(p1-p) and d*(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)

Answer 3

let p(x,y) and a its direction the line equation is D = a.x+b where b = y - a.x

let p1(x1,y1) and p2(x2,y2) a segment which equation is D' = a'.x+b' for any x in [x1;x2] where a' = (y2-y1)/(x2-x1) and b' = y2 - a'.x2 = y1 - a'.x1

you've got an intersection if there is an x between [x1;x2] for which D = D' thus if X = (b'-b)/(a-a') belong to [x1;x2] then Y = a.X+b = a'.X+b gives you the intersection point P(X,Y)

for instance :

let p(255,255), a = 1 => b = 0

let p1(60,179) and p2(168,54)

=> a' = -125/108

=> b' = 24596/99

=> X = (24596/99 - 0)/(1+125/108) = 115,1587983

=> Y = (24596/99 - 0)/(1+125/108) = 115,1587983

X is between 60 and 168 so there is an intersection point at P(X,Y)