CODEWITHSUNDEEP
3dgeometryline-segment
D. Neller
D. Neller

Reputation: 21

Intersecting 3D line Segments

How do I determine whether or not two 3D line segments intersect given XYZ coordinates for the start and end points of each line? If they do intersect, at what XYZ?

I've only been able to find answers for 2D: How do you detect where two line segments intersect?

Upvotes: 2

Views: 3034

Answers (1)

MBo
MBo

Reputation: 80072

Let's starting points are P0, Q0, and ending points are P1, Q1.

Direction vectors
DP = P1 - P0
DQ = Q1 - Q0
start difference vector
PQ = Q0 - P0

Segment in parametric form:

P = P0 + t * DP
Q = Q0 + u * DQ

Find values

a = Dot(DP, DP)
b = Dot(DP, DQ)
c = Dot(DQ, DQ)
d = Dot(DP, PQ)
e = Dot(DQ, PQ)

Find discriminant

DD = a * c- b * b

If DD = 0, then segments are parallel, and consider special case of (partial) coincidence, else

Find parameters for the closest points on lines

tt = (b * e - c * d) / DD
uu = (a * e - b * d) / DD

If any parameter is out of range 0..1, then segments don't intersect, else

Find distance between points

 P(tt) = P0 + tt * DP
 Q(uu) = Q0 + uu * DQ
 Dist = Length(Q(uu) - P(tt))

If Dist is zero (or less than some small Epsilon value like 1.0E-12 due to numerical errors), then segments are intersect in this point P(tt)

Upvotes: 7

Related Questions