如何检测两条线段相交的位置？ [关闭]

如何确定两条线是否相交，如果相交，则在什么 x,y 点相交？

There’s a nice approach to this problem that uses vector cross products. Define the 2-dimensional vector cross product v × w to be v_x w_y − v_y w_x.

假设两条线段从p to p + r和来自q to q + s。那么第一条线上的任意点都可以表示为p + t r（对于标量参数t) 和第二行上的任意点为q + u s（对于标量参数u).

如果我们能找到两条线相交t and u这样：

p + t r = q + u s

两边交叉用s，得到

(p + t r) × s = (q + u s) × s

自从s × s= 0，这意味着

t (r × s) = (q − p) × s

因此，求解t:

t = (q − p) × s / (r × s)

同理，我们可以解出u:

(p + t r) × r = (q + u s) × r

u (s × r) = (p − q) × r

u = (p − q) × r / (s × r)

为了减少计算步骤的数量，可以方便地将其重写如下（记住s × r = − r × s):

u = (q − p) × r / (r × s)

现在有四种情况：

1. If r × s= 0 和 (q − p) × r= 0，则两条线共线。

   在这种情况下，表示第二段的端点 (q and q + s）根据第一条线段的方程（p + t r):

   t₀ = (q − p) · r / (r · r)

   t₁ = (q + s − p) · r / (r · r) = t₀ + s · r / (r · r)

   If the interval between t₀ and t₁ intersects the interval [0, 1] then the line segments are collinear and overlapping; otherwise they are collinear and disjoint.

   Note that if s and r point in opposite directions, then s · r < 0 and so the interval to be checked is [t₁, t₀] rather than [t₀, t₁].

2. If r × s= 0 和 (q − p) × r≠ 0，则两条线平行且不相交。

3. If r × s≠ 0 且 0 ≤t≤ 1 和 0 ≤u≤ 1，两条线段相交于点p + t r = q + u s.

4. 否则，两条线段不平行但不相交。

图片来源：该方法是 3D 线相交算法的 2 维特化，摘自 Ronald Goldman 发表的文章“三空间中两条线的相交”，发表于图形宝石，第 304 页。在三维空间中，通常的情况是线是倾斜的（既不平行也不相交），在这种情况下，该方法给出两条线最接近的点。