How to check if line segment intersects a rectangle?

Question

If you have 2 points, (x1, y1) and (x2, y2), which represent two opposite corners of a rectangle, and 2 other points, (x3,y3) and (x4,y4), which represent 2 endpoints of a line segment, how can you check if the line segment intersects the rectangle?

(The line segment is just the segment contained between the given endpoints. It is not an infinite length line defined by those two points.)

Mariettamariette

possible duplicate of line-rectangle collision detection – Jollanta

your line is called segment – Connelly

Answer 1

One very simple option would be to use a standard algorithm for checking whether two line segments intersect to check whether the line segments intersects any of the four line segments that make up the corners of the box. It's computationally very efficient to check if two line segments intersect, so I would expect that this could run very quickly.

Hope this helps!

Jollanta

There is one case that is not handled by the idea given by @templatetypedef: the case where the two endpoints of the line segment are inside the rectangle. But that case is easy to check: x1 < x3 && x3 < x2 && y1 < y3 && y3 < y2. – Woaded

@Woaded Except that if it's contained in the rectangle, it doesn't intersect the rectangle. – Schall

@MarkPing: that depends if you consider the rectangle as-is, or only the boundary of it. – Woaded

What's the best way to handle the case where the line segment passes directly through a corner of the rectangle, thus causing intersection checks with both sides of the rectangle touching that corner to fail? – Miniaturize

Wouldn't the collision checks pass if the line hits a corner? Assume you have an inclusive check for each edge, you should be fine. – Jollanta

@templatetypedef: Yep, you're right. I thought I was getting a rounding error, but my line segment intersection code was just checking exclusively, not inclusively. Thanks! (I do, though, still wonder if it's possible for rounding errors to cause problems here.) – Miniaturize

Answer 2

To understand how to derive the formula for testing whether a line-segment intersects a rectangle, it's important to remember the properties of the vector dot product.

Represent the line-segment as a unit-vector and a distance between the line-segment's start-point and the origin. Here's some C# code to calculate that from the PointF variables a_ptStart and a_ptEnd, using a Vector:

Vector vecLine = new Vector(a_ptEnd.X - a_ptStart.X, a_ptEnd.Y - a_ptStart.Y);
double dLengthLine = vecLine.Length;
vecLine /= dLengthLine;
double dDistLine = Vector.Multiply(vecLine, new Vector(a_ptStart.X, a_ptStart.Y));

You'll also need to calculate the perpendicular vector, and its distance from the origin, for the line segment. Rotating a unit vector by 90° is easy.

Vector vecPerpLine = new Vector(-vecLine.Y, vecLine.X);
double dDistPerpLine = Vector.Multiply(vecPerpLine, new Vector(a_ptStart.X, a_ptStart.Y));

Assuming the four corners of the rectangle are in Vector variables called vecRect1, vecRect2, vecRect3, and vecRect4, calculate the distance between the line-segment and all four corners of the target's bounding-rectangle:

double dPerpLineDist1 = Vector.Multiply(vecPerpLine, vecRect1) - dDistPerpLine;
double dPerpLineDist2 = Vector.Multiply(vecPerpLine, vecRect2) - dDistPerpLine;
double dPerpLineDist3 = Vector.Multiply(vecPerpLine, vecRect3) - dDistPerpLine;
double dPerpLineDist4 = Vector.Multiply(vecPerpLine, vecRect4) - dDistPerpLine;
double dMinPerpLineDist = Math.Min(dPerpLineDist1, Math.Min(dPerpLineDist2,
    Math.Min(dPerpLineDist3, dPerpLineDist4)));
double dMaxPerpLineDist = Math.Max(dPerpLineDist1, Math.Max(dPerpLineDist2,
    Math.Max(dPerpLineDist3, dPerpLineDist4)));

If all distances are positive, or all distances are negative, then the rectangle is on one side of the line or the other, so there's no intersection. (Zero-extent rectangles are considered not to intersect with any line-segment.)

if (dMinPerpLineDist <= 0.0 && dMaxPerpLineDist <= 0.0
        || dMinPerpLineDist >= 0.0 && dMaxPerpLineDist >= 0.0)
    /* no intersection */;

Next, project all four corners of the target's bounding rectangle onto the line-segment. This gives us the distance between the line's origin and the projection of the rectangle-corner on that line.

double dDistLine1 = Vector.Multiply(vecLine, vecRect1) - dDistLine;
double dDistLine2 = Vector.Multiply(vecLine, vecRect2) - dDistLine;
double dDistLine3 = Vector.Multiply(vecLine, vecRect3) - dDistLine;
double dDistLine4 = Vector.Multiply(vecLine, vecRect4) - dDistLine;
double dMinLineDist = Math.Min(dDistLine1, Math.Min(dDistLine2,
    Math.Min(dDistLine3, dDistLine4)));
double dMaxLineDist = Math.Max(dDistLine1, Math.Max(dDistLine2,
    Math.Max(dDistLine3, dDistLine4)));

If the rectangle's points don't fall within the line segment's extent, then there's no intersection.

if (dMaxLineDist <= 0.0 || dMinLineDist >= dLengthLine)
    /* no intersection */;

I believe that's sufficient.

Detergency

does this method generalizes to 3D? Assuming we have normal of that rectangle. With segment direction and normal we can get 3rd direction which is perpendicular to both of them, so we can calculate 'vecPerpLine'. Rest is using dot products and subtractions of distance. That makes sense for me. Someone can comment my idea ? – Archle

Answer 3

Get the dot product of all 4 vertices (the corners of the rectangle) with the direction vector of the line segment. If all 4 have values of the same sign, then all the vertices lie on the same side of the line (not the line segment, but the infinite line) and thus the line does not intersect the rectangle. This approach is only viable for 2D intersection detection. This can be used to filter through most of them quickly (using only multiplications and additions). You'll have to do further checks for line segments instead of lines.

Amourpropre

I have been thinking about this... It's not correct. All the vertices can lie at the same side of the line, but still produce dot products with opposite signs. Also using the direction vector does not take into account where the line actually is. One can choose two parallel lines: one that intersects the rectangle and one that doesn't. Since their direction is the same, the four dot products will produce the same values for both lines, which clearly contradicts the theorem. I have to -1 this, although the initial idea was nice. – Miceli

This answer seems very confusing? It gets rid of any positional data for the line so would only be valid for lines that go through the origin. Even so, it doesn't work even for lines that through the origin, think of a line direction vector (1/√2, 1/√2), and a rectangle (5, 10), (15,10), (5,0), (15,0). All dot products are positive yet it intersects. – Northey

It could work if you took the normal to the direction vector however, which still doesn't work for lines not going through the origin. You could however offset all coordinates by this amount and it would work. – Northey