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.

Are you talking about a [line](https://en.wikipedia.org/wiki/Line_%28geometry%29), or a line segment? e.g. if the two points are both inside the rectangle, does the line intersect — naught101, Oct 20 '15 at 08:28
check it out: http://www.jeffreythompson.org/collision-detection/line-rect.php — ashleedawg, Jul 01 '21 at 15:34

HABJAN · Accepted Answer · 2011-04-01T14:52:45.377

32

    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;
    }

edited Apr 01 '11 at 14:52

answered Apr 01 '11 at 14:15

HABJAN

9,212
3
35
59

@Habjan: Thanks, simple, and concrete. The best answer. Is it tested? – Daniel Peñalba Apr 01 '11 at 14:36
@Daniel Peñalba: I did couple of tests :-) – HABJAN Apr 01 '11 at 14:40
@Daniel, What if the line segment is contained entirely within the rectangle? Is it considered "intersecting"? – Dave Rager Apr 01 '11 at 14:49
I updated the code, added (r.Contains(p1) && r.Contains(p2)) in LineIntersectsRect. Now it does @Dave Rager – HABJAN Apr 01 '11 at 14:53
2

@HABJAN: Thanks for the update. I think that condition is (r.Contains(p1) || r.Contains(p2)). If any point is inside the rectangle, the line intersects. – Daniel Peñalba Apr 04 '11 at 09:28
5

can someone explain implementation, it is not totally clear...thanks – Marko Nov 26 '13 at 20:58
1

@Marko: I agree, the variable naming especially makes it unclear. But a simple algorithm (assuming your rectangle has horizontal and vertical lines) is: get x values of verticals, check the y value of the line at each x. Then get the y values of the horizontals. If both line y values are greater than the top rectangle y, or both are less than the bottom rectangle y, then your line doesn't intersect. Otherwise, it does. – naught101 Oct 20 '15 at 00:23
what if the line intersects one of the corner points while this MBR lies in one side of this line? The method above cannot handle this case. – chenzhongpu Jul 23 '19 at 13:08

score 16 · Answer 2 · answered May 13 '14 at 20:30

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.

Very good answer. And yes Johann's code look much more better. Thank you for explanation. — Xtro, May 12 '15 at 19:14

Johann Gerell · Answer 3 · 2011-04-01T14:47:15.490

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;
}

As JPE mentioned in his answer, your code is much better than the upvoted answer. — Xtro, May 12 '15 at 19:15
This answer seems to be for a line segment though, not an (infinite) line. — naught101, Oct 20 '15 at 00:25
The question doesn't mention line segment. Two points can also define an actual line. But yeah, the question is a bit ambiguous. — naught101, Oct 20 '15 at 08:23
A gotcha for this answer is that, although for X we almost certainly expect X to increase going RIGHT, for Y this is less sure. In some cases Y increases going DOWNWARDS, in other situations Y increases going UPWARDS like it is assumed in this answer. — Gerard, Aug 24 '17 at 15:13

score 8 · Answer 4 · answered Feb 24 '17 at 09:41

This code has better performance:

    public static bool SegmentIntersectRectangle(
        double rectangleMinX,
        double rectangleMinY,
        double rectangleMaxX,
        double rectangleMaxY,
        double p1X,
        double p1Y,
        double p2X,
        double p2Y)
    {
        // Find min and max X for the segment
        double minX = p1X;
        double maxX = p2X;

        if (p1X > p2X)
        {
            minX = p2X;
            maxX = p1X;
        }

        // Find the intersection of the segment's and rectangle's x-projections
        if (maxX > rectangleMaxX)
        {
            maxX = rectangleMaxX;
        }

        if (minX < rectangleMinX)
        {
            minX = rectangleMinX;
        }

        if (minX > maxX) // If their projections do not intersect return false
        {
            return false;
        }

        // Find corresponding min and max Y for min and max X we found before
        double minY = p1Y;
        double maxY = p2Y;

        double dx = p2X - p1X;

        if (Math.Abs(dx) > 0.0000001)
        {
            double a = (p2Y - p1Y)/dx;
            double b = p1Y - a*p1X;
            minY = a*minX + b;
            maxY = a*maxX + b;
        }

        if (minY > maxY)
        {
            double tmp = maxY;
            maxY = minY;
            minY = tmp;
        }

        // Find the intersection of the segment's and rectangle's y-projections
        if (maxY > rectangleMaxY)
        {
            maxY = rectangleMaxY;
        }

        if (minY < rectangleMinY)
        {
            minY = rectangleMinY;
        }

        if (minY > maxY) // If Y-projections do not intersect return false
        {
            return false;
        }

        return true;
    }

You can also check how it's work in JS demo: http://jsfiddle.net/77eej/2/

If you have two Points and Rect you can call this function like that:

    public static bool LineIntersectsRect(Point p1, Point p2, Rect r)
    {
        return SegmentIntersectRectangle(r.X, r.Y, r.X + r.Width, r.Y + r.Height, p1.X, p1.Y, p2.X, p2.Y);
    }

score 4 · Answer 5 · answered Nov 23 '12 at 09:48

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.

Thanks from Objective-C guys! – Stanislav Pankevich Dec 06 '13 at 23:06 — Stanislav Pankevich, Dec 06 '13 at 23:06

score 1 · Answer 6 · answered Feb 01 '18 at 07:01

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;
        }
    }
}

score 0 · Answer 7 · edited Dec 11 '22 at 16:32

There is no simple predefined .NET method you can call to accomplish that. However, using the Win32 API, there is a pretty easy way to do this (easy in the sense of implementation, performance is not the strong point): LineDDA

BOOL LineDDA(int nXStart,int nYStart,int nXEnd,int nYEnd,LINEDDAPROC lpLineFunc,LPARAM lpData)

This functions calls the callback function for every pixel of the line to be drawn. In this function, you can check if the pixel is within your rectangle - if you find one, then it intersects.

As I said, this is not the fastest solution, but pretty easy to implement. To use it in C#, you will of course need to DllImport it from gdi32.dll.

[DllImport("gdi32.dll")] public static extern int LineDDA(int n1,int n2,int n3,int n4,int lpLineDDAProc,int lParam);

ceyko · Answer 8 · 2011-04-01T14:33:58.283

0

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.

edited Apr 01 '11 at 14:33

answered Apr 01 '11 at 14:10

ceyko

4,822
1
18
23

Surely if you intersect *any* segment of the polygon then you must intersect the polygon? A line that crosses one side of the rectangle but does not reach the other side still intersects the rectangle... – Dan Puzey Apr 01 '11 at 14:14
2

But it is a **line**. It is impossible for it to cross one segment and then just stop in the middle of a rectangle. You're thinking of a segment. I suppose I could have misinterpreted what the question asked, however... – ceyko Apr 01 '11 at 14:21
I think you are describing the algorithm for determining if a point is contained within a polygon by calculating the intersections of the edges of a polygon with a line from the point in question to a point known to be outside the polygon. – Dave Rager Apr 01 '11 at 14:24
I woudl define a line as the straight connection of two points. Are you defining a line in the classical geometric way (i.e. indefinitely?). – Dan Puzey Apr 01 '11 at 14:26
1

If it's a line with no endpoints the number of intersections can never be odd. – Dave Rager Apr 01 '11 at 14:29
@Dave Eek, you're right. I'll just remove the bit about odd/even - clearly if the line intersects *any* segment then it must intersect the polygon. @Dan Yes, I have more of a math background, so I think line == infinite length segment. – ceyko Apr 01 '11 at 14:30
Your edit further confuses the issue: now you're talking about using a (presumably geometric) line as a ray (which it is not). For a ray, your calculation is invalid (you can pass from left to right of a ray without crossing it if you pass "behind" the origin - the calculation is correct for a line, assuming your line isn't running due left-to-right...). I'm not sure this answer is helping to solve the original question! – Dan Puzey Apr 01 '11 at 14:34
It is still LeftOf the ray, even if it doesn't actually cross the ray. I mentioned rays to give a better definition of what LeftOf meant; it's not exactly clear if we say something is left of a line. – ceyko Apr 01 '11 at 14:40
I think the original answer was better, actually: if one of the sides of the rectangle is a sub-line of the line, then the line will only intersect with one side of the rectangle, and will not pass through the rectangle - e.g. it's a tangent of the rectangle. – naught101 Oct 20 '15 at 00:30

How to know if a line intersects a rectangle

8 Answers8

Linked

Related