确定两条射线是否相交

Question

我在一个二维平面上有两条射线，它们一直延伸到无穷远，但都有一个起点。它们都由起点和指向无穷远的矢量描述。我想知道这两条射线是否相交，但不需要知道它们相交的位置（这是碰撞检测算法的一部分）。

我查看了所有的资料，都是关于如何找到两条线或线段的交点。有没有快速算法可以解决这个问题？

- Faken

---

2D还是3D？如果是前者，只需检查并查看两者的斜率是否相同：如果相同，则它们要么平行，要么是同一条线。否则，它们将相交。 - fbrereto

这些是射线，不是直线，对吗？所有的直线在二维空间中都会相交，除非它们是平行的。 - Carl Norum

@fbereto：抱歉，是2D平面。已经修改以反映这一点。 - Faken

@Carl Norum：是的，你是对的。抱歉，你是正确的。 - Faken

乍一看，寻找一些矢量积和角度比较的花哨用法很诱人，但是请考虑计算这些积所需的计算，并查看Adam或Peter的解决方案。计算方程组的行列式几乎与计算矢量积相同。 - Maciej Hehl

Answer 1

很抱歉我不同意Peter Walser的答案。在我的桌子上解方程得到：

u = ((bs.y - as.y) * bd.x - (bs.x - as.x) * bd.y) / (bd.x * ad.y - bd.y * ad.x)
v = ((bs.y - as.y) * ad.x - (bs.x - as.x) * ad.y) / (bd.x * ad.y - bd.y * ad.x)

将公共项分离后，这变成了：

dx = bs.x - as.x
dy = bs.y - as.y
det = bd.x * ad.y - bd.y * ad.x
u = (dy * bd.x - dx * bd.y) / det
v = (dy * ad.x - dx * ad.y) / det

五次减法，六次乘法和两次除法。

如果您只需要知道射线是否相交，则u和v的符号就足够了，这两个除法可以替换为num * denom < 0或（sign(num) != sign(denom)），具体取决于目标计算机上哪个更有效率。

请注意，当det==0时的罕见情况意味着射线不相交（需要进行一次额外的比较）。

- Gunter Blache

---

对于那些对导数感到困惑的人，这里有一个链接：https://math.stackexchange.com/questions/2788943 - MarkWeston

链接已过期。 - WDC

小细节：对于 det==0 的情况，它可能意味着没有交点，也可能意味着输入的线段重叠。也许更准确的说法是“射线没有唯一的交点”。 - jwd

Answer 2

已知：两条射线a，b，起点（原始向量）为as，bs，方向向量为ad，bd。

当存在交点p时，这两条直线相交：

p = as + ad * u
p = bs + bd * v

如果这个方程组有一个u>=0且v>=0的解（正方向是使它们成为光线），那么这些光线会相交。

对于2D向量的x/y坐标，这意味着：

p.x = as.x + ad.x * u
p.y = as.y + ad.y * u
p.x = bs.x + bd.x * v
p.y = bs.y + bd.y * v

进一步的步骤：

as.x + ad.x * u = bs.x + bd.x * v
as.y + ad.y * u = bs.y + bd.y * v

解决v的问题：

v := (as.x + ad.x * u - bs.x) / bd.x

插入和解决 u：

as.y + ad.y * u = bs.y + bd.y * ((as.x + ad.x * u - bs.x) / bd.x) 
u := (as.y*bd.x + bd.y*bs.x - bs.y*bd.x - bd.y*as.x ) / (ad.x*bd.y - ad.y*bd.x)

计算u，然后计算v，如果两者均为正数，则射线相交，否则不相交。

- Peter Walser

---

你如何解出最后一个公式中的u？它包含了自身。 - ColacX

糟糕，我把“v”插入了错误的方程式中。现在已经修复了。 - Peter Walser

我知道这篇文章已经有些年头了，但我不确定为什么或者如何，但是当向量a和b被交换时，这个解决方案会导致不同的解决方案，特别是当解决方案本应该是v = 2时，却变成了1。我使用的点是：对于第一个向量(7.64475393f, 5.59931898f)，(6.30824f, 4.91833f)；对于第二个向量(6.43122959f, 7.98099709f)，(6.43122864f, 6.48099709f)。 - user975989

你如何从 as.y + ad.y * u = bs.y + bd.y * ((as.x + ad.x * u - bs.x) / bd.x) 推导出 u := (as.y*bd.x + bd.y*bs.x - bs.y*bd.x - bd.y*as.x ) / (ad.x*bd.y - ad.y*bd.x)？ - MarkWeston

Answer 3

一条射线可以由点集 A + Vt 表示，其中 A 是起始点，V 是指示射线方向的向量，t >= 0 是参数。因此，要确定两条射线是否相交，请执行以下操作：

bool DoRaysIntersect(Ray r1, Ray r2)
{
    // Solve the following equations for t1 and t2:
    //   r1.A.x + r1.V.x * t1 == r2.A.x + r2.V.x * t2
    //   r1.A.y + r1.V.y * t1 == r2.A.y + r2.V.y * t2
    if(no solution)  // (e.g. parallel lines)
    {
        if(r1 == r2)  // same ray?
            return true;
        else
            return false;  // parallel, non-intersecting
    }
    else  // unique solution
    {
        if(t1 >= 0 && t2 >= 0)
            return true;
        else
            return false;  // they would intersect if they are lines, but they are not lines
    }
}

- Adam Rosenfield

Answer 4

GeomAlgorithms.com有一些非常棒的处理3D线条的算法...但总的来说，在3D空间中，两条线相交的概率是非常低的。

在二维平面中，你需要检查斜率。如果斜率不相等，则它们相交。如果斜率相等，则它们相交，如果它们上的一个点具有相同的x坐标或y坐标。

- vicatcu

---

问题明确指出它仅限于2D。 - corsiKa

@glowcoder 在我最初回答时没有说明这一点，编辑了帖子以描述2D算法。 - vicatcu

@glowcoder：没关系，如果是3D的话，我只需要将所有z分量设为零并简化方程，它应该就能工作了。谢谢vicatcu，我会查看这个网站的。 - Faken

Answer 5

我在查找两条射线的交点时发现了这篇文章，基于其他答案。以防有人寻找相同的答案而来到这里，这里提供一份TypeScript / JavaScript的答案。

/**
 * Get the intersection of two rays, with origin points p0 and p1, and direction vectors n0 and n1.
 * @param p0 The origin point of the first ray
 * @param n0 The direction vector of the first ray
 * @param p1 The origin point of the second ray
 * @param n1 The direction vector of the second ray
 * @returns
 */
export function getRaysIntersection(
  p0: number[],
  n0: number[],
  p1: number[],
  n1: number[]
): number[] | undefined {
  const dx = p1[0] - p0[0];
  const dy = p1[1] - p0[1];
  const det = n1[0] * n0[1] - n1[1] * n0[0];
  const u = (dy * n1[0] - dx * n1[1]) / det;
  const v = (dy * n0[0] - dx * n0[1]) / det;
  if (u < 0 || v < 0) return undefined; // Might intersect as lines, but as rays.

  const m0 = n0[1] / n0[0];
  const m1 = n1[1] / n1[0];
  const b0 = p0[1] - m0 * p0[0];
  const b1 = p1[1] - m1 * p1[0];
  const x = (b1 - b0) / (m0 - m1);
  const y = m0 * x + b0;

  return Number.isFinite(x) ? [x, y] : undefined;
}

演示在这里：https://codesandbox.io/s/intersection-of-two-rays-mcwst

- Stephen Ruiz

---

当光线方向与轴对齐时，这将失败... - user2867288

Answer 6

线段由点p和向量v表示：

线段 = p + a * v（对于所有a）

射线是该线段的正半部分：

射线 = p + a * v（对于所有a≥0）

要确定两条线是否相交，请将它们设置为相等并解决：

交点出现在p₁ + a₁ * v₁ = p₂ + a₂ * v₂处
（请注意，有两个未知数a₁和a₂，以及两个方程，因为p和v是多维的）

解决a₁和a₂的值 - 如果它们都是非负数，它们相交。如果其中一个是负数，则它们不相交。

- BlueRaja - Danny Pflughoeft

Answer 7

c++ for Guntners solution

bool RaysIntersection(const Point& as, const Point& ad, const Point& bs, const Point& bd, Point& result)
{
    if (as == bs) {
        result = as;
        return true;
    }
    auto dx = bs.X - as.X;
    auto dy = bs.Y - as.Y;
    auto det = bd.X * ad.Y - bd.Y * ad.X;
    if (det != 0) { // near parallel line will yield noisy results
        double u = (dy * bd.X - dx * bd.Y) / (double)det;
        double v = (dy * ad.X - dx * ad.Y) / (double)det;
        if (u >= 0 && v >= 0) {
            result = as + ad * u;
            return true;
        }
    }
    return false;
}

- Yomi1984

Answer 8

我只想检查两条射线是否相交。我将通过计算从这两条射线创建的两个“三角形”的旋转方向来实现。虽然它们并不是真正的三角形，但从数学的角度来看，如果我只想计算三角形的旋转，我只需要两个具有共同起点的向量，其余部分并不重要。

第一个三角形将由两个向量和一个起点组成。起点将是第一条射线的起点。第一个向量将是第一条射线的方向向量。第二个向量将是从第一条射线的起点到第二条射线的起点的向量。从这里我们取两个向量的叉积并注意符号。

我们再次为第二个三角形执行此操作。同样，起点是第二条射线的起点。第一个向量是第二条射线的方向，第二个向量是从第二条射线的起点到第一条射线的起点的向量。我们再次取两个向量的叉积并注意符号。

现在我们只需取两个符号并检查它们是否相同。如果它们相同，我们就没有相交。如果它们不同，我们就有一个相交。就是这样！

以下是一些伪代码：

sign1 = cross(vector1, point1 - point2)
sign2 = cross(vector2, point2 - point1)

if (sign1 * sign2 < 0) // If signs are mismatched, they will multiply to be negative
    return intersection

这相当于五次乘法，六次减法和一次比较。

- Faken

---

啊，你懂了。我没看到那个。 - John

不知道是否需要考虑“边缘情况”，但我编辑了我的答案来描述它们。 - John

我的应用程序中的边缘情况非常不太可能发生，即使有误报，也不会真正对我造成伤害。由于我正在迭代可能达到数十亿次的这种情况，所以我需要原始速度。我只会简单地说如果出现任何共线现象，我们将称其为交叉点，而不是添加一些额外的语句来明确发生了什么。 - Faken

不，这是错误的。请看我在CashCommons的John评论中同样不正确的解决方案。 - Adam Rosenfield

Answer 9

如果线的长度是无限的，那么它们将总是相交，除非它们是平行的。要检查它们是否平行，请找到每条线的斜率并进行比较。斜率将只是(y2-y1)/(x2-x1)。

- Ben313

---

直线并非射线，而且平行的直线也可以相交（如果它们是同一条直线）。 - corsiKa

如果二维空间是弯曲的，平行线可以相交（例如纬度和经度）。 - Vivin Paliath

抱歉，我编辑了我的帖子以反映我真正想问的问题。这些线实际上是从一个起点开始但没有结束的射线。检查斜率不会给我答案，因为“线”可能在点的“错误”一侧相交，这被视为未命中。 - Faken

我认为这个问题意味着它们在两个方向上都不是无限的：它们有一个起始向量和一个方向向量。因此，从（1,2）开始并朝（0,1）方向延伸的一条直线将不会与从（2,1）开始并沿（1,0）方向延伸的一条直线相交。 如果它们是直线而不是“射线”，那么你的答案当然是正确的。 - Elliot