Jump to content

  • Log In with Google      Sign In   
  • 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.

  • You cannot reply to this topic
5 replies to this topic

#1 dworm   Members   -  Reputation: 334

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?



Sponsor:

#2 richardurich   Members   -  Reputation: 1187

Like
0Likes
Like

Posted 07 February 2014 - 11:54 AM

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

 

You can also just google about calculating rectangle overlap.



#3 ultramailman   Prime Members   -  Reputation: 1561

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.



#4 dworm   Members   -  Reputation: 334

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?



#5 Lactose!   GDNet+   -  Reputation: 2883

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.



#6 Servant of the Lord   Crossbones+   -  Reputation: 17900

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' rather than copy+pasting it all the time.

[Fly with me on Twitter] [Google+] [My broken website]

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.                                                                                                                                                            [Need web hosting? I personally like A Small Orange]
Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal





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.



PARTNERS