Jump to content
  • Advertisement
Sign in to follow this  
Big Muscle

Optimize overlapping rectangles

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello,

 

I have an array of 0 - 4 rectangles (each one is specified with [left, top, right, bottom] coordinates) and these rectangles can overlap in some areas. Is there any algorithm which could help to reduce these overlapped areas (not to remove the intersection completely but to remove it only from one of the rectangles).

 

I can be sure that the number of rectangles is always from zero to four. The cases 0 and 1 can be ignored because there are no overlapping rectangles but the rest is always in the following form:

 

[attachment=18406:rectangles.png]

 

The order of rectangles is always maintained but any of them can be missing (which is the main problem here). So array can look e.g. ABCD or BC or AD etc. The goal is to get:

 

[attachment=18407:rectangles.png]

 

I tried several thing but without success. Could someone help? Thanks!

Share this post


Link to post
Share on other sites
Advertisement

You always want B and C to be clipped to A and D if they exist?

 

Draw A and D if they exist

If A exists set B.top and C.top to be A.bottom (or A.bottom + 1), if B and/or C exist.

If D exists set B.bottom and C.bottom to be D.top (or D.top - 1) if B and/or C exist.

Share this post


Link to post
Share on other sites

I used A,B,C,D marks only to specify their order. If array contains e.g. 3 items only I cannot say whether it is ABC, BCD, ACD or ABD.

Share this post


Link to post
Share on other sites

Off the top of my head brute-force approach that works for any number of rectangles:

 

For each separate rectangle pair:

- if one of the rectangles is completely "contained" in the other when looking at one axis (for instance, B is completely contained in A when you look at the x-axis), then check overlapping on the other axis and see if you can chop off a side from the contained rectangle.

- if you do, then bail out of the pair-checking and start again (since one of the rectangles was modified).

Share this post


Link to post
Share on other sites
Guest Hiwas
I'm not sure I really understand the limitations implied here. I'll take a quick stab at a solution but I think we need a better description of the limits of the inputs and the results if this won't work. Basically I'd look at the minimal area change solution. If you simply split the 2 rectangles at the point of overlap you end up with a, b, c, d. Now given the first diagram 'a' would be the left portion of A and 'b' would be the top portion of B. 'b' has the smaller area, so remove 'b' and undo the changes to 'A' since there is no longer any overlap. Repeat until you have no overlap among the given polygons.

Obviously if there is a case where you could actually chop B into two polygons this would not work correctly, i.e. B's top extended over A's top such that chopping out the overlap would leave a portion of B above and below A. But if that is also guaranteed not to happen then the minimal area removal should always provide a usable answer.

Share this post


Link to post
Share on other sites

If I describe a bit the original problem - I need to write a C++ function which receives an array of rectangles which do not overlap and look similary to the picture #2:

 

post-208213-0-38175400-1381958521.png

It is simply rectangular description of the geometry which results from subtraction of two overlapped rectangles. Overlapping can be arbitrary, the size of any rectangle can be arbitrary. I cannot influence the subtraction nor the format which I receive. My task is to inflate this geometry by some number and return it (in the same format - array of 0-4 rectangles). The problem is that returned (inflated) rectangles mustn't overlap - they can touch but not overlap.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!