Sign in to follow this  
Big Muscle

Optimize overlapping rectangles

Recommended Posts

Big Muscle    135

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

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
phil_t    8084

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

You can end up with the situation where each rect overlaps another though (simplest case, you can have them axis aligned with 4 rects mutually overlapping)

 

Won't let me paste this as an image

 

see this page

 

http://www.sciencekids.co.nz/pictures/math/overlappingrectangles.html

Edited by Paradigm Shifter

Share this post


Link to post
Share on other sites
Hiwas    5807
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
Big Muscle    135

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

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