Line Intersection with Aabb Rectangle

Line intersection with AABB Rectangle?

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 :)

---

Edit 1 year later now I've gone to university and done a Graphics course:

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:

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.

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.

Intersection of a 2D segment with a rectangle

You can find an example for a line segment intersection with an aabb box here.

Or the same question as your question here

Get intersection point of rectangle and line

Solution for C#, WPF:

 /// <summary>
    /// Get Intersection point
    /// </summary>
    /// <param name="a1">a1 is line1 start</param>
    /// <param name="a2">a2 is line1 end</param>
    /// <param name="b1">b1 is line2 start</param>
    /// <param name="b2">b2 is line2 end</param>
    /// <returns></returns>
    public static Vector? Intersects(Vector a1, Vector a2, Vector b1, Vector b2)
    {
        Vector b = a2 - a1;
        Vector d = b2 - b1;
        var 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 null;

        Vector c = b1 - a1;
        var t = (c.X * d.Y - c.Y * d.X) / bDotDPerp;
        if (t < 0 || t > 1)
            {
            return null;
        }

        var u = (c.X * b.Y - c.Y * b.X) / bDotDPerp;
        if (u < 0 || u > 1)
        {
            return null;
        }

        return a1 + t * b;
    }

Edit
Found Link to SO question where the answer above comes from.

---

Related Topics