CODEWITHSUNDEEP
mathgeometrylineintersection
bittersoon
bittersoon

Reputation: 403

Line and Line Segment intersection

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

Upvotes: 9

Views: 10949

Answers (4)

Mokhabadi
Mokhabadi

Reputation: 304

To detect the intersection, simply put p1 and p2 in the line equation. if the sign of values was not the same, they are on both sides of the line.

to find the intersection point, calculate the weighted average of p1 and p2 with the weight of previous values you calculated, swapped for p1 and p2 (absolute values albeit).

example: p=(3,2) d=(7,6) p1=(9,10) p2=(12,8)
line equation is ax+by+c=0
for a and b you can put (6,-7) so 6x-7y+c=0
to find c, put p in the line equation 6*3-7*2+c=0 so c=-4
so the line equation is 6x-7y-4=0
p1: 6*9-7*10-4=-20
p2: 6*12-7*8-4=12

so the line intersects that line segment because signs are not the same. to find the intersection point, get the weighted average with swapped absolute of calculated values:

pi=(p1*12+p2*20)/(12+20) = (10.875,8.75)

to verify your answer, put pi in the line equation:

6*10.875-7*8.75-4=0 ok!

so it is on the line. and also it is definitely on the line segment because it is a linear combination of p1 and p2. For more information refer to linear algebra books.

I explained as simply as I could.

Upvotes: 0

Eugene Smith
Eugene Smith

Reputation: 9398

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.

Upvotes: 7

hoang
hoang

Reputation: 1917

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)

Upvotes: 0

Andrew
Andrew

Reputation: 24846

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)

Upvotes: 7

Related Questions