rectangle overlay

Mar 7, 2022 at 5:35pm
leo2008 (148)
I am trying to solve this problem, than given 2 rectangles as below:

+===============+ (x2,y2)
| |
| |
(x1,y1)+===============+

Need to implement function that returns true or false if 2 rectangles overlay.
Rectangle C = [x1,y1,x2,y2] and Rectangle D = [x1,y1,x2,y2]

Example: Rectangle[1,1,3,3] overlays with Rectangle[2,2,4,4] return true

Below is my pseudo code so far.

1
2
3
4
5
6
7
8
9
10
11
12
 

int solve(int C[], int O, int D[], int L)
{

  if(O <D[0] || L <C[0]) return 0;
  if(D[1]<O || C[1]<L) return 0;
        
        else return 1;

}


Any comments?
Mar 7, 2022 at 5:46pm
jonnin (11494)
solve it on paper (just the math part, no code). Does it count if they touch, eg share a line?
Once you solve it on paper, implementation in code will be trivial.

code-wise, pointless if-statements can cost you depending on a lot of compiler optimization factors and cpu capabilities.
just say
return (compound boolean expression);
and, use bool (type) with true/false (keywords) for boolean expressions. Int works, but it is crude.
Last edited on Mar 7, 2022 at 5:48pm
Mar 7, 2022 at 7:48pm
Duthomhas (13277)
Variable names matter, dude.

So do type names and function names.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
#include <stdbool.h>
#include <stdio.h>

typedef int rectangle[4];

bool is_overlap( rectangle r1, rectangle r2 )
{
  ...
}

int main()
{
  rectangle a = { 1,1,3,3 };
  rectangle b = { 2,2,4,4 };
  if (is_overlap( a, b ))
  {
    puts( "overlap" );
  }
  else
  {
    puts( "disjoint" );
  }
}
Edit & run on cpp.sh

The names of things are directly related to how clearly you are able to think about your code.
Mar 7, 2022 at 9:18pm
dhayden (5799)
It's easier to solve the inverse problem: when do rectangles r1 and r2 NOT overlap. They don't overlap if r1 is above, below, to the left, or to the right of r2. Think carefully about when they are adjacent so you don't end up with an off-by-one error. Consider these tests:
In addition to the above, consider these test cases:
r1 is completely inside r2
r1 is adjacent to r2
r1 and r2 touch at the corners.
Mar 8, 2022 at 9:12am
leo2008 (148)
How about this way?

1
2
3
4
5
6
 

bool isRect_Overlap(vector<int>& rect1, vector<int>& rect2) 
    {
        return max(rect1[1],rect2[1])<min(rect1[3],rect2[3])&&max(rect1[2],rect2[2])<min(rect1[4],rect2[4]);
    }
Last edited on Mar 8, 2022 at 9:20am
Mar 8, 2022 at 9:19am
lastchance (6980)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
#include <iostream>
#include <algorithm>
using namespace std;

struct Rectangle
{
   double x1, y1, x2, y2;
   Rectangle( double x1_, double y1_, double x2_, double y2_ ) : x1( x1_ ), y1( y1_ ), x2( x2_ ), y2( y2_ )
   {
      if ( x1 > x2 ) swap( x1, x2 );             // Force storage as bottom-left / top-right
      if ( y1 > y2 ) swap( y1, y2 );
   }
};

bool overlay( Rectangle r, Rectangle s )         // FWIW, take as true if there is a non-zero area of intersection 
{
   if ( r.x1 >= s.x2 || r.x2 <= s.x1 || r.y1 >= s.y2 || r.y2 <= s.y1 ) return false;
   return true;
}


int main()
{
   Rectangle A{ 0, 0, 1, 1 }, B{ 0.5, 0.5, 0.6, 0.8 };
   cout << boolalpha << overlay( A, B ) <<'\n';
}
Edit & run on cpp.sh
Mar 8, 2022 at 9:23am
leo2008 (148)
Thanks a lot, lastchance, for your valuable inputs here :-)
Topic archived. No new replies allowed.