# Optimize overlapping rectangles

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

## 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 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 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 on other sites

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

##### 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 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

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

##### Share on other sites
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 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:

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.

• 13
• 18
• 29
• 11
• 27