与AABB矩形线的交点？ [英] Line intersection with AABB Rectangle?

问题描述

preferably不使用任何形式的循环，因为这会在游戏中使用。

Preferably without using any kind of loop, as this'll be used in a game.

我想相交的线用矩形，任意大小的。
但我也希望有交点[S]被返回。

I wish to intersect a line with a rectangle, of arbitrary size. But I also wish for the intersection point[s] to be returned.

这是可能的，我做了一个小Googling，但还没有制定出来。

It's possible, I've done a little googling, but still have not worked it out.

的线是用（X1，Y1，X2，Y2）定义。
该矩形这两点了。

The line is defined using (x1,y1,x2,y2). The rectangle has these two points too.

推荐答案

我会建议简单地做每一线段（边），构成了矩形一个线段，线段相交检查。这里是一个线段相交检测算法我很久以前写的，从我的旧XNA项目之一疏浚了起来：

I would recommend simply doing a line-segment-line-segment intersection check on each line segment (edge) that makes up the rectangle. Here is a line segment intersection detection algorithm I wrote ages ago, dredged up from one of my old XNA projects:

// 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;
}

我将离开输入每个边到上述方法收集的结果作为练习读者：）

I will leave inputting each edge into the above method and collecting the results as an exercise to the reader :)

看看在科恩 - 萨瑟兰算法，当你有一个有效地做到这一点大集大多数不相交矩形线条。它采用了9段网格，你把线的每个端点在所述电网的区域：

Take a look at the Cohen–Sutherland algorithm to do this efficiently when you have a large set of lines where most do not intersect the rectangle. It uses a 9 segment grid and you place each endpoint of the line in a region of said grid:

使用此，我们可以判断，不会有任何的直线相交：

Using this we can tell if there will not be any line intersections:

例如这里 CD 不会相交的矩形（在第一幅图像显示为红色）既 C 和 D 是前行中既不意愿 AB 。对于个位数，其中该行可能相交矩形，我们必须尝试线 - 线交叉点。

For example here CD will not intersect the rectangle (shown in red in the first image) as both C and D are in the top row and neither will AB. For the ones where the line may intersect the the rectangle we have to try the line-line intersections.

他们的方法/标有部分的编号可以让我们简单地做 X和Y！= 0 （其中 X 和是是每个线的端点），则区间的标签，以确定是否存在将不会被一个路口

They way the sections are numbered/labelled allows us to simply do x AND y != 0 (where x and y are the labels of the sections for each of the line's endpoints) to determine if there will not be an intersection.

使用这种方法意味着我们有很多很多更少的线线的交会点，大规模加速了整个事情。

Using this method means we have to many, many fewer line-line intersections which speeds up the whole thing massively.

这篇关于与AABB矩形线的交点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！