问如何检测两个线段(在3d空间)是否相交？

EN

有几种方法可以进行线-线相交测试。经典的方法是使用线性代数(即解线性矩阵系统)，但从软件开发的角度来看，我更喜欢几何代数方法，以Plucker坐标的形式，它只需要实现向量代数运算(即叉积和点积)，这比解线性系统的矩阵运算更容易编码。

向量代数解

给定由点P1和P2限制的线段P和由点Q1和Q2限制的线段Q。

P(t0) = Q(t1)

假设存在两个未知数t0和t1。展开上面的等式，我们得到：

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

为了避免处理矩阵代数，我们可以尝试使用向量代数和代换方法来解决系统：

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

t0 =a+ t1 b

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

其中：

A= (P2 - P1)·(Q1 - P1) / |P2 - P1|^2

B= (P2 - P1)·(Q2 - Q1) / |P2 - P1|^2

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

如果t0和t1都在区间0 1内，则存在交点P(t0) (或Q(t1))。

Plucker坐标way

给定由点P1和P2限制的线段P和由点Q1和Q2限制的线段Q。

线P的Plucker坐标由一对3d矢量(Pd，Pm)给出：

Pd = P2 - P1

Pm = P1×P2

其中Pm是P1和P2的叉积。线Q的Plucker坐标(Qd，Qm)可以用完全相同的方式计算。

Pd·Qm + Qd·Pm =0

如果Pd×Qd =0，则直线是平行的(这里0是零向量)。同样，对于(Pd×Qd)的平方长度很小的情况，应该进行稳健的检验。

如果两条线不平行，则它们是共面的，它们的交点(在Plucker的行话中称为“相交”)将是点：

X= ((Pm·N) Qd - (Qm·N) Pd - (Pm·Qd) N) / (Pd×Qd)·N

其中N是任意坐标轴向量(即，(1,0,0)或(0,1,0)或(0,0,1))，使得(Pd×Qd)·N不为零。

如果P和Q都不通过原点，则它们的Plucker坐标Pm和Qm将分别为非零，并且以下正弦公式将起作用

X= Pm×Qm / Pd·Qm

有关Plucker坐标的介绍，请参见：

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

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

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

线性代数方法

给定由点P1和P2限制的线段P和由点Q1和Q2限制的线段Q。

其中t是区间0- 1中的实数。

如果两条直线相交，则以下等式成立：

P(t0) = Q(t1)

展开上面的等式，我们得到：

我们可以通过在矩阵代数中表示上面的方程来求解t0和t1：

A x=B

其中A是3x2矩阵，向量坐标(P2 - P1)在第一列，向量坐标(Q2 - Q1)在第二列；x是未知数t0和t1的2x1列向量，B是坐标为向量(Q1 - P1)的3x1列向量。

经典地讲，该系统可以通过计算矩阵A的伪逆来解决，用A^+表示：

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

请参阅：https://en.m.wikipedia.org/wiki/Generalized_inverse

幸运的是，Python中的任何矩阵包都应该能够非常容易地计算上述计算，而且可能也非常高效。

如果将A与其伪逆交集相乘等于单位矩阵I，即(A A^+) == I，则存在唯一的答案(交集)，并且您可以通过计算以下乘积来获得它：

X= A^+ B

当然，如果你一开始就不能计算伪逆，例如，因为(A^T A)是奇异的(即行列式是零)，那么就不存在交集。

由于我们处理的是线段，因此交点位于点P( x0 )或Q( x1 )当且仅当x0和x1都在区间0 1内。

我可以告诉你你可以使用的数学(尽管它有点复杂)。您可以以参数形式为每一行编写方程式。然后找到每一行的参数。如下例所示：

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


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

因此，对于第一条线，方程应该是A+t(B-A) (这实际上表示t在0和1之间的线段上的一个点)，对于第二条线，C+s(D-C)，其中t和s是参数，对于要位于线段上的点，其值应该在0和1之间。(0是A，1是B)这里A表示(a1，a2，a3)，因此您可以将交点(如果有)的两个方程相等，并找到满足这三个方程的t和s：

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

T和s应介于0和1之间，才能使点真正位于线段上。所以我希望你得到它：)代码：

#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')

这是你最终得到的代码段.hope：)