Fast rectangle to rectangle intersection

Question

What's a fast way to test if 2 rectangles are intersecting?

A search on the internet came up with this one-liner (WOOT!), but I don't understand how to write it in Javascript, it seems to be written in an ancient form of C++.

struct
{
    LONG    left;
    LONG    top;
    LONG    right;
    LONG    bottom;
} RECT; 

bool IntersectRect(const RECT * r1, const RECT * r2)
{
    return ! ( r2->left > r1->right
        || r2->right < r1->left
        || r2->top > r1->bottom
        || r2->bottom < r1->top
        );
}

Well, this is where its from and it looks the same to me -- http://tekpool.wordpress.com/2006/10/11/rectangle-intersection-determine-if-two-given-rectangles-intersect-each-other-or-not/ — Robin Rodricks, May 02 '10 at 03:36
The original article has a typo. `r2->right left` doesn't make sense. It's might be broken due to HTML escaping issues. — Marcelo Cantos, May 02 '10 at 03:41
I'm curious how you think the above code would be different in a "modern" form of C++. — jamesdlin, May 02 '10 at 03:58
I'm sure the missing characters are `<` symbols due to html escaping. — devios1, May 27 '11 at 15:42
@jamesdlin you would make the function as a member function of the struct, taking one parameter. Secondly you normally would use const& instead of const*. You might use templates to have both int, long, and double versions, instead of using some Win32 macro... (It does not compile either, as RECT ends up being an instance of an unnamed struct, not a type name.) Example: http://ideone.com/bnzwl3 — Sebastian Wahl, Nov 23 '14 at 14:08
I'm voting to close this question as off-topic because it is about trivial translation of source code into another language. — Emil Laine, Feb 07 '16 at 00:53

score 160 · Accepted Answer · edited Jun 16 '23 at 21:41

160

This is how that code can be translated to JavaScript. Note that there is a typo in your code, and in that of the article, as the comments have suggested. Specifically r2->right left should be r2->right < r1->left and r2->bottom top should be r2->bottom < r1->top for the function to work.

function intersectRect(r1, r2) {
  return !(r2.left > r1.right ||
    r2.right < r1.left ||
    r2.top > r1.bottom ||
    r2.bottom < r1.top);
}

// Test case:

var rectA = {
  left: 10,
  top: 10,
  right: 30,
  bottom: 30
};

var rectB = {
  left: 20,
  top: 20,
  right: 50,
  bottom: 50
};

var rectC = {
  left: 70,
  top: 70,
  right: 90,
  bottom: 90
};

console.log(intersectRect(rectA, rectB)); // returns true
console.log(intersectRect(rectA, rectC)); // returns false

edited Jun 16 '23 at 21:41

Lee Taylor

7,761
16
33
49

answered May 02 '10 at 03:50

Daniel Vassallo

337,827
72
505
443

Just to add/confirm - this is testing three boxes that are 20px x 20px, except rectB, which is 30px x 30px – verenion Mar 20 '13 at 12:29
7

if r1 and r2 are identical, the intersectRect function would return false – zumalifeguard Sep 23 '13 at 15:28
Fantastic Eloquent Implementation. Love it! +1, worked perfectly for my game. – Unome Sep 04 '14 at 22:37
1

@zumalifeguard Why do you think that? – Minix Jul 13 '15 at 21:05
1

This function is so genius. I would have never thought of that, instead I would have tried to make the two boxes intersect. – nikk wong Sep 08 '18 at 07:27

score 76 · Answer 2 · answered May 02 '10 at 03:42

76

function intersect(a, b) {
  return (a.left <= b.right &&
          b.left <= a.right &&
          a.top <= b.bottom &&
          b.top <= a.bottom)
}

This assumes that the top is normally less than bottom (i.e. that y coordinates increase downwards).

answered May 02 '10 at 03:42

DS.

22,632
6
47
54

1

Good and working solution, but should be a bit slower since all conditions have to be evaluated. The other solution is done as soon as one of the conditions evaluates to true. – Gigo Jan 14 '13 at 20:43
22

This one is also done as soon as one of the conditions evaluates to false. I.e. in the exact same cases as the other one. – DS. Jan 22 '13 at 22:06
3

This is better as it removes the negation action. – Discipol May 31 '13 at 08:47
4

+1, as much neater than the accepted answer. if using half-open ranges (i.e. rectangle includes top and left but does not include bottom and right, as is common in many graphics systems), changing `<=` to `<` should work. – Jules Aug 08 '13 at 13:08
1

I like this solution because I can remove the `=` for each condition and it allows the rectangles to "touch" on the borders. – prograhammer Jan 03 '17 at 20:20

score 21 · Answer 3 · answered Apr 07 '14 at 19:18

This is how the .NET Framework implements Rectangle.Intersect

public bool IntersectsWith(Rectangle rect)
{
  if (rect.X < this.X + this.Width && this.X < rect.X + rect.Width && rect.Y < this.Y + this.Height)
    return this.Y < rect.Y + rect.Height;
  else
    return false;
}

Or the static version:

public static Rectangle Intersect(Rectangle a, Rectangle b)
{
  int x = Math.Max(a.X, b.X);
  int num1 = Math.Min(a.X + a.Width, b.X + b.Width);
  int y = Math.Max(a.Y, b.Y);
  int num2 = Math.Min(a.Y + a.Height, b.Y + b.Height);
  if (num1 >= x && num2 >= y)
    return new Rectangle(x, y, num1 - x, num2 - y);
  else
    return Rectangle.Empty;
}

score 6 · Answer 4 · edited Mar 03 '17 at 02:25

6

Another more simple way. (This assumes the y-axis increases downwards).

function intersect(a, b) {
  return Math.max(a.left, b.left) < Math.min(a.right, b.right) &&
          Math.max(a.top, b.top) < Math.min(a.bottom, b.bottom);
}

The 4 numbers (max's and min's) in the condition above also give the intersection points.

edited Mar 03 '17 at 02:25

Jack G

4,553
2
41
50

answered Feb 03 '16 at 11:52

Duke

1,332
12
12

score 1 · Answer 5 · answered Sep 21 '16 at 17:46

1

This has a Rect type you can use. It is already JavaScript.

https://dxr.mozilla.org/mozilla-beta/source/toolkit/modules/Geometry.jsm

answered Sep 21 '16 at 17:46

englebart

563
4
9

This code will return false for rects A(0,0,100,100) & B(100,100,100,100). I think theres should be <= instead of – Stanislav S. Nov 02 '16 at 11:50
<= gives a rectangle with a height of 0. Not useful for my purposes. – englebart Nov 16 '16 at 21:05

score 0 · Answer 6 · answered Oct 01 '19 at 14:31

I used a blend of methods, to detect a smaller rectangle inside a large rectangle. This is a nodejs method and uses width/height but can easily be adapted.

            isIntersectingRect: function (r1, r2) {
              var quickCheck = (r1.x <= r2.x + r2.w &&
                      r2.x <= r1.x + r1.w &&
                      r1.y <= r2.y + r2.h &&
                      r2.y <= r1.y + r1.h)
              if (quickCheck) return true;
              var x_overlap = Math.max(0, Math.min(r1.x + r1.w, r2.x + r2.w) - Math.max(r1.x, r2.x));
              var y_overlap = Math.max(0, Math.min(r1.y + r1.h, r2.y + r2.h) - Math.max(r1.y, r2.y));
              var overlapArea = x_overlap * y_overlap;
              return overlapArea == 0;
            }

score 0 · Answer 7 · answered Aug 24 '21 at 20:44

The current .NET way is simply

    public bool IsEmpty => _width < 0.0;   

    public bool IntersectsWith(Rect rect)
    {
        if (IsEmpty || rect.IsEmpty)
        {
            return false;
        }

        if (rect.Left <= Right && rect.Right >= Left && rect.Top <= Bottom)
        {
            return rect.Bottom >= Top;
        }

        return false;
    }

Fast rectangle to rectangle intersection

7 Answers7

Linked