Intersection of a Line and a Rectangle

I have to calculate the intersection of a line segment (represented by 2 points) with a rectangle.

For example:

Axis aligned rectangle corners: (0, 0) (100, 100)

Point 1: (50, 50)

Point 2: (50, 150)

Expected result: (50, 100)

What would be the way to find the intersection of the line segment with the rectangle?

Answer

As you will easily find out, the most straight-forward solution is to run multiple times an algorithm that checks whether there is an intersection between the segment formed by Point1 and Point2 (let's call them p1 and p2) and the ones formed by each of the vertices of the rectangle (let's call them r1, r2, r3 and r4).

A clean implementation line-seg/line-seg intersection in C# (which can easily be converted to JavaScript, which I think is closer to what you need) is the following:

Vector2? LSegsIntersectionPoint(Vector2 ps1, Vector2 pe1, Vector2 ps2, Vector2 pe2)
{
    // Get A,B of first line - points : ps1 to pe1
    float A1 = pe1.y-ps1.y;
    float B1 = ps1.x-pe1.x;

    // Get A,B of second line - points : ps2 to pe2
    float A2 = pe2.y-ps2.y;
    float B2 = ps2.x-pe2.x;

    // Get delta and check if the lines are parallel
    float delta = A1*B2 - A2*B1;
    if(delta == 0) return null;

    // Get C of first and second lines
    float C2 = A2*ps2.x+B2*ps2.y;

    float C1 = A1*ps1.x+B1*ps1.y;
    //invert delta to make division cheaper
    float invdelta = 1/delta;
    // now return the Vector2 intersection point
    return new Vector2( (B2*C1 - B1*C2)*invdelta, (A1*C2 - A2*C1)*invdelta );
}

Now, considering that you have mentioned to me in the comments of your question that p1 is always inside the rectangle, you will never have more than one intersection between the segment formed by p1 and p2, and the rectangle. So, you just have to repeat the above code for each sides of the rectangle with:

Vector2? LSegRec_IntersPoint_v01(Vector2 p1, Vector2 p2, Vector2 r1, Vector2 r2, Vector2 r3, Vector2 r4)
{

    Vector2? intersection = null;
    intersection = LSegsIntersectionPoint(p1,p2,r1,r2);
    if(intersection == null) intersection = LSegsIntersectionPoint(p1,p2,r2,r3);
    if(intersection == null) intersection = LSegsIntersectionPoint(p1,p2,r3,r4);
    if(intersection == null) intersection = LSegsIntersectionPoint(p1,p2,r4,r1);
    return intersection;
}

I don't know if you plan to perform such checking hundreds of thousands of times, or if performance even is an issue for you. Anyways, for completeness (and for fun), notice that you also have said in your question that your rectangle is axis aligned. This information, summed to the fact that p1 is always inside the rectangle, can raise a much faster solution. Not necessarily easier to code (sorry for calling it "easier"), but much more efficient in case you have a lot of segment-rectangle checks to make. The trick here is the following. You first calculate the min_x, min_y, max_x and max_y of your rectangle. Then, you can use the following function to first check where p2 is in relation to the rectangle and then just do the line-seg checks if the precise sides of the rectangle (never having to check more than 2, while in the worst case the first solution had to check all 4):

Vector2? LSegRec_IntersPoint_v02(Vector2 p1, Vector2 p2, float min_x, float min_y, float max_x, float max_y)

{
    Vector2? intersection;

    if (p2.x < min_x) //If the second point of the segment is at left/bottom-left/top-left of the AABB
    {
        if (p2.y > min_y && p2.y < max_y) { return LSegsIntersectionPoint(p1, p2, new Vector2(min_x, min_y), new Vector2(min_x, max_y)); } //If it is at the left
        else if (p2.y < min_y) //If it is at the bottom-left
        {
            intersection = LSegsIntersectionPoint(p1, p2, new Vector2(min_x, min_y), new Vector2(max_x, min_y));
            if (intersection == null) intersection = LSegsIntersectionPoint(p1, p2, new Vector2(min_x, min_y), new Vector2(min_x, max_y));

            return intersection;
        }
        else //if p2.y > max_y, i.e. if it is at the top-left
        {
            intersection = LSegsIntersectionPoint(p1, p2, new Vector2(min_x, max_y), new Vector2(max_x, max_y));
            if (intersection == null) intersection = LSegsIntersectionPoint(p1, p2, new Vector2(min_x, min_y), new Vector2(min_x, max_y));
            return intersection;
        }
    }


    else if (p2.x > max_x) //If the second point of the segment is at right/bottom-right/top-right of the AABB
    {
        if (p2.y > min_y && p2.y < max_y) { return LSegsIntersectionPoint(p1, p2, new Vector2(max_x, min_y), new Vector2(max_x, max_y)); } //If it is at the right
        else if (p2.y < min_y) //If it is at the bottom-right
        {
            intersection = LSegsIntersectionPoint(p1, p2, new Vector2(min_x, min_y), new Vector2(max_x, min_y));
            if (intersection == null) intersection = LSegsIntersectionPoint(p1, p2, new Vector2(max_x, min_y), new Vector2(max_x, max_y));
            return intersection;
        }
        else //if p2.y > max_y, i.e. if it is at the top-left

        {
            intersection = LSegsIntersectionPoint(p1, p2, new Vector2(min_x, max_y), new Vector2(max_x, max_y));
            if (intersection == null) intersection = LSegsIntersectionPoint(p1, p2, new Vector2(max_x, min_y), new Vector2(max_x, max_y));
            return intersection;
        }
    }

    else //If the second point of the segment is at top/bottom of the AABB
    {
        if (p2.y < min_y) return LSegsIntersectionPoint(p1, p2, new Vector2(min_x, min_y), new Vector2(max_x, min_y)); //If it is at the bottom

        if (p2.y > max_y) return LSegsIntersectionPoint(p1, p2, new Vector2(min_x, max_y), new Vector2(max_x, max_y)); //If it is at the top
    }

    return null;

}

But notice: that second solution is only faster if you can calculate the min_x, min_y, max_x and max_y of your rectangle beforehand. Otherwise, you will have to calculate those inside the function and that will make it slower. Let's say you use the exact same code as the second solution, but just doing that calculation of mins and maxs of the rectangle within the function:

Vector2? LSegRec_IntersPoint_v03(Vector2 p1, Vector2 p2, Vector2 r1, Vector2 r2, Vector2 r3, Vector2 r4)
{

    Vector2? intersection;
    float min_x = Mathf.Min(r1.x, r2.x, r3.x, r4.x);
    float min_y = Mathf.Min(r1.y, r2.y, r3.y, r4.y);
    float max_x = Mathf.Max(r1.x, r2.x, r3.x, r4.x);
    float max_y = Mathf.Max(r1.y, r2.y, r3.y, r4.y);

... then the rest of the the second version continues here

In order to profile that, I created a rectangle where r1 = (-2,-2), r2 = (2,-2), r3 = (2,2) and r4 = (-2,2), p1 = (0,0) and then randomly positioned p2 a bunch of times, always have its X and Y coordinates between -4 and 4. Here are the results, where N is the number of iterations of the simulation:

Notice that, as expected, version 2 is generally much faster to run. The only exception is for N<=1000, when it is roughly the same thing. For greater number of iterations, however, it becomes much faster. But as I've pointed, that's only the case if the mins and maxs of the rectangle are calculated beforehand, because if they have to be calculated within the function (i.e. v03), then it becomes much slower.