c# - 线与 AABB 矩形相交？

Question

最好不要使用任何类型的循环，因为这将在游戏中使用。

我希望将一条线与任意大小的矩形相交。但我也希望返回交点[s]。

这是可能的，我已经做了一些谷歌搜索，但仍然没有解决。

直线是使用 (x1,y1,x2,y2) 定义的。矩形也有这两点。

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 年后现在我已经上大学并完成了图形类(class):

看看 Cohen–Sutherland algorithm当你有一大组线，其中大多数线不与矩形相交时，可以有效地做到这一点。它使用 9 段网格，您将线的每个端点放在所述网格的区域中:

使用它我们可以判断是否不会有任何线交叉点:

例如，CD 不会与矩形(在第一张图中以红色显示)相交，因为 C 和 D 都在顶行，AB 也不会。对于那些线可能与矩形相交的地方，我们必须尝试线与线相交。

它们对部分进行编号/标记的方式允许我们简单地执行 x AND y != 0(其中 x 和 y 是每个线端点的部分标签)以确定是否不会有交叉点。

使用这种方法意味着我们必须减少很多很多的线对线交叉点，这会大大加快整个过程。