How to detect if a certain range resides (partly) within an other range?

Lets say I've got two squares and I know their positions, a red and blue square:

redTopX;
redTopY;
redBotX;
redBotY;
blueTopX;
blueTopY;
blueBotX;
blueBotY;

Now, I want to check if square blue resides (partly) within (or around) square red. This can happen in a lot of situations, as you can see in this image I created to illustrate my situation better: alt text http://www.feedpostal.com/etc/ranges.gif

Note that there's always only one blue and one red square, I just added multiple so I didn't have to redraw 18 times.

My original logic was simple, I'd check all corners of square blue and see if any of them are inside 开发者_如何学Csquare red:

if (
((redTopX >= blueTopX) && (redTopY >= blueTopY) && (redTopX <= blueBotX) && (redTopY <= blueBotY)) || //top left
((redBotX >= blueTopX) && (redTopY >= blueTopY) && (redBotX <= blueBotX) && (redTopY <= blueBotY)) || //top right
((redTopX >= blueTopX) && (redBotY >= blueTopY) && (redTopX <= blueBotX) && (redBotY <= blueBotY)) || //bottom left
((redBotX >= blueTopX) && (redBotY >= blueTopY) && (redBotX <= blueBotX) && (redBotY <= blueBotY)) //bottom right
) {
    //blue resides in red
}

Unfortunately, there are a couple of flaws in this logic. For example, what if red surrounds blue (like in situation 1)?

I thought this would be pretty easy but am having trouble coming up with a good way of covering all these situations.. can anyone help me out here?

Regards, Tom

A test that checks whether red rectangle resides completely outside the blue rectangle looks as follows

bool outside = 
  redBotX > blueTopX || redTopX < blueBotX || 
  redBotY > blueTopY || redTopY < blueBotY;

Now, the negative of that will tell you whether red rectangle intersects the blue rectangle

bool intersects =
  !(redBotX > blueTopX || redTopX < blueBotX || 
    redBotY > blueTopY || redTopY < blueBotY);

If you wish, you can apply the De Morgan rule and rewrite it as

bool intersects =
  redBotX <= blueTopX && redTopX >= blueBotX && 
  redBotY <= blueTopY && redTopY >= blueBotY;

Of course, the above tests assume that the coordinates are "normalized*, i.e.

assert(redBotX <= redTopX && redBotY <= redTopY);
assert(blueBotX <= blueTopX && blueBotY <= blueTopY);

Also, the comparisons might be strict or non-strict depending on whether you consider touching rectangles as intersecting or not.

EDIT: I see that you use a different convention for rectangle coordinates: Top is the lower coordinate and Bot is the higher one, i.e.

assert(redTopX <= redBotX && redTopY <= redBotY);
assert(blueTopX <= blueBotX && blueTopY <= blueBotY);

To handle this case you just need to swap the Bot and Top coordinates in all conditions. For example, the last one will now look as follows

bool intersects =
  redTopX <= blueBotX && redBotX >= blueTopX && 
  redTopY <= blueBotY && redBotY >= blueTopY;

Assuming both squares are aligned, as you've indicated:

The squares intersect if all of the following hold:

1. The left side of Red is left of the right side of Blue.
2. The right side of Red is right of the left side of Blue.
3. The top of Red is above the bottom of Blue.
4. The bottom of Red is below the top of Blue.

(Convince yourself that this is true!)

One formula for intersection of two rectangles would be

! ( (redTopX > blueBotX) || (blueTopX > redBotX) || (redTopY < blueBotY) || (blueTopY < redBotY))

You can use DeMorgan's Theorem to simplify.

if (blueTopY < redBotY) return (0);
if (blueBotY > redTopY) return (0);
if (blueBotX < redTopX) return (0);
if (blueTopX > redBotX) return (0);
return (1); // there must clash

for each blue corner:
  if corner is between all four red sides:
    return true
return false

For higher-dimensional ranges or if you want to check a lot of ranges it might be worthwhile to store your ranges (e.g. their centers) in a R tree and search for it for where the corners of your range are.