• Create Account

# Optimize overlapping rectangles

7 replies to this topic

### #1Big Muscle  Members   -  Reputation: 135

Like
0Likes
Like

Posted 16 October 2013 - 03:34 PM

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:

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:

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

### #2Paradigm Shifter  Crossbones+   -  Reputation: 3994

Like
0Likes
Like

Posted 16 October 2013 - 03:46 PM

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.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

### #3Big Muscle  Members   -  Reputation: 135

Like
0Likes
Like

Posted 16 October 2013 - 04:06 PM

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.

### #4Paradigm Shifter  Crossbones+   -  Reputation: 3994

Like
0Likes
Like

Posted 16 October 2013 - 04:11 PM

Well I'd fix it so you know which ones exist, much easier then.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

### #5phil_t  Crossbones+   -  Reputation: 1928

Like
0Likes
Like

Posted 16 October 2013 - 05:39 PM

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

### #6Paradigm Shifter  Crossbones+   -  Reputation: 3994

Like
0Likes
Like

Posted 16 October 2013 - 05:48 PM

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

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

Edited by Paradigm Shifter, 16 October 2013 - 05:50 PM.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

### #7AllEightUp  Moderators   -  Reputation: 3642

Like
0Likes
Like

Posted 16 October 2013 - 05:52 PM

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.

### #8Big Muscle  Members   -  Reputation: 135

Like
0Likes
Like

Posted 17 October 2013 - 08:18 AM

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:

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.

PARTNERS