3D lines intersection algorithm

Question

I have line direction using x,y,z

and two points A, B , I used line segment using B- A

how to get the intersection point between them

Best regards

convert your lines into systems of linear equations, then combine them and solve the resulting system — Zruty
– Zruty, Commented Aug 10, 2011 at 11:58
what if the lines do not intersect at all? This is very likely situation with 1D lines in 3D. — Tomas
– Tomas, Commented Aug 10, 2011 at 12:00
Does the first line go through the origin, as you only have a direction? — Christian Rau
– Christian Rau, Commented Aug 10, 2011 at 12:03
If you try and state the problem properly, you might actually solve it by yourself easily. — Indy9000
– Indy9000, Commented Aug 10, 2011 at 12:10

Ricky Bobby · Accepted Answer · 2011-08-11 08:19:47Z

8

Sytem of equations:

The parametrice equation of a line with direction (a,b,c) and one point X(x1,x2,x3) is :

D1:(x, y, z) = (x1, y1, z1) + t1(a, b, c)

The parametrice equation of a line with 2 points A and B is :

 D2:(x, y, z) = (xa, ya, za) + t2(xb-xa, yb-ya, zb-za)

you just need to equalize D1 and D2 to get the result finding the parameter t1 and t2 that will work. (3 equations with 2 unknown)

If there is no solution there is no intersection.

Intersection with the segment only:

Now let M be you result you just need to verify :

t2 in [0,1] 

 or  0<AM.AB<||AB||^2 (M is in the segment AB)

remark:

If the representation of your line are from cartesian equations (intersection of plans) than the problem is the same but with 4 equations an 3 unknown

Example:

A (1,1,1)
B (0,0,0)
D2:(x,y,z)=(1-t2,1-t2,1-t2)

(a,b,c)=(1.-1.1)
(x1,y1,z1)=(1,0,1)
D1:(x,y,z)=(t1+1,-t1,1+t1)

(D1 and D2 are 2 diagonals of the cube of side =1 placed on 0,0,0)

let M(x,y,z) be the intersection D1, D2

we find t1 and t2 that equalize the above equation: D1 and D2

we get easily t1=-1/2 and t2=1/2

moreover t2 is in [0,1] so the resulting intersection is in [A,B]

M(1/2,1/2,1/2) =D1(t1)=D2(t2) is the solution

edited Aug 11, 2011 at 8:19

answered Aug 10, 2011 at 12:08

Ricky Bobby

7,6488 gold badges51 silver badges65 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Christian Rau Over a year ago

You know you've written the equation of a plane in 3D, as there are infinitely many n orthogonal to AB.

Ricky Bobby Over a year ago

Aha sorry, yep I will correct it. parametric equation of a line is: (x, y, z) = (x1, y1, z1,) + t(a, b, c) where a,b,c is the directional vector

AMH Over a year ago

could u give me more details, I couldn't understand that, I have the line direction as vector , x , y, z componenet

Ricky Bobby Over a year ago

@AMH , ok corrected, the idea is the same. Sorry for the mistake

Christian Rau Over a year ago

@Ricky Seems correct now. By the way, for the segment check you can also test if t2 is in [0,1].

|

Collectives™ on Stack Overflow

3D lines intersection algorithm

1 Answer 1

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related