• Create Account

## rectangles over rectangles

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

5 replies to this topic

### #1dworm  Members

683
Like
0Likes
Like

Posted 07 February 2014 - 11:28 AM

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?

### #2richardurich  Members

1187
Like
0Likes
Like

Posted 07 February 2014 - 11:54 AM

http://leetcode.com/2011/05/determine-if-two-rectangles-overlap.html

### #3ultramailman  Prime Members

1720
Like
0Likes
Like

Posted 07 February 2014 - 12:26 PM

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.

### #4dworm  Members

683
Like
0Likes
Like

Posted 07 February 2014 - 12:59 PM

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?

### #5Lactose!  GDNet+

9599
Like
0Likes
Like

Posted 07 February 2014 - 01:20 PM

( 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.

Hello to all my stalkers.

### #6Servant of the Lord  Members

33485
Like
0Likes
Like

Posted 07 February 2014 - 01:43 PM

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.
It's perfectly fine to abbreviate my username to 'Servant' or 'SotL' rather than copy+pasting it all the time.
All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.
Of Stranger Flames -

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.