# 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?

• is the rectangle always axis aligned? – ratchet freak Nov 10 '15 at 13:36
• Notice that in your example you just have one intersection between the line segment and the rectangle. But there might be cases where you have two intersection points because the segment may cross the rectangle. The answer you have accepted as correct will only give you the intersection point with the side it finds first (not necessarily in any specific practical order). I will try to post an answer that finds both. – MAnd Nov 10 '15 at 14:50
• @MAnd it's okay one vector is always in the rectangle – ChuckNorris Nov 10 '15 at 15:37
• That's easier, then! In any case I had already answered before you replied my comment. So I think I will not delete the answer anyways, in case it proves somewhat useful to someone who reads it. – MAnd Nov 10 '15 at 16:01
• How would do this it easier? – ChuckNorris Nov 10 '15 at 16:51

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.

• I see where this checks if they are parallel which would be good enough if we were dealing with lines but what about all the other times where two line segments may not intersect? – Zev May 17 '18 at 15:19
• Your first function: LSegsIntersectionPoint does not work for line segments, rather full lines. Your other functions are based on this, so many of them will give bad/invalid results. – A.R. Feb 5 '19 at 4:24

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
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)
return ret.x,ret.y,ret
end
return false,false,nil
end


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.

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