1
$\begingroup$

I am trying to code an algorithm in Scala, programming language. The program will return false if the line segment intersects in 3D: I don't need to find the point of the intersection even if they intersect.

The problem is that I am not able to find the step by step mathematical method for the line segments, most of them are for lines: lines might intersect at some point, but line segment, given the specific length might not intersect in the given band.

Given point A (Ax, Ay, Az), point B(Bx, By, Bz), point C(Cx, Cy, Cz), and point D(Dx,Dy,Dz), does AB intersect CD? (True or False)

$\endgroup$
  • $\begingroup$ I would find the intersection of the lines, then check if it lies on both segments. $\endgroup$ – saulspatz Feb 16 at 4:33
2
$\begingroup$

Points on the line through $A$ and $B$ have the form $tA + (1-t)B$ for various real numbers $t$. The point will be on the line segment connecting $A$ and $B$ if and only if $0 \le t \le 1$. All other points on the line will have either $t < 0$ or $t > 1$. Similarly, points on the line segment connecting $C$ and $D$ have form $sC + (1-s)D$ for $0\le s \le 1$.

The intersection of the two lines must have both forms, giving the equation $$tA + (1-t)B = sC + (1-s)D$$ This is actually three equations in the two unknowns $t$ and $s$:

$$t(A_x - B_x) + s(D_x - C_x) = D_x - B_x\\t(A_y - B_y) + s(D_y - C_y) = D_y - B_y\\t(A_z - B_z) + s(D_z - C_z) = D_z - B_z$$

If these three equations have a simultaneous solution for $t$ and $s$ (solve two of them, then check the solution in the third), then the two lines intersect. If the solution also satisfies $0 \le t \le 1, 0 \le s \le 1$, then the segments intersect.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.