两条移动线段（或一条移动线段和一个点）的交集

Question

我试图设计一个具有连续碰撞检测的2D物理引擎。对象存储为非旋转线段列表。因此，我可以通过查找任意两个对象之间每对线段之间的碰撞时间来检测碰撞。

我想找到两个移动的线段以相同的方向移动的交点之间的交点的确切时间确切的，这证明是困难的。

我发现我可以通过查找线段上每个点与另一个线段（反之亦然）之间的碰撞时间来进一步简化问题。这可能是计算效率低下的问题，因此两条线段的一般解决方案将是理想的答案。我也可以忽略线条平行的情况（我想将线条/点与“无碰撞”共享相同的位置和速度）。

如果答案是“不可能”到正好找到这个交点时间，我会接受它作为一个解决方案。任何有关这个问题的帮助将不胜感激。

编辑：根据维基百科的上一个Line segment文章，与端点A = (a_x, a_y)和C = (c_x, c_y)，为线段的一般公式线段看起来是这样的：

对于线 - 段 - 点相交，将代替

• p_x + p_v * t对于a_x（左侧o NLY，右侧就是p_x）
• p_y + p_v * t为a_y（左侧只，右侧就是p_y）
• q_x + q_v * t为c_x（仅左侧，右侧就是q_x）
• q_y + q_v * t为c_y（左侧只，右侧就是q_y）
• r_x + r_v * t为x
• r_y + r_v * t为y

的线段PQ [(p_x, p_y), (q_x, q_y)]，点R (r_x, r_y)，在p_v == q_v的速度移动！= r_v有解对于t？下面是完整的方程：

Answer 1

上面的公式不正确，因为它对x和y分量都使用相同的速度。由于速度是恒定的，所以我可以简化方程，使点参考线段移动。用于速度的变量的数量大大减少，对于每个线段的速度，点r和0的速度使用v = r_v - qp_v。在随后插入变量的公式变为：

由于WolframAlpha的，方程式，然后求解T：

有趣的是，如果你分析这个，这是对称为3D。跨产品[x1, y1, 0]和[x2, y2, 0]是[0, 0, x1*y2 - y1*x2]。然后该公式转换为：

Answer 2

对于线段 - 交点，我可以找到，其中有一个碰撞的间隔（尽管此间隔比实际时间碰撞大）：

给定一个线段[p, q]在速度v移动，并且点r以速度w，direction(w) != direction(v)，定义三行L1 = [p, p+v], L2 = [q, q+v], L3 = [r, r+w]。令t1, t_p和t2, t_q分别为L1和L3之间的交叉点和L2和L3之间的交点。如果间隔[t1, t2]与[t_p, t_q]不互斥，则在这两个间隔的交集处存在交叉点（例如，[-1, 10]和[2, 20]之间的交集是[2, 10]）。如果这些时间间隔是相互排斥的，则不会发生碰撞。

此外，如果v和w的方向相同，但长度不相等，则可以找到确切的碰撞时间。当投影到[p, q]行时，让s为点r。如果此点位于线段[p, q]中，则时间为t1时发生碰撞，可通过将点r与点s之间的距离除以点r与线段[p, q]之间的相对速度来计算。

使用该时间间隔可以通过使用类似于二进制搜索的方法来比较段和点之间在特定时间的距离，从而得出时间的估计值。然而，这是非常低效的。