How to check if line segment intersects a rectangle?

Solution 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!

Solution 2:

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.

Solution 3:

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.