Sign in to follow this  
dworm

rectangles over rectangles

Recommended Posts

dworm    683

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 this post


Link to post
Share on other sites
ultramailman    1720

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 this post


Link to post
Share on other sites
dworm    683

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 this post


Link to post
Share on other sites
Lactose    11446


( 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 this post


Link to post
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this