与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
不会与矩形相交(在第一张图像中以红色显示),因为C
和D
都在顶行, AB
也不在。 对于线可能与矩形相交的线,我们必须尝试线 – 线交点。
它们的编号/标记部分允许我们简单地执行x AND y != 0
(其中x
和y
是每个线的端点的部分的标签)以确定是否不存在交叉点。
使用这种方法意味着我们必须有许多,更少的线路交叉点,这大大加快了整个事物的速度。