2

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?

JumpingJezza
  • 5,498
  • 11
  • 67
  • 106
D. Neller
  • 21
  • 1
  • 4

1 Answers1

7

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)

MBo
  • 77,366
  • 5
  • 53
  • 86
  • I tried to implement it in c++ but i cant make it work – raaj Sep 03 '20 at 18:39
  • https://gist.github.com/soulslicer/26c4d6d36407e37c21cdf033c532a9ca – raaj Sep 03 '20 at 18:39
  • @raaj Wrong in the beginning: `DP(P[3]-P[0], P[4]-P[1], P[5]-P[2]);` and similar for DQ – MBo Sep 04 '20 at 02:10
  • In my code the vector P consits of the point and the vector. so P(0 to 2) is the point and P(3 to 5) is the normalized vector – raaj Sep 05 '20 at 20:33
  • Similar approach has been used many times. Look code [here](https://www.geometrictools.com/GTE/Samples/Distance/DistanceSegments3/DistanceSegments3Console.cpp), function `DistanceSegments3Console`. Or [here](http://geomalgorithms.com/a07-_distance.html). Substitute some simple points (0 0 0-1 0 0, 0 1 0-0 0 1) and check intermediate values – MBo Sep 06 '20 at 04:19
  • I suspect the sign of the discrimnant may be flipped in this code – Makogan Aug 11 '23 at 09:07
  • @Makogan What do you mean? – MBo Aug 11 '23 at 15:14
  • @MBo I tried this algorithm on a bunch of tests and it was consistently giving values for tt and uu that were in the opposite direciton of what I expected. once I did -dd instead of dd, things worked. – Makogan Aug 11 '23 at 20:19