How to know if a line intersects a rectangle

Question

I have checked out this question, but the answer is very large for me:

How to know if a line intersects a plane in C#? - Basic 2D geometry

Is there any .NET method to know if a line defined by two points intersects a rectangle?

public bool Intersects(Point a, Point b, Rectangle r)
{
   // return true if the line intersects the rectangle
   // false otherwise
}

Thanks in advance.

Answer 1

The simplest computational geometry technique is to just walk through the segments of the polygon and see if it intersects with any of them, as it then must also intersect the polygon.

The only caveat of this method (and most of CG) is that we have to be careful about edge cases. What if the line crosses the rectangle at a point - do we count that as intersection or not? Be careful in your implementation.

Edit: The typical tool for the line-intersects-segment calculation is a LeftOf(Ray, Point) test, which returns if the point is the to the left of the ray. Given a line l (which we use as a ray) and a segment containing points a and b, the line intersects the segment if one point is to the left and one point is not:

(LeftOf(l,a) && !LeftOf(l,b)) || (LeftOf(l,b) && !LeftOf(l,a))

Again, you need to watch out for edge-cases, when the point is on the line, but depends how you wish to actually define intersection.

Answer 2

For Unity (inverts y!). This takes care of division by zero problem that other approaches here have:

using System;
using UnityEngine;

namespace Util {
    public static class Math2D {

        public static bool Intersects(Vector2 a, Vector2 b, Rect r) {
            var minX = Math.Min(a.x, b.x);
            var maxX = Math.Max(a.x, b.x);
            var minY = Math.Min(a.y, b.y);
            var maxY = Math.Max(a.y, b.y);

            if (r.xMin > maxX || r.xMax < minX) {
                return false;
            }

            if (r.yMin > maxY || r.yMax < minY) {
                return false;
            }

            if (r.xMin < minX && maxX < r.xMax) {
                return true;
            }

            if (r.yMin < minY && maxY < r.yMax) {
                return true;
            }

            Func<float, float> yForX = x => a.y - (x - a.x) * ((a.y - b.y) / (b.x - a.x));

            var yAtRectLeft = yForX(r.xMin);
            var yAtRectRight = yForX(r.xMax);

            if (r.yMax < yAtRectLeft && r.yMax < yAtRectRight) {
                return false;
            }

            if (r.yMin > yAtRectLeft && r.yMin > yAtRectRight) {
                return false;
            }

            return true;
        }
    }
}

Answer 3

    public static bool LineIntersectsRect(Point p1, Point p2, Rectangle r)
    {
        return LineIntersectsLine(p1, p2, new Point(r.X, r.Y), new Point(r.X + r.Width, r.Y)) ||
               LineIntersectsLine(p1, p2, new Point(r.X + r.Width, r.Y), new Point(r.X + r.Width, r.Y + r.Height)) ||
               LineIntersectsLine(p1, p2, new Point(r.X + r.Width, r.Y + r.Height), new Point(r.X, r.Y + r.Height)) ||
               LineIntersectsLine(p1, p2, new Point(r.X, r.Y + r.Height), new Point(r.X, r.Y)) ||
               (r.Contains(p1) && r.Contains(p2));
    }

    private static bool LineIntersectsLine(Point l1p1, Point l1p2, Point l2p1, Point l2p2)
    {
        float q = (l1p1.Y - l2p1.Y) * (l2p2.X - l2p1.X) - (l1p1.X - l2p1.X) * (l2p2.Y - l2p1.Y);
        float d = (l1p2.X - l1p1.X) * (l2p2.Y - l2p1.Y) - (l1p2.Y - l1p1.Y) * (l2p2.X - l2p1.X);

        if( d == 0 )
        {
            return false;
        }

        float r = q / d;

        q = (l1p1.Y - l2p1.Y) * (l1p2.X - l1p1.X) - (l1p1.X - l2p1.X) * (l1p2.Y - l1p1.Y);
        float s = q / d;

        if( r < 0 || r > 1 || s < 0 || s > 1 )
        {
            return false;
        }

        return true;
    }

Answer 4

Unfortunately the wrong answer has been voted up. It is much to expensive to compute the actual intersection points, you only need comparisons. The keyword to look for is "Line Clipping" (http://en.wikipedia.org/wiki/Line_clipping). Wikipedia recommends the Cohen-Sutherland algorithm (http://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland) when you want fast rejects, which is probably the most common scenario. There is a C++-implementation on the wikipedia page. If you are not interested in actually clipping the line, you can skip most of it. The answer of @Johann looks very similar to that algorithm, but I didn't look at it in detail.

Answer 5

Brute force algorithm...

First check if the rect is to the left or right of the line endpoints:

• Establish the leftmost and rightmost X values of the line endpoints: XMIN and XMAX
• If Rect.Left > XMAX, then no intersection.
• If Rect.Right < XMIN, then no intersection.

Then, if the above wasn't enough to rule out intersection, check if the rect is above or below the line endpoints:

• Establish the topmost and bottommost Y values of the line endpoints: YMAX and YMIN
• If Rect.Bottom > YMAX, then no intersection.
• If Rect.Top < YMIN, then no intersection.

Then, if the above wasn't enough to rule out intersection, you need to check the equation of the line, y = m * x + b, to see if the rect is above the line:

• Establish the line's Y-value at Rect.Left and Rect.Right: LINEYRECTLEFT and LINEYRECTRIGHT
• If Rect.Bottom > LINEYRECTRIGHT && Rect.Bottom > LINEYRECTLEFT, then no intersection.

Then, if the above wasn't enough to rule out intersection, you need to check if the rect is below the line:

• If Rect.Top < LINEYRECTRIGHT && Rect.Top < LINEYRECTLEFT, then no intersection.

Then, if you get here:

• Intersection.

N.B. I'm sure there's a more elegant algebraic solution, but performing these steps geometrically with pen and paper is easy to follow.

Some untested and uncompiled code to go with that:

public struct Line
{
    public int XMin { get { ... } }
    public int XMax { get { ... } }

    public int YMin { get { ... } }
    public int YMax { get { ... } }

    public Line(Point a, Point b) { ... }

    public float CalculateYForX(int x) { ... }
}

public bool Intersects(Point a, Point b, Rectangle r)
{
    var line = new Line(a, b);

    if (r.Left > line.XMax || r.Right < line.XMin)
    {
        return false;
    }

    if (r.Top < line.YMin || r.Bottom > line.YMax)
    {
        return false;
    }

    var yAtRectLeft = line.CalculateYForX(r.Left);
    var yAtRectRight = line.CalculateYForX(r.Right);

    if (r.Bottom > yAtRectLeft && r.Bottom > yAtRectRight)
    {
        return false;
    }

    if (r.Top < yAtRectLeft && r.Top < yAtRectRight)
    {
        return false;
    }

    return true;
}

Answer 6

I took HABJAN's solution, which worked well, and converted it to Objective-C. The Objective-C code is as follows:

bool LineIntersectsLine(CGPoint l1p1, CGPoint l1p2, CGPoint l2p1, CGPoint l2p2)
{
    CGFloat q = (l1p1.y - l2p1.y) * (l2p2.x - l2p1.x) - (l1p1.x - l2p1.x) * (l2p2.y - l2p1.y);
    CGFloat d = (l1p2.x - l1p1.x) * (l2p2.y - l2p1.y) - (l1p2.y - l1p1.y) * (l2p2.x - l2p1.x);

    if( d == 0 )
    {
        return false;
    }

    float r = q / d;

    q = (l1p1.y - l2p1.y) * (l1p2.x - l1p1.x) - (l1p1.x - l2p1.x) * (l1p2.y - l1p1.y);
    float s = q / d;

    if( r < 0 || r > 1 || s < 0 || s > 1 )
    {
        return false;
    }

    return true;
}

bool LineIntersectsRect(CGPoint p1, CGPoint p2, CGRect r)
{
    return LineIntersectsLine(p1, p2, CGPointMake(r.origin.x, r.origin.y), CGPointMake(r.origin.x + r.size.width, r.origin.y)) ||
    LineIntersectsLine(p1, p2, CGPointMake(r.origin.x + r.size.width, r.origin.y), CGPointMake(r.origin.x + r.size.width, r.origin.y + r.size.height)) ||
    LineIntersectsLine(p1, p2, CGPointMake(r.origin.x + r.size.width, r.origin.y + r.size.height), CGPointMake(r.origin.x, r.origin.y + r.size.height)) ||
    LineIntersectsLine(p1, p2, CGPointMake(r.origin.x, r.origin.y + r.size.height), CGPointMake(r.origin.x, r.origin.y)) ||
    (CGRectContainsPoint(r, p1) && CGRectContainsPoint(r, p2));
}

Many thanks HABJAN. I will note that at first I wrote my own routine which checked each point along the gradient, and I did everything I could do to maximize performance, but this was immediately far faster.