兩條移動線段（或一條移動線段和一個點）的交集

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]之間的相對速度來計算。

使用該時間間隔可以通過使用類似於二進制搜索的方法來比較段和點之間在特定時間的距離，從而得出時間的估計值。然而，這是非常低效的。