Rectangle interception! HELP!

[misaeltovar]

so im writing a program to test if rectangles intersect... im given x,y,width and length of each rectangle.. so far i have this calculation but in some cases its right and then some is incorrect!

anybody know what im doing wrong?

class Rectangle{
public:
int x, y;

int width;
int length;

Rectangle(int x1, int y1, int w, int l)//Constructor
{
x = x1;
y = y1;

width = w;
length = l;
}

bool intersect(Rectangle r1, Rectangle r2)
{
// x1, y1, w1, L1........ x2, y2, w2, L2
//If X1+H1<X2 or X2+H2<X1 or Y1+W1<Y2 or Y2+W2<Y1

if(r1.x+r1.length < r2.x || r2.x+r2.length < r1.x || r1.y+r1.width < r2.y || r2.y+r2.width < r1.y){
return true;
}
else {
return false;
}
}
};

[Duthomhas]

Your test is wrong.

Consider the following five pairs of rectangles:

  ┌───────────┐             ┌───────────┐
  │ 1         │             │ 2         │
  │           │             │           │
  │      ┌────┼──────┐      │           │ ┌───────────┐
  │      │    │      │      │           │ │           │  
  └──────┼────┘      │      └───────────┘ │           │
         │           │                    │           │
         └───────────┘                    └───────────┘



                            ┌───────────┐
  ┌───────────┐             │ 4         │
  │ 3┌───────┐│             │           │
  │  │       ││             │           │
  │  └───────┘│             │           │
  │           │             └───────────┘
  └───────────┘                    ┌───────────┐
                                   │           │
                                   │           │
                                   │           │
                                   └───────────┘

          ┌───────┐
  ┌───────┼───┐   │
  │ 5     │   │   │
  │       │   │   │
  │       │   │   │
  │       │   │   │
  └───────┼───┘   │
          │       │
          └───────┘

Which rectangles "intersect"?

1 and 5 obviously do.
2 and 4 obviously do not.
3 does -- maybe (depends on how you define the intersection).

Your choice on how to handle pair-3 will affect your algorithm:

If pair-3 does intersect, then all you need to check is if any corner of either rectangle is inside the area of the other rectangle (or on the edge line).

If pair-3 does not intersect, then you must also test that at least one other corner of the rectangle is not inside the area of the other rectangle.

Hope this helps.

[misaeltovar]

pair-3 DOES intersect! but i have no idea how to start the method

[Duthomhas]

then all you need to check is if any corner of either rectangle is inside the area of the other rectangle (or on the edge line).

Here's another hint: your intersect() function for rectangles should look like this:

bool intersects( const Rectangle& r1, const Rectangle& r2 )
  {
  if (point_in_rect( r1.x,                r1.y,                 r2 )) return true;
  if (point_in_rect( r1.x + r1.width - 1, r1.y,                 r2 )) return true;
  if (point_in_rect( r1.x,                r1.y + r1.height - 1, r2 )) return true;
  ...
  return false;
  }

If you are inclined to think it through, you can make it a lot shorter than that, but it will do.

[ne555]

then all you need to check is if any corner of either rectangle is inside the area of the other rectangle (or on the edge line).

I think that you made a mistake. The test fails if you have a cross.

[Duthomhas]

Oops! I knew I was leaving something out...
Yes, the cross is a special case not handled by my algorithm... Solve it and you'll get a better algorithm...

[webJose]

LOL! Duoas, that is probably the most thoughtful and selfless post I have ever seen. I mean, you actually drew 10 rectangles in text to demonstrate this. The OP should be kissing your @ss! :-) Kudos for being so darn helpful!

@ OP: If you don't need an algorithm, just results, and you are using Windows, you can use the regions API to find out if the rectangles intersect. Just saying! :-P