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

问题描述

如何确定两条线是否相交，并且如果他们确实在x，y指向哪个点？

解决方案

>对于使用向量交叉产品的这个问题有一个很好的方法。定义二维向量叉乘积 v × w 为 v _x w _y - v _y w _x 。

假设两条线段从 p 运行到 p + r 和 q 到 q + s 。那么第一行的任何一点都可以表示为 p + t r （对于标量参数 t ）和第二行的任何点都是 q + u s （对于标量参数 u ）。

如果我们可以找到 t 和 u 这样的话，那么两条线相交：

p + t r = q pngalt =交叉点公式>

用 s 交叉双方，得到

（ p + t r ）× s =（ q + u s ）× s g

自 s × s = 0， / p>

t （ r × s ）=（ p ） s

因此，解决 t ：

t =（ q - p ）× s /（ r × s ） b

以同样的方式，我们可以解决 u ：

（ p + t r ）× r =（ （ s × r ）=（ p - q ）× r

u =（ p - q ）r /（ s × r ）

为了减少计算步骤的数量，可以很方便地将其重写为（记住 s × r = r × s ）：

u =（ q p ）× r /（ r × s blockquote>

现在有四种情况：

1. 如果 r x s = 0和（ q p ）× r = 0，在这种情况下，表达第二部分的端点（ q 和 q + p + t r ）： b
   $ b < blockquote>
   

   t ₀ =（ q - p ）r /（ r r ）

   1 =（ q + s - p ） / strong> r ）= t ₀ + s r r ）
   
   

/ em> ₀ 和 t ₁ 与区间[0，1]相交，则线段共线并重叠;如果 s 和 r 指向相反的方向，则 > s · r < 0，所以要检查的时间间隔是[ t ₁ ， t ₀ ]，而不是[ 如果 r s = 0且 q p × ≠ 0，那么这两条线是平行的并且是不相交的。 如果 r × s ≠ 0和0≤ ≤1且0≤ ≤1时，两条线段在 p + t r = q + u 。

否则，这两条线段并不平行，但不会相交。

方法是Ronald Goldman发表在图形宝石一书第304页的文章三维空间中两行相交的3D线交集算法的二维特化。在三尺寸，通常的情况是这些线是倾斜的（既不平行也不相交），在这种情况下，该方法给出两条线最接近的点。

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

解决方案

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.

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).

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

p + t r = q + u s

Cross both sides with s, getting

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

And since s × s = 0, this means

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

And therefore, solving for t:

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

In the same way, we can solve for u:

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

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

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

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)

Now there are four cases:

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

   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 + 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 and (q − p) × r ≠ 0, then the two lines are parallel and non-intersecting.

3. 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.

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

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屋！