Intersection of a Line Segment and a Rectangle

Question

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 1

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.

Answer 2

One easy approach is: check intersection with each rectangle line.

Here follow my lua code for that (Line line intersection)

function getVec2(x_,y_)
    vec2={}
    vec2.x=x_
    vec2.y=y_

    function vec2:dist() --set relative position
        return math.sqrt(vec2.x*vec2.x + vec2.y*vec2.y)
    end

    function vec2:sqrdist() --set relative position
        return vec2.x*vec2.x + vec2.y*vec2.y
    end

    function vec2.mulf(v,f  ) 
        return getVec2(v.x*f , v.y*f)
    end

    function vec2.minus(v1 ,v2  ) 
        return getVec2(v1.x-v2.x , v1.y-v2.y)
    end

    --cross product v × w to be vx wy − vy wx
    function vec2.cross(v1,v2  ) 
        return v1.x*v2.y - v1.y*v2.x
    end
    function vec2.dot(v1,v2  ) 
        return v1.x*v2.x + v1.y*v2.y
    end
    function vec2.add(v1,v2  ) 
        return getVec2(v1.x+v2.x , v1.y+v2.y)
    end

    function vec2.normalize(v1)
        local d = v1:dist() 
        if d> 0 then
            return getVec2(v1.x/d,v1.y/d)
        else
            return getVec2(0,0)
        end
    end

    function vec2.normal(v1)
        return getVec2(-v1.y ,v1.x)
    end

    function vec2.left(v1)
        return getVec2(-v1.y ,v1.x)
    end

    function vec2.right(v1)
        return getVec2(v1.y ,-v1.x)
    end
    return vec2 
end
function findIntersect(l1p1x,l1p1y, l1p2x,l1p2y, l2p1x,l2p1y, l2p2x,l2p2y)
    local p = getVec2(l1p1x,l1p1y)
    local p1 = getVec2(l1p2x,l1p2y)
    local q = getVec2(l2p1x,l2p1y)
    local q1 = getVec2(l2p2x,l2p2y)

    return  vec2findIntersect(p,p1,q,q1)

end

function vec2findIntersect(p,p1,q,q1)
--https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect

    local r = vec2.minus(p1 ,p  ) 
    local s = vec2.minus(q1 ,q  ) 

    --t = (q − p) × s / (r × s)
    --u = (q − p) × r / (r × s)

    local q_p = vec2.minus(q,p)
    local q_pdots = vec2.cross(q_p,s)
    local q_pdotr = vec2.cross(q_p,r)
    local rdots = vec2.cross(r,s)

    --If r × s = 0
    if rdots == 0 then
        return false,false,nil
    end

    local t = q_pdots / rdots
    local u = q_pdotr / rdots

    --if 0 ≤ t ≤ 1 and 0 ≤ u ≤ 1, the two line segments meet at the point p + t r = q + u s.
    if ((t>= 0 ) and (t<=1) and (u>= 0 ) and (u<= 1 )) then
        --p + t  *r 
        local ret = vec2.mulf(r,t) 
        ret = vec2.add(p,ret  ) 
        return ret.x,ret.y,ret
    end
    return false,false,nil
end 

Answer 3

Technically, you have a line expressed as a series of points. Then, you express the rectangle as bounded constraints. Then you would create sub-lines from the original lines by the bounded constraints. Depending on your own algorithm, this may have different effects, but this is the general idea.

Answer 4

You can use the Line-Line intersection formula, Line-line intersection.

If you consider a class Line class that is made up of two Vector2s you can calculate, using the above formula, the intersection between them.

class Line {
    public Vector2 a;
    public Vector2 b;

    public Line(Vector2 a, Vector2 b) {
        this.a = a;
        this.b = b;
    }

    Vector2 findIntersection(Line a, Line b)
        float x1 = a.a.x;
        float y1 = a.a.y;
        float x2 = a.b.x;
        float y2 = a.b.y;

        float x3 = b.a.x;
        float y3 = b.a.y;
        float x4 = b.b.x;
        float y4 = b.b.y;

        float denominator = (x1 - x2)*(y3 - y4) - (y1 - y2)*(x3 - x4);
        if (denominator == 0)
            return null;

        float xNominator = (x1*y2 - y1*x2)*(x3 - x4) - (x1 - x2)*(x3*y4 - y3*x4);
        float yNominator = (x1*y2 - y1*x2)*(y3 - y4) - (y1 - y2)*(x3*y4 - y3*x4);

        float px = xNominator / denominator;
        float py = yNominator / denominator;

        return new Vector2D(px, py);
    }
}

The above maps onto the function on wikipedia where you've got two points on a line (Given two points on each line).

Then it's a matter of turning the rectangle into Line which is of course done by taking the different corners as the points on the line and call the above method for each line and corner-to-corner line. Somewhat ugly that can be solved like this;

Vector2 findIntersection(Line a, Vector2 c0, Vector2 c1, Vector2 c2, Vector2 c3) {
    Line l0 = new Line(c0, c1);
    Line l1 = new Line(c1, c2);
    Line l2 = new Line(c2, c3);
    Line l3 = new Line(c3, c0);

    Vector2 intersection = null;

    intersection = findIntersection(a, l0);
    if (intersection != null) return intersection;

    intersection = findIntersection(a, l1);
    if (intersection != null) return intersection;

    intersection = findIntersection(a, l2);
    if (intersection != null) return intersection;

    intersection = findIntersection(a, l3);
    if (intersection != null) return intersection;

    return null;

} 

An important thing to point out here is that the formula will give you an intersection even if that intersection isn't between a and b, so you likely will want to constrain the results to results that fall within that range (one way to do that would be to do an bounds-inclusive contains on the source rectangle).