您的问题可以转换为线性规划问题并准确解决。
首先,假设 (p0,p1,p2,p3) 是 t0 时刻的顶点,(q0,q1,q2,q3) 是第一个四面体在 t1 时刻的顶点,那么在 4d 时空中,它们填充以下 4d 封闭体积
V = { (r,t) | (r,t) = a0 (p0,t0) + … + a3 (p3,t0) + b0 (q0,t1) + … + b3 (q3,t1) }
这里 a0...a3 和 b0...b3 参数在区间 [0,1] 中并且总和为 1:
a0+a1+a2+a3+b0+b1+b2+b3=1
第二个四面体同样是一个凸多边形(在上面的所有内容中添加一个 ' 以定义 V' 移动四面体的 4d 体积。
现在两个凸多边形的交点就是一个凸多边形。第一次发生这种情况将满足以下线性规划问题:
如果 (p0,p1,p2,p3) 移动到 (q0,q1,q2,q3) 并且 (p0',p1',p2',p3') 移动到 (q0',q1',q2',q3')那么第一次相交发生在点/时间(r,t):
最小化 t0*(a0+a1+a2+a3)+t1*(b0+b1+b2+b3) 服从
0 <= ak <=1, 0<=bk <=1, 0 <= ak’ <=1, 0<=bk’ <=1, k=0..4
a0*(p0,t0) + … + a3*(p3,t0) + b0*(q0,t1) + … + b3*(q3,t1)
= a0’*(p0’,t0) + … + a3’*(p3’,t0) + b0’*(q0’,t1) + … + b3’*(q3’,t1)
最后一个实际上是 4 个方程,一个对应于 (r,t) 的每个维度。这是 16 个值 ak、bk、ak' 和 bk' 的总共 20 个线性约束。如果有解决方案,那么
(r,t)= a0*(p0,t0) + … + a3*(p3,t0) + b0*(q0,t1) + … + b3*(q3,t1)
是第一个交点。否则它们不会相交。