how to detect whether two segments (in 3d space) intersect?

Question

only check，no need to find the point.
coordinate z is not = 0. The old questions in stack overflow are all for 2d. Thanks in advance

Answer 1

There are several ways to do line-line intersection test. The classic way is using linear algebra (i.e., solving a linear matrix system) but from software development point of view I like more the Geometric-Algebra way, in the form of Plucker Coordinates, which only requires to implement vector algebra operations (i.e., cross-product and dot-product) which are simpler to code than matrix operations for solving linear systems.

Vector Algebra Solution

Given line segment P limited by points P1 and P2 and line segment Q limited by points Q1 and Q2.

The parametric form of the lines is given by:

P(t) = P1 + t (P2 - P1)

Q(t) = Q1 + t (Q2 - Q1)

Where t is a real number in the interval [0 1].

If two lines intersect then the following equation holds:

P(t0) = Q(t1)

Provided that the two unknown numbers t0 and t1 exist. Expanding the above equation we get:

t0 (P2 - P1) - t1 (Q2 - Q1) = Q1 - P1

To avoid dealing with matrix algebra we can try to solve the system using vector algebra and substitution method:

t0 (P2 - P1) - t1 (Q2 - Q1) = Q1 - P1

t0 = a + t1 b

t1 = C • (Q1 - (1 - a) P1 - a P2) / |C|^2

Where:

a = (P2 - P1) • (Q1 - P1) / |P2 - P1|^2

b = (P2 - P1) • (Q2 - Q1) / |P2 - P1|^2

C = b (P2 - P1) - (Q2 - Q1)

Where (•) is the dot-product. The intersection point P(t0) (or Q(t1)) exist if t0 and t1 are both in the interval [0 1].

Plucker Coordinates way

Given line segment P limited by points P1 and P2 and line segment Q limited by points Q1 and Q2.

The Plucker Coordinates of line P is given by a pair of 3d vectors (Pd, Pm):

Pd = P2 - P1

Pm = P1 × P2

Where Pm is the cross-product of P1 and P2. The Plucker Coordinates (Qd, Qm) of line Q can be calculated in exactly the same way.

The lines P and Q only can intersect if they are coplanar. The lines P and Q are coplanar iif:

Pd • Qm + Qd • Pm = 0

Where (•) is the dot-product. Since machines have finite precision a robust test should check not for zero but for a small number. If Pd × Qd = 0 then lines are parallel (here 0 is the zero vector). Again a robust test should be for instamce that the squared length of (Pd × Qd) is small.

If the lines are not parallel then they are coplanar and their intersection (called "meet" in Plucker's jargon) will be the point:

x = ((Pm • N) Qd - (Qm • N) Pd - (Pm • Qd) N) / (Pd × Qd) • N

Where N is any coordinate axis vector (i.e., (1,0,0) or (0,1,0) or (0,0,1)), such that (Pd × Qd) • N is non-zero.

If the neither P nor Q pass through the origin, then their Plucker coordinates Pm and Qm respectively will be non-zero and the following sinpler formula will work

x = Pm × Qm / Pd • Qm

For an introduction to Plucker Coordinates see:

https://en.m.wikipedia.org/wiki/Plücker_coordinates

http://www.realtimerendering.com/resources/RTNews/html/rtnv11n1.html#art3

For a general intersection formula see "Corollary 6" of:

http://web.cs.iastate.edu/~cs577/handouts/plucker-coordinates.pdf

Linear Algebra Way

Given line segment P limited by points P1 and P2 and line segment Q limited by points Q1 and Q2.

The parametric form of the lines is given by:

P(t) = P1 + t (P2 - P1)

Q(t) = Q1 + t (Q2 - Q1)

Where t is a real number in the interval [0 1].

If two lines intersect then the following equation holds:

P(t0) = Q(t1)

Provided that the two unknown numbers t0 and t1 exist. Expanding the above equation we get:

t0 (P2 - P1) - t1 (Q2 - Q1) = Q1 - P1

We can solve for t0 and t1 by expressing the above equation in matrix algebra:

A x = B

Where A is a 3x2 matrix with coordinates of vector (P2 - P1) in the first column and coordinates of the vector (Q2 - Q1) in the second column; x is a 2x1 column vector of unknowns t0 and t1 and B is a 3x1column vector with coordinates of vector (Q1 - P1).

Classically the system can be solved calculating the pseudo-inverse of matrix A, denoted by A^+:

A^+ = (A^T A)^-1 A^T

See: https://en.m.wikipedia.org/wiki/Generalized_inverse

Fortunately any matrix package in Python should be able to compute the above calculations very easily and perhaps very efficiently too.

If multiplying A with its pseudo-inverse A^+ is equal to the identity matrix I, i.e., (A A^+) == I, then there IS a unique answer (intersection) and you can get it computing the following product:

x = A^+ B

Of course if you cannot compute the pseudo-inverse in the first place, e.g., because (A^T A) is singular (i.e. determinant is zero), then no intersection exists.

Since we are dealing with segments, the intersection point is at point P(x0) or Q(x1) iff x0 and x1 are both in the interval [0 1].

Answer 2

I can tell you about the maths you can use(although it's a bit complicated). You write the equation for each line in parametric form. Then find the parameters for each line. See example below:

(a1,a2,a3)________________(b1,b2,b3)
A                           B 


and second line 
(c1,c2,c3)________________(d1,d2,d3)
C                            D

So equation would be A+t(B-A) for first line(this represents actually a point on line segment for t between 0 and 1) and C+s(D-C) for second line Where t and s are parameters Whose value should be between 0 and 1 for point to lie on line segment. (0is A, 1 is B) Here A means(a1,a2,a3) So you can equate the two equation for point of intersection (if any) and find a t and s which satisfies the three equations:

  a1+t(b1-a1)=c1+s(d1-c1)
  a2+t(b2-a2)=c2+s(d2-c2)
  a3+t(b3-a3)=c3+s(d3-c3)

The t and s should lie between 0 and 1 for the point to be really on the line segment. So I hope you got it:) Code:

#input a1,a2,a3 and all the other components here. 

#define all constants required for solving t and s
A=b1-a1
B=c1-d1
C=c1-a1
D=b2-a2
E=c2-d2
F=c2-a2

#find t and s using formula
t=(C*E-F*B)/(E*A-B*D)
s=(D*C-A*F)/(D*B-A*E)

#check if third equation is also satisfied(we have 3 equations and 2 variable
if ((t*(b3-a3)+s*(c3-d3))==c3-a3):
    if(0<=t<=1 and 0<=s<=1):
       print('line segments intersect')
    else:
       print ('line segments intersect on being produced')

This is the code segment .hope you finally got it:)