直线与AABB矩形的相交？

Question

最好不要使用任何循环，因为这将用于游戏。

我希望将一条线段与一个任意大小的矩形相交。 但我也希望返回交点（们）。

我已经尝试过谷歌搜索，但仍未解决问题。

该线由(x1,y1,x2,y2)定义。 矩形也有这两个点。

- Steffan Donal

---

从简单问题开始。你知道如何求两条无限长的直线的交点吗？ - Eric Lippert

我并不认为你通过苏格拉底式的教学方法会学得更好；我理解并非每个人都适用这种方法。相反，我试图评估你现有知识水平。如果你不知道如何相交两条直线，那么在尝试相交更复杂的几何图形之前，你可能需要先学习这个。 - Eric Lippert

我基本上不同意这种说法。有时候，仅仅实现别人的代码解决方案，验证其可行性，然后忘掉它，会比学习解决方案背后的理论并自己实现更好。虽然你不能学到太多知识，但并非每个人都想要或需要学到所有东西。 - Minthos

Answer 1

我建议对组成矩形的每条线段（边）进行线段交点检查。以下是我很久以前编写的线段交点检测算法，从我的旧XNA项目中挖掘出来：

// a1 is line1 start, a2 is line1 end, b1 is line2 start, b2 is line2 end
static bool Intersects(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2, out Vector2 intersection)
{
    intersection = Vector2.Zero;

    Vector2 b = a2 - a1;
    Vector2 d = b2 - b1;
    float bDotDPerp = b.X * d.Y - b.Y * d.X;

    // if b dot d == 0, it means the lines are parallel so have infinite intersection points
    if (bDotDPerp == 0)
        return false;

    Vector2 c = b1 - a1;
    float t = (c.X * d.Y - c.Y * d.X) / bDotDPerp;
    if (t < 0 || t > 1)
        return false;

    float u = (c.X * b.Y - c.Y * b.X) / bDotDPerp;
    if (u < 0 || u > 1)
        return false;

    intersection = a1 + t * b;

    return true;
}

我将把每条边输入上述方法并收集结果留给读者作为练习 :)

---

编辑1年后，现在我已经上了大学并学了一门图形课程：

当您有一组大多数不与矩形相交的线时，可以查看Cohen-Sutherland算法以高效地完成此操作。它使用一个9段网格，并将每个线段的端点放置在该网格的某个区域中：

使用这种方法，我们可以确定是否没有任何线段相交：

例如，在此处CD不会与矩形相交（在第一幅图像中以红色显示），因为C和D都在顶行，AB也是如此。对于可能与矩形相交的线，我们必须尝试线-线交点。

部分编号/标签的方式使我们可以简单地执行x AND y != 0（其中x和y是每个线段端点的部分标签）以确定是否不会有交点。

使用此方法意味着我们必须进行许多更少的线-线交点，从而大大加快了整个过程的速度。

- Callum Rogers

---

在上面的代码示例中，那些实际上是叉积，而不是点积。 - Nathanael Weiss

Cohen-Sutherland算法似乎是关于剪裁和查找交点，而不是判断是否有交点 - 所以这肯定会更慢吧？ - paulm

嗯，Cohen-Sutherland算法假设有限空间被分成9个相等的区域（或者在3D中是27个）。当你的空间是无限大时会发生什么？ - Matt Esch

@MattEsch：我猜你只需要使得外部的8（26）个区域无限就可以了。 - Moberg

如果这些线是无限的呢？ - rxantos