Public Group

# rectangles over rectangles

This topic is 2075 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

so basically i have a list of rectangles

what i have to do is, given one of them, calculate if there is a common area (and eventually calculate it)

i really cant find any simplification over checking point by point, maybve im overthinking it... but isnt there some simpler math to do it?

##### Share on other sites

If you have a very long list, you can do better than two loops brute force by separating your list of rectangles to multiple lists of rectangles that can't overlap. Check out quad trees for more info.

##### Share on other sites

thnx very much, i got it

i guess there is a mistake though cause the final thing

( P2.y = P3.y && P1.y = P4.

i suppose its >=  not = right...

@ ultra

how long is a long list ?

mine is like a hundred and i think it can reach maybe few hundred but never close to thousand, is that enought to justify learning quad trees?

##### Share on other sites

( P2.y = P3.y && P1.y = P4.

i suppose its >=  not = right...

There is a mistake there, yes.

In the comments section of the linked page you can see a user called jeff posting corrections to the simplified expressions.

As a side-note: if you need to compare values to see if they match perfectly, keep in mind that the linked page uses = for comparison, while a lot of languages use == instead.

##### Share on other sites
Here's how I calculate whether a rect is overlapping in C++:
//Returns true if the two rects overlap each other (either by intersecting, or one containing the other).
bool cRect::Overlaps(const cRect &other)
{
if(this->Right() < other.Left())
return false;
if(this->Left() > other.Right())
return false;
if(this->Bottom() < other.Top())
return false;
if(this->Top() > other.Bottom())
return false;

return true;
}
Where Top() returns 'y' pos, Bottom() returns (y + height), Left() returns 'x' pos, Right() rights (x + width).
Normally I just use 'x' and 'y' directly, being public members, but I like to use Left() and Top() for code readability and self-documentation of intent, when I'm also using Right() and Bottom().

Here's how I calculate what the overlapping portion is:

//Resizes the rect to contain just the portion of both rects that overlap.
//Basically, the AND'd portion of the two rects. If they aren't overlapping anything, this rect becomes empty.
void cRect::Intersect(const cRect &other)
{
if(!this->Overlaps(other))
{
this->Clear();
return;
}

int left = std::max(this->Left(), other.Left());
int right = std::min(this->Right(), other.Right());

int top = std::max(this->Top(), other.Top());
int bottom = std::min(this->Bottom(), other.Bottom());

//Recreate this rect from the new positions.
this->FromCorners({left, top}, {right, bottom});
}
As @ultramailman says, if you have a list of 100+ rectangles, you might want to figure out which ones are near each other before doing a huge amount of more-accurate tests. But if you just a few rectangles, doing it brute-force is better. Even if you do have hundreds or thousands of rectangles, you should do it brute-force first to make sure you got it working before you try to optimize it.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 14
• 30
• 9
• 16
• 22