你如何检测两条线段相交的位置? [英] How do you detect where two line segments intersect?

问题描述

如何确定两条线是否相交，如果相交，在 x,y 点的什么位置?

How do I determine whether or not two lines intersect, and if they do, at what x,y point?

推荐答案

有一个很好的方法来解决这个问题，它使用向量叉积.将二维向量叉积 v × w 定义为 v_x w_y - v_y w_x.

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 到 p + r 和从 q 到 q + s.然后第一行上的任何点都可以表示为 p + t r(对于标量参数 t)和第二行上的任意点为 q + u s(对于标量参数 u).

Suppose the two line segments run from p to p + r and from q to q + s. Then any point on the first line is representable as p + t r (for a scalar parameter t) and any point on the second line as q + u s (for a scalar parameter u).

如果我们可以找到 t 和 u，那么两条线相交:

The two lines intersect if we can find t and u such that:

p + t r = q + u s

p + t r = q + u s

用s交叉两边，得到

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

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

由于 s × s = 0，这意味着

And since s × s = 0, this means

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

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

因此，求解t:

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

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

同理，我们可以解出u:

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

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

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

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

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

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

为了减少计算步骤的数量，将其重写如下(记住 s × r = - r × <强>s):

To reduce the number of computation steps, it's convenient to rewrite this as follows (remembering that s × r = − r × s):

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

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

现在有四种情况:

1. 如果 r × s = 0 且 (q − p) × r = 0，则两条线共线.

1. If r × s = 0 and (q − p) × r = 0, then the two lines are collinear.

在这种情况下，用第一段的方程表示第二段的端点(q 和 q + s)线段(p + t r):

In this case, express the endpoints of the second segment (q and q + s) in terms of the equation of the first line segment (p + t r):

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

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

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

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

如果 t₀ 和 t₁ 之间的区间与区间 [0, 1] 相交，则线段共线且重叠；否则它们是共线且不相交的.

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.

请注意，如果 s 和 r 指向相反的方向，则 s · r <0 因此要检查的间隔是 [t₁, t₀] 而不是 [t₀, t₁].

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₁].

如果 r × s = 0 且 (q − p) × r ≠ 0，则两条线平行且不相交.

If r × s = 0 and (q − p) × r ≠ 0, then the two lines are parallel and non-intersecting.

如果 r × s ≠ 0 和 0 ≤ t ≤ 1 和 0 ≤ u≤ 1，两条线段相交于p + t r = q + u s.

If r × s ≠ 0 and 0 ≤ t ≤ 1 and 0 ≤ u ≤ 1, the two line segments meet at the point p + t r = q + u s.

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

Otherwise, the two line segments are not parallel but do not intersect.

Credit:此方法是 Ronald Goldman 发表于 Graphics Gems 第 304 页的文章三空间中两条线的交点"中 3D 线相交算法的 2 维特化. 在三个维度中，通常的情况是线是倾斜的(既不平行也不相交)，在这种情况下，该方法给出了两条线最接近的点.

Credit: this method is the 2-dimensional specialization of the 3D line intersection algorithm from the article "Intersection of two lines in three-space" by Ronald Goldman, published in Graphics Gems, page 304. In three dimensions, the usual case is that the lines are skew (neither parallel nor intersecting) in which case the method gives the points of closest approach of the two lines.

这篇关于你如何检测两条线段相交的位置?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！