与AABB矩形线交叉?

优选地,不使用任何类型的循环,因为这将在游戏中使用。

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

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

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

我建议简单地在构成矩形的每个线段(边缘)上进行线段线段交叉检查。 这是我很久以前写过的线段交叉检测算法,从我以前的一个旧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 = bX * dY - bY * dX; // 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 = (cX * dY - cY * dX) / bDotDPerp; if (t < 0 || t > 1) return false; float u = (cX * bY - cY * bX) / bDotDPerp; if (u < 0 || u > 1) return false; intersection = a1 + t * b; return true; } 

我将把每个边缘输入到上面的方法中并将结果作为练习收集给读者:)


编辑1年后,我已经上大学并完成了图形课程:

当你有一大堆不与矩形相交的线条时,看一下Cohen-Sutherland算法可以有效地做到这一点。 它使用9段网格,并将该行的每个端点放置在所述网格的区域中:

格

使用这个我们可以判断是否没有任何线交叉点:

网格线

例如,此处CD不会与矩形相交(在第一张图像中以红色显示),因为CD都在顶行, AB也不在。 对于线可能与矩形相交的线,我们必须尝试线 – 线交点。

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

使用这种方法意味着我们必须有许多,更少的线路交叉点,这大大加快了整个事物的速度。